Искусственный интеллект в Tic-Tac-Toe с использованием С#

Ответ 1

С Tic Tac Toe это не столько ИИ, сколько таблица поиска: для каждой возможной схемы макета найдите лучшее место.

XKCD имеет такую ​​таблицу поиска. В основном каждая макет совета получает уникальный идентификатор и адрес поля, где устанавливается следующий знак. Wikipedia имеет эту таблицу в другом формате.

Таблица работает следующим образом: X идет первым, затем O. X помещает свой X в одну из 9 ячеек. Когда O идет, теперь существует 9 возможных макетов платы, в зависимости от того, какая ячейка имеет X:

 X  |    |
----+----+----
    |    |
----+----+----
    |    |

Если вы посмотрите на карту O, в ней есть 9 больших сеток, а в левом верхнем углу находится X в верхнем левом пятне, так что это тот, который нужно использовать. Место O в центре.

Теперь, когда X снова идет, он должен найти этот макет платы:

 X  |    |
----+----+----
    | O  |
----+----+----
    |    |

Вы найдете это посередине. Красный - это где положить X в изображение XKCD, и это показывает, что вы положили его в нижнем правом углу:

 X  |    |
----+----+----
    | O  |
----+----+----
    |    | X 

Теперь O снова идет и ищет вышерасположенную раскладку, которая находится в нижней правой маленькой сетке в верхней левой большой сетке. O необходимо поместить в среднее дно:

 X  |    |
----+----+----
    | O  |
----+----+----
    | O  | X 

И так далее. Диаграмма немного сложна для чтения вначале (щелкните по ней, чтобы ее увеличить), поскольку она вложена, но, как сказано: вы создаете таблицу Lookup, в которой есть каждый уникальный макет платы и информация, где следует поместить следующий знак.

Это создает идеального противника, хотя: компьютер никогда не проиграет. Как сделать его более человечным, тогда тонкая настройка (например, произвольно отбросить выбор и поместить знак в случайную ячейку)

Ответ 2

Я на самом деле написал такого зверя много лет назад, настоящий автомат, который узнал по его ошибкам.

Характер игры означает, что вы можете хранить результаты для каждой возможной позиции. Хотя TicTacToe практически не применим для игры, такой как шахматы, имеет только 3 ⁹ или 19683, говорится.

Здесь бит интеллекта, который я использовал.

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

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

Таким образом, позиции, которые приведут к победе, станут более вероятными, тогда как те, которые привели к потере, станут менее вероятными.

Причина, по которой желательность никогда не снижалась до нуля, была настолько невозможной, чтобы ее невозможно было достичь. Конечно, один с оценкой желательности одного был очень маловероятным, если бы все остальные имели более высокие баллы.

Для ИИ потребовалось немало игр, чтобы стать достойным игроком, но вы могли бы ускорить его, нажимая его против автоматического врага, который чередовался между тем же AI и случайными ходами.

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

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

Ответ 3

С Tic-Tac-Toe должно быть возможно, чтобы ИИ проанализировал все возможные результаты игры. Вы можете сделать это, создав древовидную структуру, которая веткится для каждого выбора, который может сделать игрок и AI. Оттуда ИИ может выбрать путь, который ведет к его победе.

Чтобы сделать избивающего противника, вы могли бы ограничить количество анализа, которое делает ИИ (т.е. ограничить глубину древовидной структуры) и заставить ИИ решить путь, не зная окончательного результата. Более сильный ИИ будет анализировать больше ходов, более слабый AI меньше.

Ответ 4

Другие ответы говорят вам использовать таблицу поиска. Но учтите, что если на доске больше 3 штук, есть очень простой алгоритм (так как там будет существовать хотя бы одна строка с двумя типами и пустым пространством): Выиграйте, если это возможно, в противном случае заблокируйте противника.

Тогда вам понадобится гораздо меньшая таблица поиска, чтобы обрабатывать шаги открытия.

Ответ 5

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

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

Ответ 6

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