[译]井字游戏使用AI –简单方法
By robot-v1.0
本文链接 https://www.kyfws.com/ai/tic-tac-toe-using-ai-the-easy-way-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 10 分钟阅读 - 4529 个词 阅读量 0井字游戏使用AI –简单方法(译文)
原文地址:https://www.codeproject.com/Articles/1275528/Tic-Tac-Toe-Using-AI-The-Easy-Way
原文作者:George Swan
译文由本站 robot-v1.0 翻译
前言
A simple invincible implementation of Tic Tac Toe
井字游戏的简单无敌实现
介绍(Introduction)
一些使用AI进行播放的应用(Some of the apps that use AI to play) 井字游戏(Tic Tac Toe) 对抗对手非常复杂.本文描述了一种简单的基于策略的方法,无需使用递归算法或复杂的存储动作数据库.应该指出,在这个阶段,“使用AI"是指示例应用程序模仿人类玩家的动作和反应的能力,而不是仅允许两个人进行对抗的应用程序.这不是机器学习中的练习.它更多是如何使用(against an opponent are incredibly complicated. This piece describes a simple strategy-based approach without using recursive algorithms or a complex database of stored moves. It should be stated, at this stage, that ‘using AI’ refers to the sample application’s ability to mimic the actions and responses of a human player, in contrast to apps that simply allow two people to play against each other. It’s not an exercise in machine learning. It’s more of an example of how to use the) 责任链模式(chain of responsibility pattern) 对人类对手的举动实施结构化反应.(to implement a structured response to moves made by a human opponent.)
基本策略(The Basic Strategy)
这里的想法是将构成板的九个正方形矩阵分成一系列的八行.每行有三个正方形.如果任何一个玩家占据一行中的所有三个方格,则他们将赢得比赛.因此,这些线由构成木板矩阵的3行,3列和两个对角线组成. AI会先行评估线路的状态.(The idea here is to divide the nine square matrix that forms the board into a series of eight lines. Each line has three squares. If any one player occupies all three of the squares in a line, they win the game. So the lines consist of the 3 rows, 3 columns and two diagonals that make up the board matrix. The AI appraises the state of the lines before making its move.)
评估一条线(Appraising a Line)
评估需要系统地进行.首先要检查的是潜在的获胜线.那条线中AI已占据3个正方形中的2个,第三个正方形为空.如果找不到胜利,那么接下来的事情就是看对手是否可以在接下来的动作中获胜.在这种情况下做出的移动是强制移动,从某种意义上说,如果不进行移动,游戏将会失败.还有另一种不太明显的强制动作,那就是对手有机会在接下来的动作中打开2条获胜线.有两条获胜线的情况称为分叉.(The appraisal needs to be done in a systematic manner. The first thing to check for is a potentially winning line. That’s a line where the AI has already occupied 2 of the 3 squares and the third square is empty. The next thing, if no win is found, is to see if the opponent can win on the following move. The move made in response to this situation is a forced move in the sense that the game is lost if the move is not played. There’s another forced move that’s not quite as obvious and that’s where the opponent has the opportunity to open up 2 winning lines on their next move. The situation where there are two winning lines is called a fork.)
防止叉(Preventing Forks)
在上面的示例中,存在一个潜在的分叉,其中包含具有来自第0列的正方形的线和来自第2行的具有正方形的线.一个潜在的分叉包含两条共享一个公共正方形的线,在这种情况下,其位于索引的6中.方阵.两条线都由同一个玩家占据,但是每条线都只有一个方块,而该方块不是共享方块.当检测到这种情况时,有一个潜在的分叉.防御是阻止两条路线之一.(In the example above, there is a potential fork involving the line with the squares from column 0 and the line with the squares from row 2. A potential fork involves two lines that share a common square, in this case it’s at index 6 in the squares array. Both lines are occupied by the same player but each line has only a single square occupied and that square is not the shared square. When this situation is detected, there is a potential fork. The defence is to block one of the two lines.)
上面是一个双叉,涉及第0列第2行和第2列第0行的行.防御与单行相同-阻止其中一行.但在这里,(Above is a double fork involving lines Column 0 Row 2 and Column 2 Row 0. The defence is the same as for a single fork – block one of the lines. But here,) PlayerX
一定不能占据一个角正方形.因此,在选择另一个正方形之前,应先采取预防叉的动作,以直线的三个正方形阵列中的中心正方形为准.当AI检查了获胜路线和潜在分叉,但没有找到时,它就可以采取战略行动.(must not take a corner square. So a fork prevention move should look to take the centre square in the line’s three square array before choosing another square. When the AI has checked for winning lines and potential forks and has found none, it is in a position to play a strategic move.)
战略举措(Strategic Moves)
板上的所有正方形的值都不相等.中心正方形是最强大的正方形,因为它在四条线之间共享.接下来最强大的是四个角正方形,这些正方形由三条线共享.可以说中心正方形的影响值为4,角正方形的影响值为3.但这是假定所有共享这些正方形的线都处于活动状态.这并非总是如此.两个玩家都已经占据的线实际上是多余的,因此,该线在该线的存在不应该计入该线的影响值.采取具有最高影响值的正方形的策略将始终导致AI占据中心正方形(如果有)或角落正方形(如果没有).为了避免出现下面显示的丢失情况,这是必不可少的.(All squares on the board are not of equal value. The centre square is the most powerful square as it is shared between four lines. The next most powerful are the four corner squares, these squares are shared by three lines. It could be said that the centre square has an impact value of 4 and the corner squares have an impact value of 3. But this assumes that all the lines that share those squares are active. This is not always the case. A line that’s already occupied by both players is effectively redundant, so the square’s presence in that line should not count towards the square’s impact value. Adopting the strategy of taking the square with the highest impact value will always result in the AI occupying the centre square, if it’s available, or a corner square if it’s not. This is essential in order tp avoid the losing scenario show below.)
PlayerO
之后未能取得角点正方形(has failed to take a corner square after) PlayerX
占据了中心,输掉了比赛.(took the centre and has lost the game.)
在代码中实施策略(Implementing the Strategy in Code)
这里的窍门是使用(The trick here is to use the) 责任链模式(chain of responsibility pattern) 避免多重嵌套(to avoid multiple and nested) if then else
返回AI的方法中的语句((statements in the method that returns the AI’s () PlayerX
)移动.这样该方法变为:() move. So that the method becomes:)
public Move MoveX(IBoard board)
{
this.board = board;
moveHandler.ReSet(board);
Move result = moveHandler.
HandleXWin().
HandleOWinOnNext().
HandlePossibleFork().
HandleStrategicMove().Result;
return result;
}
的(The) MoveHandler
链中的每个方法都返回的实例(methods in the chain each return the instance of the) MoveHandler
类.这种安排可以使用上面显示的格式调用连续方法.所有方法都遵循类似的模式,如(class. This arrangement enables consecutive methods to be called using the format shown above. All the methods follow a similar pattern as can be seen in the) HandleXWin
方法.(method.)
public MoveHandler HandleXWin()
{
if (IsHandled) return this;
if (gameScorer.BestScoreX == Constants.WinOnNextMove)
{
//this is a winning Line it has 2 X and 0 O
lineService.TryFindEmptySquare(gameScorer.BestLineX, out int index);
Result.Index = index;
Result.MoveResult= GameState.Xwin;
IsHandled = true;
}
return this;
}
它首先检查移动是否已经处理,然后返回(It first checks to see if the move has already been handled and returns the) MoveHandler
实例(如果有).如果未处理举动并且可以处理此举,则(instance if it has. If the move is unhandled and it can handle the move, the) Result
变量,类型为(variable, which is of type) Move
,有(, has its) Index
属性设置为移动的索引,其(property set to the index of the move, its) MoveResult
属性设置为结果(property set to the resulting) GameState
和(and the) IsHandled bool
设定为(is set to) true
.该方法以返回的实例结束(. The method ends by returning the instance of the) MoveHandler
.的(. The) Result
调用链中的最后一个方法后,将返回变量的值.(variable’s value is returned after the last method in the chain has been called.)
public enum GameState
{
InPlay,
Xwin,
Owin,
Draw,
SearchCompleted//debugging
}
public struct Move
{
public int Index;
public GameState MoveResult;
}
使用助手类(Using Helper Classes)
通过使用助手类,链中的方法减少到几行代码.(The methods in the chain are reduced to a few lines of code by employing helper class.)
public MoveHandler HandleOWinOnNext()
{
if (IsHandled) return this;
if (gameScorer.BestScoreO == Constants.WinOnNextMove)
{
//O could win on its next move if the line is not blocked now
lineService.TryFindEmptySquare(gameScorer.BestLineO, out int index);
Result.Index = index;
IsHandled = true;
}
return this;
}
public MoveHandler HandleStrategicMove()
{
if (IsHandled) return this;
int index = gameScorer.GetBestImpactSquare();
Result.Index = index;
IsHandled = true;
return this;
}
public MoveHandler HandlePossibleFork()
{
if (IsHandled) return this;
if (lineService.TrySelectAntiForkSquare(board, out int index))
{
Result.Index = index;
IsHandled = true;
}
return this;
}
的(The) GameScorer
helper类更新空方块的影响值.(helper class updates the impact values of empty squares.)
private void UpdateImpactScores()
{
ResetImpactScores();
foreach (var line in lines)
{
if (!line.IsLineBlocked )
{
UpdateImpactScoresForLine(line);
}
}
}
private void UpdateImpactScoresForLine(Line line)
{
for (int i = 0; i < 3; i++)
{
if (line.Squares[i].IsEmpty)
{
ImpactScores[line.Squares[i].BoardIndex] += 1;
}
}
}
的(The) LineService
上课寻找潜在的叉子.(class looks for potential forks.)
public bool TrySelectAntiForkSquare(IBoard board, out int result)
{
int[,] cornerLines = board.CornerLines;
for (int i = 0; i < cornerLines.GetLength(0); i++)
{
if (board.Lines[cornerLines[i, 0]].OScore == 1
&& board.Lines[cornerLines[i, 1]].OScore == 1
&& board[cornerLines[i, 2]].Content != 'O')
{
return TryFindEmptySquare(board.Lines[cornerLines[i, 0]],out result);
}
}
result = -1;
return false;
}
的(The) cornerLines
变量是三列(variable is a three column) int
数组,第一和第二列包含组成角的两条线的索引号,第三列包含共享正方形的索引号.(array, the first and second columns contain the index numbers for the two lines that make up the corner and the third column has the index number of the shared square.)
内容更改事件(The Content Changed Event)
的(The) Square
班级提出一个(class raises a) SquareContentChangedEvent
当其内容更改时.的(when its contents change. The) Line
类使用事件更新其自身的属性.(class uses the event to update its own properties.)
public class Line
{
public Square[] Squares = new Square[3];
public int Ocount { get; private set; }
public int Xcount { get; private set; }
public int XScore { get; set; }
public int OScore { get; set; }
public bool IsLineOblocked => Xcount > 0;
public bool IsLineXblocked => Ocount > 0;
public bool IsLineBlocked => IsLineOblocked && IsLineXblocked;
public Line(Square c0, Square c1, Square c2)
{
Squares[0] = c0;
Squares[1] = c1;
Squares[2] = c2;
foreach (var square in Squares)
{
square.SquareContentChangedEvent += SquareChangedEventHandler;
}
Update();
}
private void SquareChangedEventHandler(object sender, System.EventArgs e)
{
Update();
}
public void Update()
{
Xcount = 0;
Ocount = 0;
foreach (var square in Squares)
{
if (square.Content == 'X') Xcount++;
if (square.Content == 'O') Ocount++;
}
XScore = IsLineXblocked ? 0 : Xcount ;
OScore = IsLineOblocked ? 0 : Ocount ;
}
}
游戏引擎(The Game Engine)
游戏在进行中(The game is progressed in the) Play
的方法(method of the) Game
类.(class.)
private Move Play()
{
inputOutputService.ShowBoard(board);
char firstPlayer = inputOutputService.GetIsYes(Constants.PromptGoFirst) ? 'O' : 'X';
char[] Players = firstPlayer == 'O' ? new char[] { 'O', 'X' } : new char[] { 'X', 'O' };
int moveNumber = 0;
Move move;
move.MoveResult = GameState.InPlay;
move.Index = -1;
while (move.MoveResult == GameState.InPlay)
{
char player = Players[moveNumber % 2];
move = player == 'X' ? MoveX(board) : MoveO();
board[move.Index].Content = player;
moveNumber++;
if (player == 'X')
{
inputOutputService.ShowBoard(board);
}
if (move.MoveResult == GameState.InPlay && moveHandler.IsGameADraw())
{
move.MoveResult = GameState.Draw;
}
}
inputOutputService.OutputGameResult(move, board);
return move;
}
只要(The game continues so long as the) GameState
的变量(variable of the) Move struct
每一步的值为时返回的值(that’s returned after every move has a value of) InPlay
.(.)
可靠测试(Infallibility Testing)
为使应用程序被认为是可靠的,AI必须能够为对手处理所有可能的移动顺序,(For the app to be considered infallible, the AI must be able to handle all the possible move sequences for its opponent,) PlayerO
.第一步有9种方法,而对于第一步,每一种都有7种方法进行第三步,((. There are 9 ways of making the first move and for each of the first moves, there are 7 ways of playing the third move, () playerO
是第二步),依此类推.一种(’s second move), and so on. A) 递归算法(recursive algorithm) 应该能够实现这种情况.(should be able to implement this scenario.)
private GameState PlayRecursiveMove(IBoard board, int depth, bool isPlayerO)
{
var unoccupiedSquares = board.GetUnOccupiedSquaresIndexes().ToList();
IBoard newBoard;
GameState result = GameState.InPlay;
if (isPlayerO)
{
for (int i = 0; i < unoccupiedSquares.Count; i++)
{
result = GameState.InPlay;
newBoard = board.Clone();
newBoard[unoccupiedSquares[i]].Content = 'O';
//debugging aid, stores move sequence
moves[depth] = unoccupiedSquares[i];
if (newBoard.Lines.Any((l) => l.OScore == Constants.WinningScore
&& result == GameState.InPlay))
{
inputOutputSerice.ShowBoard(newBoard);
OWinCount++;
totalMoves += unoccupiedSquares.Count + 1;
result = GameState.Owin;
}
if (newBoard.GetOccupiedSquaresCount() == Constants.TotalSquares
&& result == GameState.InPlay)
{
DrawCount++;
totalMoves += Constants.TotalSquares;
result = GameState.Draw;
}
if (result == GameState.InPlay)
{
result = PlayRecursiveMove(newBoard, depth + 1, false);
}
}
return GameState.SearchCompleted;
}
#region PlayerX
newBoard = board.Clone();
var move = MoveX(newBoard);
newBoard[move.Index].Content = 'X';
moves[depth] = move.Index;
if (newBoard.Lines.Any((l) => l.XScore == Constants.WinningScore))
{
XWinCount++;
totalMoves += unoccupiedSquares.Count + 1;
return GameState.Xwin;
}
if (newBoard.GetOccupiedSquaresCount() == Constants.TotalSquares)
{
totalMoves += Constants.TotalSquares;
DrawCount++;
return GameState.Draw;
}
return PlayRecursiveMove(newBoard, depth + 1, true);
#endregion
}
首先,该方法会遍历所有可用的空白方块的列表.它为(Firstly, the method iterates through a list of every empty square that’s available. It plays a move for) PlayerO
到迭代中的当前平方并检查结果.如果没有结果,则使用再次调用该方法.(to the current square in the iteration and checks for a result. If there is no result, the method is called again with the) IsplayerO bool
设置(set to) false
.这导致AI在递归中向下移动一个新级别.如果没有结果,则再次调用该方法,这一次是(. This results in the AI making its move at the next level down in the recursion. If there is no result, the method is called again, this time with) IsPlayerO
被设置为(being set to) true
并在新级别开始新的迭代.当在AI的移动中找到结果时,该方法将返回上一级,并选择迭代中的下一个平方作为移动(and a new iteration is started at the new level. When a result is found on the AI’s move, the method returns to the previous level and the next square in the iteration is selected as a move for) PlayerO
.同样,当在(. Similarly, when a result is found on) PlayerO
轮到了,选择了迭代中的下一个正方形.这一直持续到迭代完成并且方法返回上一级为止.除了将结果传递到上一级之外,AI不会对返回的结果进行任何处理.下一个升级是(’s turn, the next square in the iteration is selected. This continues until the iteration completes and the method returns to the previous level. The AI does nothing with the returned result other than to pass it up to the previous level. The next level up is) PlayerO
轮到该顺序,直到所有动作组合都用尽为止.结果如下:(’s turn and the sequence is repeated until all the combination of moves has been exhausted. Here are the results:)
X的总赢额(Total Wins For X) | 364(364) |
---|---|
O的总赢额(Total Wins For O) | 0 |
总抽奖(Total Draws) | 125 |
游戏总数(Total Games) | 489 |
总动作(Total Moves) | 2673 |
结论(Conclusion)
无需递归或存储动作的数据库,就可以玩非常棒的井字游戏.(It’s possible to play a very strong game of tic tac toe without the need for recursion or a database of stored moves.)
历史(History)
- 27(27)日(th)2019年1月:初始版本(January, 2019: Initial version)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
XML C# .NET Design VS2017 artificial-intelligence JSON 新闻 翻译