Лабораторная работа №2 Искусственный интеллект игры «Крестики-Нолики»

Игровой ИИ.

ИИ должен иметь возможность проанализировать игровую ситуацию и решить, как он будет ходить дальше. Чтобы дальнейшее описание было более понятным, обозначим три типа ячеек на игровом поле: углы, стороны и центр. Для наглядности ниже приведен рисунок с этими обозначениями:

Рис. -3 Расположение ячеек с точки зрения ИИ.
Логика ИИ для игры «Крестики-Нолики» очень простая. Алгоритм представляет собой завершенный набор инструкций для вычисления результата. Любая программа может использовать несколько алгоритмов. Алгоритм вычислений наилучшего варианта можно представить в виде блок-схемы. ИИ выбирает лучший вариант игры, из тех которые доступны.
Алгоритм ИИ выполняет следующие шаги:

1. 
   Сначала компьютер проверяет, может ли он победить следующим ходом. Если может – победный ход будет сделан. Если нет, выполнение программы переходит ко второму шагу.
   
2. 
   Проверяет, может ли игрок завершить игру следующим ходом. Если да, то старается заблокировать эту возможность. Если возможности победить на следующем ходу у игрока нет, программа переходит к следующему шагу.
   
3. 
   ИИ проверяет, свободна ли хоть одна из ячеек (пробелы в ячейках 1, 3, 7, 9). Если таковые есть – помещает свой знак в одну из доступных ячеек. Если такой возможности нет, программа переходит к шагу 4.
   
4. 
   Программа проверяет, свободен ли центр игрового поля (ячейка с индексом [5]). Если да, то помещает туда свой символ. Если нет – управление передается пятому шагу
   
5. 
   ИИ определяет, какие из ячеек 2, 4, 6, 8 свободны. В одну из свободных ячеек компьютер поставит свой знак.
   

Пятый шаг является последним, потому что если управление дошло до него, то других свободных ячеек кроме 2, 4, 6, 8, не осталось.
Эти шаги выполняются в тот момент, когда поток выполнения программы доходит до блока «Ход компьютера». Эту информацию можно добавить в блок-схему программы:

Рис.4. Алгоритм работы ИИ в игре «Крестики-Нолики».
Этот алгоритм реализован в функциях getComputerMove() и всех остальных, которые вызываются из этой функции.