我可以使用什么算法进行井字游戏来确定AI的"最佳动作"？

在一个井字游戏的实现中,我认为具有挑战性的部分是确定机器播放的最佳动作.

有哪些算法可以追求？我正在研究从简单到复杂的实现.我该如何处理这部分问题？

1> 小智..：

---

维基百科用于玩完美游戏(每次赢或平)的策略看起来像是简单的伪代码:

来自维基百科的引用(Tic Tac Toe#Strategy)

玩家可以玩一个完美的井字游戏(赢得或者至少是抽奖),如果他们选择以下列表中的第一个可用移动,每个回合,如Newell和Simon的1972 tic-tac-toe所使用的那样程序.[6]

胜利:如果你有两个连续,那就玩第三个连续三个.

阻挡:如果对手连续两次,则发挥第三个阻挡他们.

福克:创造一个可以通过两种方式获胜的机会.

Block Opponent's Fork:

选项1:连续创建两个以强制对手进行防守,只要它不会导致他们创建分叉或获胜.例如,如果"X"有一个角,"O"有中心,"X"也有相反的角,"O"不能为了赢得角落.(在这个场景中扮演角球会为"X"赢得一个分叉.)

选项2:如果存在对手可以分叉的配置,则阻止该分叉.

中心:玩中心.

对角:如果对手在角落,则对角球.

空角:玩空角落.

空荡荡的一面:空洞的一面.

认识到什么是"分叉"情况可以按照建议的蛮力方式进行.

注意:一个"完美"的对手是一个很好的练习,但最终不值得'玩'反对.但是,你可以改变上面的优先顺序,给对手的个性带来特征性的弱点.

---

所以你所说的是:唯一的胜利就是不打.

---

您如何建议实施该战略的分叉部分呢？

---

@Nick在这里没有任何有关如何找到反例的信息，“尝试一下”有点用处。这种策略是否可以达到一种配置，例如，跟随（6）而不是（7）会导致输球？在您的反例上发布更多信息将很有帮助。

2> Nick Johnson..：

---

你需要的东西(对于像Tss-tac-toe或像Chess这样更难的游戏)是minimax算法,或者它稍微复杂的变体,alpha-beta修剪.然而,普通的天真极小极大对于像tic-tac-toe这样小的搜索空间的游戏来说会很好.

简而言之,您想要做的不是为您寻找具有最佳结果的移动,而是寻找尽可能好的最坏结果的移动.如果你认为你的对手正在以最佳方式进行比赛,那么你必须假设他们会采取对你来说最糟糕的举动,因此你必须采取最小化其最大增益的举动.

---

@guidot Tic-tac-toe的搜索空间非常小,你的评价函数很简单:如果游戏是获胜状态,则为+ inf,如果是失败状态则为-inf,如果是平局则为0.

---

Minimax或alpha-beta肯定不是追求这种奇妙游戏的第一个想法(这限制了原始答案的价值).但是,如果你这样做(也许是想要进入更复杂的游戏,比如go-moku),你需要一个评估功能.这样的函数仅对给定的算法是敏感的,如果它产生任何中间位置的结果,则建议的(非常通用的)仅限于完成的游戏仅有助于选择最终的获胜消息.

---

相反,具有全有或全无评估功能的minimax或alpha-beta适用于您想要详尽搜索的任何游戏.Alpha-beta大大减少了搜索空间而非蛮力; minimax只是一种搜索游戏树并找到最佳可用移动的合理方式.

3> Adam Davis..：

---

生成每个可能的电路板的蛮力方法,并根据它后来在树下生成的电路板对其进行评分并不需要太多的内存,特别是一旦你认识到90度电路板旋转是多余的,就像在垂直方向上翻转一样,水平和对角轴.

一旦达到这一点,树形图中的数据就会少于1k来描述结果,因此是计算机的最佳移动.

-亚当

---

好吧,如果你想*真的*复杂...... ;-)蛮力方法可能比我懦弱的排名想法更好,虽然有点难以实现.

4> 小智..：

---

Tic-tac-toe的典型算法应如下所示:

Board:代表董事会的九元素向量.我们存储2(表示空白),3(表示X)或5(表示O).转弯:表示即将播放的游戏移动的整数.第一步将由1表示,最后由9表示.

算法

主算法使用三个函数.

Make2:如果电路板的中心方块为空,则返回5,即如果电路板[5] = 2.否则,此函数返回任何非角落方形(2,4,6或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为偶数,则将5设置为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.

我用过它.让我知道你们的感受.

5> billjamesdev..：

---

由于您只处理可能位置的3x3矩阵,因此只需编写一个搜索所有可能性而不会增加计算能力.对于每个开放空间,在标记该空间之后计算所有可能的结果(递归地,我会说),然后使用具有最多获胜可能性的移动.

实际上,优化这将是浪费精力.虽然一些简单的可能是:

首先检查其他团队可能获胜,阻止您找到的第一个团队(如果有2个游戏,则无论如何).

如果它处于打开状态(以前的规则没有候选人),请始终占据中心位置.

在两侧前角(再次,如果以前的规则是空的)

---

在人类层面,从P1开始的角落开始赢得更多.你的对手错误地认为,既然你没有占据中心,也许他们也不应该出于某种原因.