Quantum Tic-Tac-Toe AI

Question

В моем классе структур данных нам был присвоен проект, в котором мы должны создать полноценную игру Quantum Tic-Tac-Toe, в которой игрок сталкивается с ботом, который играет в выиграть.

Профессор предложил использовать игровое дерево в нашем искусственном интеллекте. Однако, как обычно, я ищу что-то более сложное.

Может ли кто-нибудь предложить лучший, более продвинутый подход, который я мог бы изучить и реализовать?

---

Я не ищу что-то совершенно смешное, что усложняет проблему. Скорее, я ищу продвинутый подход - например, используя алгоритм A *, а не BFS.

Answer 1

Ваше желание учиться новым вещам (по своему усмотрению) хорошо. Однако сложным решением часто является not the best solution.

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

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

Answer 2

Чтобы обеспечить возможность обучения для своей реализации, вы можете посмотреть в эмулятор для Donald Mitchie «s MENACE (спичечные обучаемые крестики и нолики двигатель) ...

Edit:
Глядя на него, это было сделано совсем немного, см., например, это на CodeProjet
Кроме того, и, приобретая статистическую модель мира (или здесь сокращенного мира Tic-Tac-Toe) и основывая будущие действия на такой модели, является интеллектуальным поведение, это может быть рассмотрено профессором из сферы видимости, потому что не касаясь ключевых концепций, (представление знаний, деревья решений ...)

Answer 3

Есть 2 части для оценки пошаговой игры.

1. Дерево игр.
2. Функция полезности.

Дерево игр позволяет вам разыгрывать ходы заблаговременно, чтобы увидеть, куда они будут вести. Если игра достаточно сложная, что вы не можете вычислить все возможности (http://en.wikipedia.org/wiki/Solved_game), вам нужен способ определения того, как «хороший» сценарий конкретной доски. Плохая функция полезности для шахмат может просто подсчитать значения штук и игнорировать позицию.

Вам также необходим эффективный способ перемещения дерева игры. Читайте о Minimax, обрезке альфа-бета, Negascout и т. Д.

Answer 4

Я на самом деле работает на этой конкретной проблемы прямо сейчас: http://www.rickb.com/quantum-tic-tac-toe

Я считал делать что-то более продвинутое, как хорошо, но я просто прилипает к хорошим алгоритмом поиска ола»альфа-бета.Моя основная проблема заключается в хорошем алгоритме для «оценки» каждого конкретного состояния платы. QTTT намного сложнее стандартного tic tac toe, число состояний для поиска экспоненциально больше. У меня есть полное стандартное игровое дерево tic tac toe в памяти, которое я использую, чтобы быстро найти оценку для каждого «классического» состояния платы, но тогда мне нужно как-то зачислить состояние суперпозиции. Количество состояний настолько велико, что вы не можете заходить слишком глубоко в дерево, поэтому подходящая функция подсчета очков для обрезки дерева раньше необходима.