Какой алгоритм для tic-tac-toe игры я могу использовать для определения “лучшего перемещения” для AI?

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

Кавычка от Википедия (Тик Tac Toe#Strategy)

плеер А может играть в идеальную игру Tic-tac-toe (чтобы победить или, по крайней мере, потянуть), если они выбирают первое доступное перемещение из следующего списка, каждого поворота, как используется в Newell и 1972 Simon tic-tac-toe программа. [6]

1. Win: Если Вы имеете два подряд, играете третье для получения три подряд.

2. Блок: Если противник имеет два подряд, играйте третье для блокирования их.

3. Ветвление: Создайте возможность, где можно победить двумя способами.

4. Ветвление Противника Блока:

   Опция 1: Создайте два подряд для принуждения противника в защиту, пока она не приводит к ним создающий ветвление или победу. Например, если "X" имеет угол, "O" имеет центр, и "X" имеет противоположный угол также, "O" не должен играть угол для завоевания. (Игра угла в этом сценарии создает ветвление для "X" для завоевания.)

   Опция 2: Если существует конфигурация, где противник может разветвиться, блок то ветвление.

5. Центр: Играйте с центром.

6. Противоположный Угол: Если противник находится в углу, играйте противоположный угол.

7. Пустой Угол: Играйте пустой угол.

8. Пустая Сторона: Играйте пустую сторону.

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

Примечание: "идеальный" противник является хорошим осуществлением, но в конечном счете не стоящий 'игры' против. Вы могли, однако, изменить приоритеты выше, чтобы дать характерные слабые места личностям противника.

В чем Вы нуждаетесь (для tic-tac-toe, или намного более трудная игра как Шахматы) минимаксный алгоритм , или его немного более сложный вариант, альфа - бета, сокращающая . Обычный наивный минимакс сделает прекрасный для игры со столь же небольшим пространством поиска как tic-tac-toe, все же.

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

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

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

-Adam

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

Оптимизация этого была бы тратой усилия, действительно. Хотя некоторые легкие могли бы быть:

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

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

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