|
|
| Создание игровой программы "шашки" для игры между человеком и компьютером на языке С++ Builder |
|
С наиболее успешно применяются в задачах распознавания образов, в том числе сильно зашумленных, однако имеются и примеры успешного применения их для построения собственно систем ИИ, это уже ранее упоминавшийся ТАИР. Для моделей, построенных по мотивам человеческого мозга характерна не слишком большая выразительность, легкое распараллеливание алгоритмов, и связанная с этим высокая производительность параллельно реализованных НС. Также для таких сетей характерно одно свойство, которое очень сближает их с человеческим мозгом - нейронные сети работают даже при условии неполной информации об окружающей среде, то есть как и человек, они на вопросы могут отвечать не только "да" и "нет" но и "не знаю точно, но скорее да". Довольно большое распространение получил и эволюционный подход. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, это может быть и НС и набор логических правил и любая другая модель. После этого мы включаем компьютер и он, на основании проверки моделей отбирает самые лучшие из них, на основании которых по самым различным правилам генерируются новые модели, из которых опять выбираются самые лучшие и т.д. В принципе можно сказать, что эволюционных моделей как таковых не существует, существует только эволюционные алгоритмы обучения, но модели, полученные при эволюционном подходе имеют некоторые характерные особенности, что позволяет выделить их в отдельный класс. Такими особенностями являются перенесение основной работы разработчика с построения модели на алгоритм ее модификации и то, что полученные модели практически не сопутствуют извлечению новых знаний о среде, окружающей систему ИИ, то есть она становится как бы вещью в себе. Еще один широко используемый подход к построению систем ИИ - имитационный. Данный подход является классическим для кибернетики с одним из ее базовых понятий - "черным ящиком" (ЧЯ). ЧЯ - устройство, программный модуль или набор данных, информация о внутренней структуре и содержании которых отсутствуют полностью, но известны спецификации входных и выходных данных. Объект, поведение которого имитируется, как раз и представляет собой такой "черный ящик". Нам не важно, что у него и у модели внутри и как он функционирует, главное, чтобы наша модель в аналогичных ситуациях вела себя точно так же. Таким образом здесь моделируется другое свойство человека - способность копировать то, что делают другие, не вдаваясь в подробности, зачем это нужно. Зачастую эта способность экономит ему массу времени, особенно в начале его жизни. Основным недостатком имитационного подхода также является низкая информационная способность большинства моделей, построенных с его помощью. С ЧЯ связана одна очень интересная идея. Кто бы хотел жить вечно? Я думаю, что почти все ответят на этот вопрос "я". Представим себе, что за нами наблюдает какое-то устройство, которое следит за тем, что в каких ситуациях мы делаем, говорим. Наблюдение идет за величинами, которые поступают к нам на вход (зрение, слух, вкус, тактильные, вестибулярные и т.д.) и за величинами, которые выходят от нас (речь, движение и др.). Таким образом человек выступает здесь как типичный ЧЯ. Далее это устройство пытается отстроить какую-то модель таким образом, чтобы при определенных сигналах на входе человека, она выдавала на выходе те же данные, что и человек. Если данная затея будет когда-нибудь реализована, то для всех посторонних наблюдателей такая модель будет той же личностью, что и реальный человек. А после его смерти она, будет высказывать те мысли, которые предположительно высказывал бы и смоделированный человек. Мы можем пойти дальше и скопировать эту модель и получить брата близнеца с точно такими же "мыслями". Можно сказать, что "это конечно все интересно, но при чем тут я? Ведь эта модель только для других будет являться мной, но внутри ее будет пустота. Копируются только внешние атрибуты, но я после смерти уже не буду думать, мое сознание погаснет (для верующих людей слово "погаснет" необходимо заменить на "покинет этот мир")". Что ж это так. Но попробуем пойти дальше. Согласно философским представлениям автора данного курса, сознание представляет собой сравнительно небольшую надстройку над нашим подсознанием, которая следит за активностью некоторых центров головного мозга, таких как центр речи, конечной обработки зрительных образов, после чего "возвращает" эти образы на начальные ступени обработки данной информации. При этом происходит повторная обработка этих образов, мы как бы видим и слышим, что думает наш мозг. При этом появляется возможность мысленного моделирования окружающей действительности при нашем "активном" участии в данном процессе. И именно наш процесс наблюдения за деятельностью этих немногих центров является тем, что мы называем сознанием. Если мы "видим" и "слышим" наши мысли, мы в сознании, если нет, то мы находимся в бессознательном состоянии. Если бы мы смогли смоделировать работу именно этих немногих "сознательных" нервных центров (работа которых правда основана на деятельности всего остального мозга) в качестве одного ЧЯ, и работу "супервизора" в качестве другого ЧЯ, то можно было бы с уверенностью говорить, что "да, данная модель думает, причем так же, как и я". Здесь я ничего не хочу говорить о том, как получить данные о работе этих нервных центров, поскольку на мой взгляд сегодня нет ничего такого, что позволило бы следить за мозгом человека годами и при этом не мешало бы его работе и жизни. И заканчивая беглое ознакомление с различными методами и подходами к построению систем ИИ, хотелось бы отметить, что на практике очень четкой границы между ними нет. Очень часто встречаются смешанные системы, где часть работы выполняется по одному типу, а часть по другому. Сокращенный листинг программы и описание алгоритмаОСНОВНЫЕ КЛАССЫглавный класс оконного интерфейса - TCheckersWindowглавный думающий, играющий класс - BOARDКРАТКОЕ ОПИСАНИЕ АЛГОРИТМАУПРАВЛЕНИЕ производится через оконный интерфейсный класс TCheckersWindow. Ход человека начинается нажатием левой кнопки мышки над фишкой (при этом запускается функция WMLButtonDown() из класса TCheckersWindow), дальше не отпуская кнопку курсорпередвигается на новую позицию фишки и кнопка отпускается (при этом запускается функция WMLButtonUp() из класса TCheckersWindow). Рассмотрим работу этих двухфункций подробнее (см. примечания в тексте функции): Функция WMLButtonDown(): void TCheckersWindow:: WMLButtonDown(TMessage&) // =====НАЧИНАЕМ ХОД======{POINT Point; if (WhoseTurn == Black) // =====ПРОВЕРЯЕМ, ДЕЙСТВИТЕЛЬНО ЛИ ХОДИТ ЧЕЛОВЕК=====return; SetCapture(HWindow); GetCursorPos(&Point); ScreenToClient(HWindow, &Point); MoveStartPoint = bd->GetValidSquare(Point, WhoseTurn); if (MoveStartPoint. x) { MovingPieceType = bd->GetPieceType(MoveStartPoint); HDC hDC = GetDC(HWindow); bd->ClearSquare(hDC, MoveStartPoint); HoldingPiece = TRUE; ReleaseDC(HWindow, hDC); }}Функция WMLButtonUp(): void TCheckersWindow:: WMLButtonUp(TMessage&) {POINT Point; ReleaseCapture(); if (! HoldingPiece || WhoseTurn == Black) return; GetCursorPos(&Point); ScreenToClient(HWindow, &Point); MoveEndPoint = bd->GetEmptySquare(Point); HDC hDC = GetDC(HWindow); if (MoveEndPoint. x && bd->UserMove(MoveStartPoint, MoveEndPoint)) { // ====ЕСЛИ ЧЕЛОВЕК МОЖЕТ СЮДА ПОСТАВИТЬ ФИШКУ... =====bd->RedrawBoard(hDC); // =========ТО ПЕРЕРИСОВЫВАЕМ ДОСКУ=======EnableMenuItem(hMenu, CM_UNDO, MF_BYCOMMAND | MF_ENABLED); EnableMenuItem(hMenu, CM_REDO, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED); if (! bd->AnotherJump()) // =====МОЖНО СДЕЛАТЬ ПОВТОРНЫЙ ХОД? ========{if (bd->NoMoreBlack()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК КОМПЬЮТЕРА... . ==={if (GetApplication() - >ExecDialog(new TEndDialog(this, "UserWonDlg")) // ТО ЧЕЛОВЕК ВЫИГРАЛ! == IDYES) {PostMessage(HWindow, WM_COMMAND, CM_FILENEW, 0L); ReleaseDC(HWindow, hDC); return; }else{PostMessage(HWindow, WM_COMMAND, CM_EXIT, 0L); ReleaseDC(HWindow, hDC); return; }}PostMessage(HWindow, WM_COMMAND, CM_MOVE, 0L); // ==ПЕРЕКЛЮЧАЕМСЯ НА ХОД=== } // =======КОМПЬЮТЕРА=======else // НЕЯВНЫЙ ВЫЗОВ ФУНКЦИИ; // ComputersMove() }else{bd->DrawPiece(hDC, MovingPieceType, MoveStartPoint); }HoldingPiece = FALSE; ReleaseDC(HWindow, hDC); }Функция ComputersMove(): void TCheckersWindow:: ComputersMove(RTMessage) {bd->EndUsersTime(); WhoseTurn = Black; EnableMenuItem(hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED); EnableMenuItem(hMenu, 1, MF_BYPOSITION | MF_DISABLED | MF_GRAYED); EnableMenuItem(hMenu, 3, MF_BYPOSITION | MF_DISABLED | MF_GRAYED); ModifyMenu(hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |MF_STRING, CM_STOP, "&Stop"); DrawMenuBar(HWindow); bd->ComputersTurn(); // =======ПЕРЕКЛЮЧАЕМСЯ НА РАБОТУ ИИ========HDC hDC = GetDC(HWindow); bd->RedrawBoard(hDC); ReleaseDC(HWindow, hDC); WhoseTurn = Red; POINT CursorPoint; GetCursorPos(&CursorPoint); ScreenToClient(HWindow, &CursorPoint); #pragma warn - stvif (PtInRect(&MainWndRect, CursorPoint)) /*SetCursor(CursorHand) */; #pragma warn +stvModifyMenu(hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |MF_STRING, CM_MOVE, "move you"); EnableMenuItem(hMenu, 0, MF_BYPOSITION | MF_ENABLED); EnableMenuItem(hMenu, 1, MF_BYPOSITION | MF_ENABLED); EnableMenuItem(hMenu, 3, MF_BYPOSITION | MF_ENABLED); DrawMenuBar(HWindow); if (bd->NoMoreRed()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК ЧЕЛОВЕКА... . ==={if (GetApplication() - >ExecDialog(new TEndDialog(this, "GameWonDlg")) // ===ТО КОМПЬЮТЕР===== IDYES) // ======ВЫИГРАЛ======{PostMessage(HWindow, WM_COMMAND, CM_FILENEW, 0L); return; }else{PostMessage(HWindow, WM_COMMAND, CM_EXIT, 0L); return; }}bd->StartUsersTime(); // ======ХОД ЧЕЛОВЕКА========}компоненты искусственного интелекта (ии) Компоненты ИИ вызываются функцией ComputersTurn() из класса BOARD: BOOL BOARD:: ComputersTurn() {int iter, i, val, row = 0, col = 0; double t; time_t itime1, itime2; long lNodes; int alpha = - MAXINT, beta = MAXINT; StopSearch = FALSE; ClearRedoStack(); memcpy(SavedBoard, Board, sizeof(Board)); if(! OnlyOneMove(Black, &row, &col)) {Nodes = 0; time(&start_t); PreEvaluate(); // =======ПОЛИТИКА ИГРЫ (НАПАДАТЬ ИЛИ ОТБИВАТЬСЯ) =====/* clear out the best-variation table */for(i = 0; i <= MAXPLY; ++i) {BestVar [i] [i]. org. SetRow(0); BestVar [0] [i]. org. SetRow(0); }/* clear out the Killer table */for(i = 0; i <= MAXPLY; ++i) {Killer [i] [0]. org. SetRow(0); Killer [i] [0]. Value = - 1; }for(iter = IterFlag? 1: SearchDepth; iter <= SearchDepth; ++iter) {lNodes = Nodes; time(&itime1); val = Evaluate(alpha, beta, Black, row, col, iter, 0); if (StopSearch) return FALSE; if(val >= beta) {val = Evaluate(alpha, MAXINT, Black, row, col, iter, 0); if (StopSearch) return FALSE; }else{if(val <= alpha) {val = Evaluate(- MAXINT, beta, Black, row, col, iter, 0); if (StopSearch) return FALSE; }}alpha = val - 12; beta = val + 12; /* seed the killer table with the best variation */for(i = 0; BestVar [0] [i]. org. GetRow(); ++i) {memcpy(&Killer [i] [0], &BestVar [0] [i], sizeof(MOVE)); Killer [i] [0]. Value = 1; /* eliminate the other killer move */Killer [i] [1]. Value = - 1; Killer [i] [1]. org. SetRow(0); }/* clear the rest of the killer table */do{Killer [i] [0]. org. SetRow(0); Killer [i] [1]. org. SetRow(0); }while(i++ < MAXPLY); time(&itime2); t = difftime(itime2, itime1); DisplaySearchStats(iter, val, Nodes - lNodes, t); }time(&end_t); if((t = difftime(end_t, start_t)) ! = 0) {sprintf(buf, "%.0f", t); sprintf(buf, "%ld", Nodes); ComputerTotalTime += t; }else{sprintf(buf, "%ld", Nodes); }for (i = 0; Man [Board [BestVar [0] [i]. org. GetRow()] [BestVar [0] [i]. org. GetCol()]. What]. GetSide() == Black; ++i) {MakeActualMove(BestVar [0] [i]); }}TimeToStr(buf, ComputerTotalTime); return(TRUE); }Функция PreEvaluate() разрабатывает политику игры: void BOARD:: PreEvaluate() {int i, j, xman, inside; int tBSizeDiv2 = BoardSize >> 1; // (BoardSize / 2) /*********************************************************This code gets a rough idea as to who is ahead in Material. **********************************************************/Material [Red] = 0; Material [Black] = 0; Man [REDMAN]. SetValue(100); Man [BLACKMAN]. SetValue(100); Man [REDKING]. SetValue (140); Man [BLACKKING]. SetValue(140); Man [EMPTY]. SetValue(0); Man [OFFBOARD]. SetValue(0); for(i = 1; i <= BoardSize; ++i) {for(j = 1; j <= BoardSize; ++j) {xman = Board [i] [j]. What; Material [Man [xman]. GetSide()] += Man [xman]. GetValue(); }}/****************************************************Now adjust the Material weights based on who is ahead. This is to encourage the fellow who is winning to exchange piecesand the fellow who is behind to not exchange pieces. If Material is dead even then you shouldn't try to force exchangesjust on general principles. *****************************************************/if(Material [Red] >= Material [Black]) {- -Man [REDMAN] ;--Man [REDKING] ; }else{- -Man [BLACKMAN] ;--Man [BLACKKING] ; }/****************************************************Examine each and every square and calculate the bonus values. *****************************************************/for(i = 1; i <= BoardSize; ++i) {for(j = 1; j <= BoardSize; ++j) {inside = (j > 1 && j < BoardSize) ? 1: 0; SValue [i] [j] [REDMAN] = Man [REDMAN]. GetValue() + inside; SValue [i] [j] [REDKING] = Man [REDKING]. GetValue() + inside; SValue [i] [j] [BLACKMAN] = Man [BLACKMAN]. GetValue() + inside; SValue [i] [j] [BLACKKING] = Man [BLACKKING]. GetValue() + inside; /* bonus points for central squares */if(abs(tBSizeDiv2 - i) < 2 && abs(tBSizeDiv2 - j) < 3) {++SValue [i] [j] [REDMAN] ; ++SValue [i] [j] [REDKING] ; ++SValue [i] [j] [BLACKMAN] ; ++SValue [i] [j] [BLACKKING] ; }/* bonus for non-Crown piece advancement */if(i > 2) {SValue [i] [j] [REDMAN] += i - 2; }if(i < BoardSize - 2) {SValue [i] [j] [BLACKMAN] += BoardSize - i - 1; }if(i == 1) ++SValue [i] [j] [REDMAN] ; if(i == BoardSize) ++SValue [i] [j] [BLACKMAN] ; }}Material [Red] = 0; Material [Black] = 0; for(i = 1; i <= BoardSize; ++i) {for(j = 1; j <= BoardSize; ++j) {xman = Board [i] [j]. What; Material [Man [xman]. GetSide()] += SValue [i] [j] [xman] ; }}}Функция Evaluate() представляет непосредственно функцию ИИ. Основной принцип - на глубину depth анадблжлизируются возможные ходы компьютера и ответные ходы человека - ищем наилучшую стратегию: int BOARD:: Evaluate(int alpha, int beta, SIDE player, int row, int col, int limit, int ply) {MOVE *list = new MOVE [MAXMOVES] ; MOVE *mptr, *endptr; int NumMoves, val; int num_back = 0; int retval = 0; int t1 = WIN - 2 - ply; int plyp1 = ply + 1; if (StopSearch) goto END_EVALUATE; ++Nodes; if((NumMoves = Lmg(list, player, row, col, ply)) == 0) {retval = LOSS + ply; goto END_EVALUATE; }MessageScan(); if (StopSearch) {retval = 0; goto END_EVALUATE; }if(list->Quiescent(limit, NumMoves, ply)) {retval = (Material [player] - Material [OPLAYER] + (NumMoves > 3? 1: 0)); goto END_EVALUATE; }for(mptr = list, endptr = mptr + NumMoves; mptr < endptr && alpha < t1; mptr++) {MakeMove(*mptr); if(mptr->Capture! = EMPTY) {if(! (mptr->Crown) && CanJump(player, mptr->dest. GetRow(), mptr->dest. GetCol())) {val = Evaluate(alpha, beta, player, mptr->dest. GetRow(), mptr->dest. GetCol(), limit, plyp1); }else{val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1; }}else{if(limit == 0 || NumMoves == 1) {val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit, plyp1) * - 1; }else{val = Evaluate(- beta, - alpha, OPLAYER, 0, 0, limit? limit - 1: 0, plyp1) * - 1; }}UnMakeMove(*mptr); if(val > alpha) {if(val >= beta) {if(KillerFlag) UpdateKillerTable(*mptr, ply); retval = beta; goto END_EVALUATE; }else{alpha = val; ++num_back; UpdateBestVariation(mptr, ply); }}BestVar [plyp1] [plyp1]. org. SetRow(0); }retval = alpha; END_EVALUATE: delete list; return retval; }Вспомагательная функция GenMoves() генерурует возможные ходы и записывает их в список: /********************************************generates the list of moves for a given player at a row, colreturns the number of legal moves found********************************************/int BOARD:: GenMoves(MOVE *list, int row, int col) {int NumMoves; int what; int trow1 = row + 1, tcol1 = col + 1, trowm1 = row - 1, tcolm1 = col - 1; NumMoves = 0; what = Board [row] [col]. What; if(what == REDKING || what == BLACKKING || what == BLACKMAN) {if(Board [trowm1] [tcolm1]. What == EMPTY) {list->org. SetRow(row); list->org. SetCol(col); list->dest. SetRow(trowm1); list->dest. SetCol(tcolm1); list->Capture = EMPTY; list->Crown = ((row == 2) && (what == BLACKMAN)); ++NumMoves; ++list; }if(Board [trowm1] [tcol1]. What == EMPTY) {list->org. SetRow(row); list->org. SetCol(col); list->dest. SetRow(trowm1); list->dest. SetCol(tcol1); list->Capture = EMPTY; list->Crown = ((row == 2) && (what == BLACKMAN)); ++NumMoves; ++list; }}if(what == REDKING || what == BLACKKING || what == REDMAN) {if(Board [trow1] [tcolm1]. What == EMPTY) {list->org. SetRow(row); list->org. SetCol(col); list->dest. SetRow(trow1); list->dest. SetCol(tcolm1); list->Capture = EMPTY; list->Crown = ((row == BoardSize - 1) && (what == REDMAN)); ++NumMoves; ++list; }if(Board [trow1] [tcol1]. What == EMPTY) {list->org. SetRow(row); list->org. SetCol(col); list->dest. SetRow(trow1); list->dest. SetCol(tcol1); list->Capture = EMPTY; list->Crown = ((row == BoardSize - 1) && (what == REDMAN)); ++NumMoves; ++list; }}return(NumMoves); }Описание работы программыИгра запускается файлом CHECKERS. EXE. Вследствии того, что программа компилировалась в пакете BORLAND C++ 3.1. для WINDOWS, для запуска программы необходимы следующие DLL - файлы: BC30RTL. DLLOWL31. DLLTCLASS31. DLLВ текстовом файле DEPTH хранится единственная настройка игры - глубина анализа ходов, по умолчанию она установлена в 3 - средний уровень игры в шашки. Меню игры предельно простое и состоит из единственного пункта - “move you” - пропуск хода. Ниже приведено две экранные копии программы. Начало игры ВыводыВ ходе курсовой работы были исследованы источники по задачам искусственного интеллекта (ИИ), рассмотрены уже существующие программы для шашечных игр. Была разработана относительно несложная функция ИИ, главными задачами которой является предсказание на установленную глубину своих ходов и ходов противника. Это предсказание базируется на выборе наилучших ходов с обеих сторон. На финальном этапе функция ИИ избирает наиболее выгодную для компьютера цепочку ходов. Программа отличается от существующих на рынке простотой интерфейса и настроек. Литература http: // newasp. omskreg. ru/intellect Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке Си. Мн., 1992. 240 С. Нейбауэр А. Моя первая программа на С/С++.П., 1995. 368 С. Бруно Бабэ. Просто и ясно о Borland C++.М., 1996. 400 С. Шамас Н.К. Основы С++ и обьектно-ориентированного программирования. К., 1996. 448 С. Справочник по классам Borland C++ 4.0.К., 1994.256 С. ObjectWindows для C++. К., 1993., 208 С. Том Сван. Программирование для Windows в Borland C++. М., 480 С. Н. Барканати. Программирование игр для Windows на Borland C++. М., 1994. 512 С.
Страницы: 1, 2, 3
|
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|
