javascript 简单的井字游戏 AI
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15753572/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Simple tic-tac-toe AI
提问by user1136342
I know this has been asked a lot and I've searched other code but most of what I've seen doesn't seem flawless (never loses) and simple, elegant and efficient. And I'm unable to decide which type of solution would fit that description.
我知道这已经被问了很多，我已经搜索了其他代码，但我所看到的大部分内容似乎并不完美（永远不会丢失），而且简单、优雅和高效。而且我无法决定哪种类型的解决方案适合该描述。
The solutions I've seen are:
我见过的解决方案是：
(1) Using minimax with alpha-beta pruning. This seems complicated to me and possibly unnecessary for such a simple game? Is it probably too complicated? If not, would I need to do a lot of hard coding or am I misunderstanding the algorithm?
(1) 使用极小极大与 alpha-beta 剪枝。这对我来说似乎很复杂，对于这样一个简单的游戏来说可能没有必要？是不是太复杂了？如果没有，我是否需要进行大量硬编码，还是我误解了算法？
(2) Write your code using the pseudocode strategy from Wikipedia... I'm not exactly sure how to implement this. For example, it just says "check for forks". Would most of these checks be done by having an array of winningLines and checking if they'd be filled in or something like that? If not, can someone give me hints on what data structures or any basic tips on how to implement the checks posed in the pseudocode here: http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy. I've also seen algorithms that give a numerical value to an 'X' square and an 'O' square and then use the sum to decide the winner but I don't see why this is particularly useful.
(2) 使用维基百科的伪代码策略编写您的代码......我不确定如何实现这一点。例如，它只是说“检查叉子”。这些检查中的大多数是否会通过拥有一组 winsLines 并检查它们是否被填充或类似的东西来完成？如果没有，有人可以给我提示什么数据结构或有关如何实现伪代码中提出的检查的任何基本技巧：http: //en.wikipedia.org/wiki/Tic-tac-toe#Strategy。我还看到了一些算法，它们为“X”方格和“O”方格提供数值，然后使用总和来决定获胜者，但我不明白为什么这特别有用。
Any other reasonablesolutions?
还有其他合理的解决方案吗？
回答by AnxGotta
To be honest, when dealing with AI and heuristics, the most simple tasks can become complicated very quickly. The minimax approach is going to give you the best results and it shouldn't be too difficult considering the fact that you are implementing AI. It is an established standard with 2 player turn based gaming logic.
老实说，在处理 AI 和启发式算法时，最简单的任务会很快变得复杂。极小极大方法将为您提供最佳结果，考虑到您正在实施人工智能，这应该不会太难。它是基于 2 人回合的游戏逻辑的既定标准。
Check out this website... it gives some good insight into tic-tac-toe AI and the minimax implementation.
看看这个网站……它对井字棋人工智能和极小极大实现提供了一些很好的见解。
http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html
http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html
Edit:
编辑：
Noticing that someone wrote "Brute Force"... this is going to end up being an inefficient way of the implementation of the heuristics involved in minimax. Iteration through every possible move based on the other players last move is just another way to implement a heuristic.. except it seems to be, in my opinion, more work. Minimax implementation will be simple and effective.
注意到有人写了“蛮力”……这最终将成为实现极小极大启发式的一种低效方式。基于其他玩家的最后一步迭代每一个可能的移动只是实现启发式的另一种方式......除了在我看来，它似乎需要更多的工作。Minimax 的实现将是简单而有效的。
Edit2:
编辑2：
"Simpler implementation" is somewhat relative. Minimax is the standard and as I said in the comment you can manipulate the heuristic to suit the cases you are looking for...
“更简单的实现”有点相对。Minimax 是标准，正如我在评论中所说，您可以操纵启发式以适应您正在寻找的情况......
I wish I could tell you the simplest way but there are so many variables dependent on the implantation of your game in code.
我希望我能告诉你最简单的方法，但是有很多变量取决于你的游戏在代码中的植入。
Take the suggestions, look at you game implementation, and then see what suits you best!
接受建议，看看你的游戏实现，然后看看什么最适合你！
What is simple to one person might be complicated to another. I'm just trying to give you options and minimax is pretty solid. Maybe try adjusting it to fit your needs.
对一个人来说简单的事情对另一个人来说可能很复杂。我只是想为您提供选择，而 minimax 非常可靠。也许尝试调整它以满足您的需求。
Edit3:
编辑3：
Let me know if you need more direction. I'm happy to help.
如果您需要更多指导，请告诉我。我很乐意提供帮助。
回答by Niet the Dark Absol
Use the format of your choice to "encode" this imageinto a set of moves. The AI will always win or tie.
使用您选择的格式将此图像“编码”为一组动作。AI 将始终获胜或打平。
For example, you could encode it as follows:
例如，您可以按如下方式对其进行编码：
var turns = {
"mefirst":{
"move":0,
"next":[
null,
{
"move":4,
"next":[
null,
null,
{"move":8}, // win
{"move":8}, // win
null,
{"move":8}, // win
{"move":8}, // win
{"move":8}, // win
{
"move":6,
"next":[
null,
null,
/* AND SO ON... */
]
}
};
Then you can start with:
然后你可以开始：
if( ai_goes_first) {
game = turns.mefirst;
makeMove(game.move);
}
else game = turns.themfirst;
playerTurn();
Where playerTurnis something like:
哪里playerTurn是这样的：
function playerTurn() {
when player clicks a valid squeare {
game = game.next[chosenSquare];
makeMove(game.move);
if( game.next) playerTurn();
}
}
