Теория разработки ИИ на примере крестиков-ноликов
glaurung@mail.ngs.ru
Эта статья будет посвящена тому, как написать простую, даже банальную игру: крестики-нолики. Причем самые обыкновенные - 3 на 3. Здесь я подробно опишу этапы написания программы и все рассуждения.
Статью можно поделить на две части - эта, где изложена теория написания крестиков-ноликов (далее - КН), и вторая - исходники программы, снабженные обильными комментариями (программа написана на C++ и адаптирована под MSVS6).
Так вот. Основа любой более или менее продвинутой игры - искусственный интеллект (ИИ). Я не подразумеваю тетрис или что-нибудь типа игры "Lines", где игрок не должен бороться с компьютером. И в наших КН ИИ должен присутствовать - пускай слабенький и тупенький, но хоть какой-то.
Для создания ИИ (если, конечно, не строить планы создать андроида) нужно сначала определиться, что он должен делать. Даже самый навороченный современный ИИ не может делать всего; интервал его способностей крайне ограничен. У нашего ИИ будет только одна задача - руководствуясь определенными правилами, поставить крестик (или нолик) в определенную клетку.
И нам надо эти правила сформулировать. Для этого надо напрячь мозги и вспомнить все тонкости игры в КН, а лучше - сыграть с десяток партий с приятелем. Поиграли, поиграли, и вывели, что:
- При идеальной игре выиграть невозможно
- Единственный шанс выиграть (если противник не абсолютно туп) - создать безвыходную ситуацию. Это достигается созданием определенной комбинации ваших меток, при которой, как бы враг ни походил, вы всегда можете выиграть партию. Эти комбинации - заполнены 3 угловые точки, причем между 2-мя парами из них должны быть пустые клетки; заполнены 2 угловые и центральная, и соблюдается то же правило.
- Из второго пункта можно понять, что существуют "выигрышные" позиции - это (1,1), (1,3), (3,1), (3,3), (2,2).
При формулировке я пользовался следующими определениями:
- Метка - крестик или нолик.
- Линия - она и есть линия, набор из 3-х клеток.
Теперь, поняв правила игры, можно писать ИИ.
Первым делом, компьютер должен проверить на наличие выигрышных ситуаций. Правда ведь, если компьютер может походить так, что выиграет, остальное его не колышет?
Затем, если ИИ не может выиграть с одного хода, он должен проверить наличие опасных для него ситуаций (т.е. противник выиграет следующим ходом).
Если и таковые ситуации отсутствуют, то компьютер должен походить просто так, а лучше - на одну из выигрышных позиций (причем лучше проверить, можно ли создать противнику безвыходную ситуацию). Если все таковые заняты, то просто на первую попавшуюся свободную клетку.
Итак, стоит обобщить вышеизложенное и кратко изложить шаги ИИ:
- Проверить, нельзя ли завершить игру победой.
- Проверить, не может ли враг на следующем ходе завершить игру победой.
- Проверить, можно ли создать противнику безвыходную ситуацию
- Если нельзя, то походить просто на одну из выгодных позиций.
- Если и это невозможно, походить на первую попавшуюся клетку.
Вот, в общем, и все. В примере компьютер играет сам с собой - и во всех тестах, что я проводил, игра заканчивается ничьей.
Оставить комментарий
Комментарии
в 4 утра думать над своим алгоритмом лень:)
Коротко по сабжу: AI + нейронка, после первого запуска проигрывает сам с собой длинный ряд партеек в крестики-нолики (пара минут), формируя csv-лог, сразу затем можете пытаться его обыграть. С гитхаба ссылка ведет на подробное описание алгоритма на русском (без зауми) с примерами кода.
Удачи в игре. :)
Так надо некоторых людей программировать)))
Статья ни о чём . . .
