在一个井字游戏的实现中，我认为具有挑战性的部分是确定机器播放的最佳动作。
有哪些算法可以追求？我正在研究从简单到复杂的实现。我该如何处理这部分问题？
维基百科用于玩完美游戏（每次赢或平）的策略看起来像是简单的伪代码：
引自Wikipedia (Tic Tac Toe#Strategy)
玩家可以玩一个完美的井字游戏（赢得或者至少是抽奖），如果他们选择以下列表中的第一个可用移动，每个回合，如Newell和Simon的1972 tic-tac-toe所使用的那样程序。[6]
- 胜利：如果你有两个连续，那就玩第三个连续三个。
- 阻挡：如果对手连续两次，则发挥第三个阻挡他们。
- 福克：创造一个可以通过两种方式获胜的机会。
- Block Opponent's Fork： 选项1：连续创建两个以强制对手进行防守，只要它不会导致他们创建分叉或获胜。例如，如果“X”有一个角，“O”有中心，“X”也有相反的角，“O”不能为了赢得角落。 （在这个场景中扮演角球会为“X”赢得一个分叉。） 选项2：如果存在对手可以分叉的配置，则阻止该分叉。
- 中心：玩中心。
- 对角：如果对手在角落，则对角球。
- 空角：玩空角落。
- 空荡荡的一面：空洞的一面。
认识到什么是“分叉”情况可以按照建议的蛮力方式进行。
注意：一个“完美”的对手是一个很好的练习，但最终不值得'玩'反对。但是，你可以改变上面的优先顺序，给对手的个性带来特征性的弱点。
let gameBoard: [
[null, null, null],
[null, null, null],
[null, null, null]
]
const SYMBOLS = {
X:'X',
O:'O'
}
const RESULT = {
INCOMPLETE: "incomplete",
PLAYER_X_WON: SYMBOLS.x,
PLAYER_O_WON: SYMBOLS.o,
tie: "tie"
}
我们需要一个可以检查结果的函数。该函数将检查一系列字符。无论董事会状态如何，结果都是4个选项之一：不完整，玩家X获胜，玩家O获胜或平局。
function checkSuccession (line){
if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X
if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O
return false
}
function getResult(board){
let result = RESULT.incomplete
if (moveCount(board)<5){
return result
}
let lines
//first we check row, then column, then diagonal
for (var i = 0 ; i<3 ; i++){
lines.push(board[i].join(''))
}
for (var j=0 ; j<3; j++){
const column = [board[0][j],board[1][j],board[2][j]]
lines.push(column.join(''))
}
const diag1 = [board[0][0],board[1][1],board[2][2]]
lines.push(diag1.join(''))
const diag2 = [board[0][2],board[1][1],board[2][0]]
lines.push(diag2.join(''))
for (i=0 ; i<lines.length ; i++){
const succession = checkSuccesion(lines[i])
if(succession){
return succession
}
}
//Check for tie
if (moveCount(board)==9){
return RESULT.tie
}
return result
}我们的getBestMove函数将接收棋盘的状态，以及我们想要确定最佳移动的玩家的符号。我们的函数将使用getResult函数检查所有可能的移动。如果它是胜利，它将得分为1.如果它是松散的，它将得到-1的分数，平局将得到0的分数。如果它未确定，我们将用新状态调用getBestMove函数董事会和相反的象征。由于下一步是对手，他的胜利是当前球员的失利，而得分将被否定。最后，可能的移动得分为1,0或-1，我们可以对移动进行排序，并返回得分最高的移动。
const copyBoard = (board) => board.map(
row => row.map( square => square )
)
function getAvailableMoves (board) {
let availableMoves = []
for (let row = 0 ; row<3 ; row++){
for (let column = 0 ; column<3 ; column++){
if (board[row][column]===null){
availableMoves.push({row, column})
}
}
}
return availableMoves
}
function applyMove(board,move, symbol) {
board[move.row][move.column]= symbol
return board
}
function getBestMove (board, symbol){
let availableMoves = getAvailableMoves(board)
let availableMovesAndScores = []
for (var i=0 ; i<availableMoves.length ; i++){
let move = availableMoves[i]
let newBoard = copyBoard(board)
newBoard = applyMove(newBoard,move, symbol)
result = getResult(newBoard,symbol).result
let score
if (result == RESULT.tie) {score = 0}
else if (result == symbol) {
score = 1
}
else {
let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
nextMove = getBestMove(newBoard, otherSymbol)
score = - (nextMove.score)
}
if(score === 1) // Performance optimization
return {move, score}
availableMovesAndScores.push({move, score})
}
availableMovesAndScores.sort((moveA, moveB )=>{
return moveB.score - moveA.score
})
return availableMovesAndScores[0]
}Algorithm in action，Github，Explaining the process in more details
你需要什么（对于井字游戏或像国际象棋这样更难的游戏）是minimax algorithm，或者它稍微复杂的变体，alpha-beta pruning。然而，普通的天真极小极大对于像tic-tac-toe这样小的搜索空间的游戏来说会很好。
简而言之，您想要做的不是为您寻找具有最佳结果的移动，而是寻找尽可能好的最坏结果的移动。如果你认为你的对手正在以最佳方式进行比赛，那么你必须假设他们会采取对你来说最糟糕的举动，因此你必须采取最小化其最大增益的举动。
生成每个可能的电路板的蛮力方法，并根据它后来在树下生成的电路板对其进行评分，这不需要太多的内存，特别是一旦你认识到90度电路板旋转是多余的，就像在垂直方向上翻转一样，水平和对角轴。
一旦达到这一点，树形图中的数据就会少于1k来描述结果，因此是计算机的最佳移动。
-亚当
Tic-tac-toe的典型算法应如下所示：
Board：代表董事会的九元素向量。我们存储2（表示空白），3（表示X）或5（表示O）。转弯：表示即将播放的游戏移动的整数。第一步将由1表示，最后由9表示。
算法
主算法使用三个函数。
Make2：如果电路板的中心方块是空白，则返回5，即board[5]=2。否则，此函数返回任何非角落方形(2, 4, 6 or 8)。
Posswin(p)：如果球员p在下一步中无法获胜，则返回0;否则，它返回构成获胜动作的平方数。此功能将使程序既赢又赢得对手。此功能通过检查每个行，列和对角线来操作。通过将每个方块的值乘以整行（或列或对角线），可以检查获胜的可能性。如果产品是18（3 x 3 x 2），那么X可以获胜。如果产品是50（5 x 5 x 2），那么O可以获胜。如果找到获胜行（列或对角线），则可以确定其中的空白正方形，并且该函数返回该正方形的数量。
Go (n)：在正方形中移动。如果Turn为奇数，则此过程将[n]设置为3，如果Turn为偶数，则设置为5。它也会逐一递增。
该算法针对每个移动都有内置策略。如果它播放X，则会产生奇数移动，如果它播放O，则为偶数移动。
Turn = 1 Go(1) (upper left corner).
Turn = 2 If Board[5] is blank, Go(5), else Go(1).
Turn = 3 If Board[9] is blank, Go(9), else Go(3).
Turn = 4 If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5 if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6 If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7 If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8 if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9 Same as Turn=7.
我用过它。让我知道你们的感受。
由于您只处理可能位置的3x3矩阵，因此只需编写一个搜索所有可能性而不会增加计算能力。对于每个开放空间，在标记该空间之后计算所有可能的结果（递归地，我会说），然后使用最有可能获胜的移动。
实际上，优化这将是浪费精力。虽然一些简单的可能是：
您可以让AI在一些示例游戏中玩游戏来学习。使用监督学习算法，以帮助它。
不使用游戏区域的尝试。
注意：当你有双倍和分叉时，检查你的双人是否给对手一个双倍。如果它给出，检查你的新强制点是否包含在你的分叉列表中。
使用数字分数对每个方块进行排名。如果采用正方形，则转到下一个选择（按等级按降序排序）。你需要选择一个策略（首先是两个主要的策略，第二个是（我认为）第二个）。从技术上讲，您可以编写所有策略，然后随机选择一个。这将成为一个不太可预测的对手。
这个答案假设你理解为P1实现完美的算法，并讨论如何在对抗普通人类玩家的条件下获胜，他们会比其他人更常犯错误。
如果两名球员都发挥最佳状态，那么比赛当然应该以平局结束。在人类层面上，P1在角落里比赛会更频繁地产生胜利。无论出于什么心理原因，P2都会认为在中锋位置上的比赛并不重要，这对他们来说是不幸的，因为这是唯一没有为P1赢得比赛的回应。
如果P2在中心正确阻挡，P1应该在相反的角落，因为无论出于何种心理原因，P2都会更喜欢角球的对称性，这也会为他们带来失败的局面。
对于P1可以进行任何移动的开始移动，如果两个玩家此后都以最佳方式玩，则可以进行移动P2可以为P1创造胜利。在这个意义上，P1可以在任何地方发挥。边缘移动是最弱的，因为对此移动的可能响应的最大部分产生平局，但是仍然存在将为P1创造胜利的响应。
经验（更确切地说，有趣的是）最好的P1开始动作似乎是第一个角落，第二个中心和最后一个边缘。
您可以亲自或通过GUI添加的下一个挑战是不显示电路板。一个人绝对可以记住所有的状态，但是增加的挑战导致对对称板的偏好，这需要更少的记忆力，导致我在第一个分支中概述的错误。
我知道，我在派对上很开心。