我可以使用什么算法来确定井字棋游戏的“最佳移动"?为了人工智能? [英] What algorithm for a tic-tac-toe game can I use to determine the "best move" for the AI?

问题描述

在井字游戏的实现中，我想最具挑战性的部分是确定机器要走的最佳动作.

In a tic-tac-toe implementation I guess that the challenging part is to determine the best move to be played by the machine.

可以追求的算法有哪些?我正在研究从简单到复杂的实现.我将如何着手解决这部分问题?

What are the algorithms that can pursued? I'm looking into implementations from simple to complex. How would I go about tackling this part of the problem?

推荐答案

维基百科中玩完美游戏(每次赢或平)的策略似乎是简单的伪代码:

The strategy from Wikipedia for playing a perfect game (win or tie every time) seems like straightforward pseudo-code:

引自 维基百科(井字游戏#Strategy)

如果玩家在每一回合中从以下列表中选择第一个可用的移动，就可以玩出完美的井字游戏(赢得或至少平局)，正如 Newell 和 Simon 1972 年的井字游戏所使用的那样tac-toe 程序.[6]

A player can play a perfect game of Tic-tac-toe (to win or, at least, draw) if they choose the first available move from the following list, each turn, as used in Newell and Simon's 1972 tic-tac-toe program.[6]

1. 赢:如果您连续打两个，则打第三个以获得连续三个.

1. Win: If you have two in a row, play the third to get three in a row.

阻挡:如果对手连续有两个，打第三个来阻挡他们.

Block: If the opponent has two in a row, play the third to block them.

分叉:创造机会，您可以通过两种方式获胜.

Fork: Create an opportunity where you can win in two ways.

阻止对手的叉子:

方案一:连续创建两个强制对手进入防守状态，只要因为它不会导致他们创造叉子或胜利.例如，如果X"有一个角，O"有中心，和X"也有对角，O"不得打角球赢.(在这个打角场景为X"创建一个叉子赢了.)

Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)

选项2:如果有配置对手可以分叉、阻挡的地方那个叉子.

Option 2: If there is a configuration where the opponent can fork, block that fork.

中心:播放中心.

Opposite Corner:如果对手在底角，则反打角落.

Opposite Corner: If the opponent is in the corner, play the opposite corner.

空角:打空角.

Empty Side:发挥空的一面.

Empty Side: Play an empty side.

可以按照建议的蛮力方式识别分叉"情况.

Recognizing what a "fork" situation looks like could be done in a brute-force manner as suggested.

注意:完美"的对手是一个很好的练习，但最终不值得对抗".但是，您可以更改上述优先级，以赋予对手个性特征.

这篇关于我可以使用什么算法来确定井字棋游戏的“最佳移动"?为了人工智能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！