Quantum Tic-Tac-Toe [закрытый] AI
Существует инструмент, названный CloneDigger, который помогает Вам найти подобные фрагменты кода.
4 ответа
Ваше желание узнавать что-то новое (даже самостоятельно) - это хорошо. Однако сложное решение часто не лучшее решение .
Есть очень веская причина, по которой ваш профессор предложил использовать дерево игр для ИИ. Предлагается, потому что это правильный инструмент для работы. Нет лучшего подхода, который вы могли бы изучить, потому что это лучший подход.
Вы упомянули, что находитесь в классе структур данных (который обычно является классом первого или второго года). Я предполагаю, что цель вашего задания - изучить древовидные структуры данных. Если вы хотите усложнить задачу, сначала напишите древовидную версию, а затем исследуйте другие способы решения той же проблемы.
There are 2 parts to evaluating a turn based game.
- The game tree.
- A utility function.
The game tree allows you to play out moves ahead of time to see where they will lead. If the game is complex enough that you cannot compute all possibilities (http://en.wikipedia.org/wiki/Solved_game), then you need a way of determining how "good" a particular board scenario is. A poor utility function for chess might simply count piece values and ignore position.
You also need an efficient way of traversing the game tree. Read about Minimax, Alpha-beta pruning, Negascout, etc.
To provide a learning feature to your implementation, you may look into an emulator for Donald Mitchie's MENACE (Matchbox Educable Noughts And Crosses Engine)...
Edit:
In looking into it, this has been done quite a bit, see for example this on CodeProjet
Furthermore, and while acquiring a statistical model of the world (or here of the Tic-Tac-Toe reduced world) and basing future actions upon such a model is intelligent behavior, it may be considered out of scope by your professor, because not touching key concepts you probably covered in class (knowledge representation, decision trees...)
На самом деле я сейчас работаю над этой конкретной проблемой: http://www.rickb.com/quantum-tic-tac-toe
Я думал о том, чтобы что-то сделать более продвинутый, но я просто придерживаюсь старого доброго алгоритма поиска альфа-бета. Моя основная проблема - это придумать хороший алгоритм для "оценки" каждого конкретного состояния платы. QTTT намного сложнее, чем стандартные крестики-нолики, количество состояний для поиска экспоненциально больше. У меня в памяти есть полное стандартное дерево игры в крестики-нолики, которое я использую, чтобы быстро найти счет для каждого «классического» состояния доски, но затем мне нужно как-то оценить состояние суперпозиции. Количество состояний настолько велико, что вы не можете углубиться в дерево, поэтому необходима соответствующая функция оценки для ранней обрезки дерева.