在井字游戏的实现中，我想具有挑战性的部分是确定机器要玩的最佳动作。
可以追求的算法有哪些？我正在研究从简单到复杂的实现。我将如何解决这部分问题？
praveen chettypally
问问题
117229 次
10 回答
55
来自维基百科的完美游戏策略（每次获胜或平局）似乎是简单的伪代码：
玩家可以玩完美的井字游戏（赢或至少平局），如果他们从以下列表中选择第一个可用的移动，每轮，如纽厄尔和西蒙的 1972 井字游戏中使用的那样[6]
赢：如果您连续获得两个，则玩第三个以获得连续三个。
阻挡：如果对手连续有两个，则使用第三个来阻挡他们。
叉子：创造一个可以通过两种方式获胜的机会。
阻止对手的叉子：
选项 1：连续制造两个以迫使对手防守，只要这不会导致他们制造分叉或获胜。例如，如果“X”有角球，“O”有中锋，而“X”也有对角角，则“O”必须不打角球才能获胜。（在这种情况下打角球会为“X”赢得一个分叉。）
选项 2：如果存在对手可以分叉的配置，则阻止该分叉。
中锋：打中锋。
对角：如果对手在角，打对角。
空角：打一个空角。
空方：播放空方。
可以按照建议以蛮力方式识别“分叉”情况的样子。
注意：一个“完美”的对手是一个很好的练习，但最终不值得“玩”。但是，您可以更改上述优先级，以将特征弱点赋予对手个性。
于 2008-09-24T05:43:13.753 回答
39
您需要的（对于井字游戏或像国际象棋这样更困难的游戏）是极小极大算法，或者它稍微复杂一点的变体，alpha-beta pruning。不过，对于像井字游戏这样的搜索空间很小的游戏，普通的幼稚极小极大也可以。
简而言之，您要做的不是寻找可能对您产生最佳结果的举动，而是寻找最坏结果尽可能好的举动。如果你假设你的对手打得最好，你必须假设他们会采取对你最不利的行动，因此你必须采取使他们的最大收益最小化的行动。
于 2008-09-24T07:40:27.153 回答
14
生成每一个可能的棋盘并根据随后在树的下方产生的棋盘对其进行评分的蛮力方法不需要太多内存，尤其是当您认识到 90 度棋盘旋转是多余的，垂直翻转也是如此，水平轴和对角轴。
一旦达到这一点，树形图中就会有不到 1k 的数据来描述结果，因此是计算机的最佳选择。
-亚当
于 2008-09-24T05:31:26.980 回答
7
tic-tac-toe 的典型算法应如下所示：
Board ：代表棋盘的九元素向量。我们存储 2（表示空白）、3（表示 X）或 5（表示 O）。Turn：一个整数，表示将要进行游戏的哪一步。第一步将由 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): 在方格 n 中移动。如果 Turn 为奇数，此过程将 board 设置[n]为 3，如果 Turn 为偶数，则将 board 设置为 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.
我已经用过了。让我知道你们的感受。
于 2012-07-13T18:16:58.987 回答
6
由于您只处理可能位置的 3x3 矩阵，因此只需编写搜索所有可能性而不会对您的计算能力征税是非常容易的。对于每个开放空间，在标记该空间之后计算所有可能的结果（我会说是递归的），然后使用具有最大获胜可能性的移动。
优化这将是浪费精力，真的。虽然一些简单的可能是：
- 首先检查另一支球队可能获胜的情况，阻止你找到的第一个（如果仍然有 2 场比赛结束）。
- 如果中心是开放的（并且之前的规则没有候选人），请始终选择中心。
- 在边前拐角（再次，如果之前的规则是空的）
于 2008-09-24T05:33:20.830 回答
3
不使用运动场的尝试。
- 赢（你的双倍）
- 如果没有，不要输（对手的双打）
- 如果没有，你是否已经有一个叉子（有一个双倍）
- 如果没有，如果对手有叉子
- 在阻塞点中搜索可能的双分叉（最终获胜）
- 如果不是在阻塞点搜索叉子（这给对手最大的失败可能性）
- 如果不只是阻塞点（不输）
- 如果不搜索 double 和 fork（最终获胜）
- 如果不是只寻找给对手最失败的可能性的叉子
- 如果不是只搜索一个双
- 如果不是死胡同，平手，随机。
- 如果不是（这意味着你的第一步）
- 如果这是游戏的第一步；
- 给对手最多输的可能性（算法只产生角球，给对手7分的可能性）
- 或者只是随机地打破无聊。
- 如果这是游戏的第二步；
- 只找到不失分的（提供更多选择）
- 或在此列表中找到最有可能获胜的点（这可能很无聊，因为它只会导致所有角落或相邻的角落或中心）
- 如果这是游戏的第一步；
注意：当你有加倍和分叉时，检查你的加倍是否给了对手一个加倍。如果给了，检查你的新强制点是否包含在你的分叉列表中。
于 2012-06-19T14:41:52.553 回答
3
您可以让 AI 在一些示例游戏中发挥自己的作用以供学习。使用监督学习算法来帮助它。
于 2008-09-24T05:37:42.020 回答
1
用数字分数对每个方格进行排名。如果选择了一个正方形，则继续下一个选择（按等级降序排列）。您将需要选择一种策略（首先有两个主要策略，其次是三个（我认为））。从技术上讲，您可以对所有策略进行编程，然后随机选择一个。这将使对手变得更难预测。
于 2008-09-24T05:28:33.073 回答
0
这个答案假设您了解为 P1 实现完美算法，并讨论如何在与普通人类玩家的情况下取得胜利，普通人类玩家会比其他人更容易犯一些错误。
如果双方球员发挥最佳，比赛当然应该以平局结束。在人类水平上，P1 在角落里打球的几率要高得多。无论出于何种心理原因，P2 都被诱使认为打中锋并不重要，这对他们来说是不幸的，因为这是唯一不会为 P1 创造获胜游戏的反应。
如果 P2确实在中路正确阻挡，P1 应该打对面的角，因为无论出于何种心理原因，P2 都会更喜欢打角的对称性，这又会为他们带来一个失败的棋盘。
对于 P1 可能为开始移动而做出的任何移动，如果两个玩家之后都发挥最佳，P2 可能会移动将为 P1 创造胜利。从这个意义上说，P1 可以在任何地方播放。边缘移动是最弱的，因为对该移动的最大可能响应产生平局，但仍有一些响应将为 P1 创造胜利。
经验上（更准确地说，传闻）最好的 P1 起始动作似乎是第一个角，第二个中心和最后一个边缘。
您可以亲自或通过 GUI 添加的下一个挑战是不显示板。一个人肯定可以记住所有状态，但是增加的挑战导致了对对称板的偏好，这需要更少的努力来记住，这导致了我在第一个分支中概述的错误。
我知道，我在聚会上很有趣。
于 2016-04-12T17:20:34.050 回答
0
井字游戏适应 min max 算法
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]
}于 2018-01-06T14:15:23.347 回答