Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11639
Последний выпуск: 19.06.2015

Теория разработки ИИ на примере крестиков-ноликов

Izvraschenok, 2003.
glaurung@mail.ngs.ru

Эта статья будет посвящена тому, как написать простую, даже банальную игру: крестики-нолики. Причем самые обыкновенные - 3 на 3. Здесь я подробно опишу этапы написания программы и все рассуждения.

Статью можно поделить на две части - эта, где изложена теория написания крестиков-ноликов (далее - КН), и вторая - исходники программы, снабженные обильными комментариями (программа написана на C++ и адаптирована под MSVS6).

Так вот. Основа любой более или менее продвинутой игры - искусственный интеллект (ИИ). Я не подразумеваю тетрис или что-нибудь типа игры "Lines", где игрок не должен бороться с компьютером. И в наших КН ИИ должен присутствовать - пускай слабенький и тупенький, но хоть какой-то.

Для создания ИИ (если, конечно, не строить планы создать андроида) нужно сначала определиться, что он должен делать. Даже самый навороченный современный ИИ не может делать всего; интервал его способностей крайне ограничен. У нашего ИИ будет только одна задача - руководствуясь определенными правилами, поставить крестик (или нолик) в определенную клетку.

И нам надо эти правила сформулировать. Для этого надо напрячь мозги и вспомнить все тонкости игры в КН, а лучше - сыграть с десяток партий с приятелем. Поиграли, поиграли, и вывели, что:

  • При идеальной игре выиграть невозможно
  • Единственный шанс выиграть (если противник не абсолютно туп) - создать безвыходную ситуацию. Это достигается созданием определенной комбинации ваших меток, при которой, как бы враг ни походил, вы всегда можете выиграть партию. Эти комбинации - заполнены 3 угловые точки, причем между 2-мя парами из них должны быть пустые клетки; заполнены 2 угловые и центральная, и соблюдается то же правило.
  • Из второго пункта можно понять, что существуют "выигрышные" позиции - это (1,1), (1,3), (3,1), (3,3), (2,2).

При формулировке я пользовался следующими определениями:

  • Метка - крестик или нолик.
  • Линия - она и есть линия, набор из 3-х клеток.

Теперь, поняв правила игры, можно писать ИИ.

Первым делом, компьютер должен проверить на наличие выигрышных ситуаций. Правда ведь, если компьютер может походить так, что выиграет, остальное его не колышет?

Затем, если ИИ не может выиграть с одного хода, он должен проверить наличие опасных для него ситуаций (т.е. противник выиграет следующим ходом).

Если и таковые ситуации отсутствуют, то компьютер должен походить просто так, а лучше - на одну из выигрышных позиций (причем лучше проверить, можно ли создать противнику безвыходную ситуацию). Если все таковые заняты, то просто на первую попавшуюся свободную клетку.

Итак, стоит обобщить вышеизложенное и кратко изложить шаги ИИ:

  • Проверить, нельзя ли завершить игру победой.
  • Проверить, не может ли враг на следующем ходе завершить игру победой.
  • Проверить, можно ли создать противнику безвыходную ситуацию
  • Если нельзя, то походить просто на одну из выгодных позиций.
  • Если и это невозможно, походить на первую попавшуюся клетку.

Вот, в общем, и все. В примере компьютер играет сам с собой - и во всех тестах, что я проводил, игра заканчивается ничьей.

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
97K
28 июля 2016 года
Sergey Sarabun
0 / / 28.07.2016
+5 / -3
Мне нравитсяМне не нравится
28 июля 2016, 17:29:44
А где ИИ? архитектура нейронной сети? механизм обучения?
2.
32K
16 августа 2007 года
k06a
0 / / 16.08.2007
+4 / -4
Мне нравитсяМне не нравится
7 декабря 2007, 21:10:11
Теперь мы умеем в ХО играть)))
Так надо некоторых людей программировать)))
Статья ни о чём . . .
3.
Аноним
+0 / -3
Мне нравитсяМне не нравится
12 февраля 2006, 04:53:41
Точно алгоритм. Вот нейронную сеть бы обучить на обшибках своих было бы не кисло.
4.
Аноним
+9 / -5
Мне нравитсяМне не нравится
27 июня 2005, 20:36:10
это не ИИ это банальный алгоритм действий
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог