我可以使用哪些算法用于井字棋游戏，以确定＆QUOT;最好的移动和QUOT;对于AI？ [英] What algorithm for a tic-tac-toe game can I use to determine the "best move" for the AI?

问题描述

在一个井字棋实现我猜测，挑战性的部分是确定最佳的举措由机器来播放。

什么是可以追求的算法？我寻找到实现从简单到复杂。我如何去解决这个问题的一部分？

解决方案

从维基百科打一场完美的比赛（赢或扎每次）的战略似乎是简单的伪code：

  

报价从维基百科（井字＃战略）

     

一个播放器可以播放井字棋的一场完美的比赛（赢或至少，画出），如果他们选择从下面的列表中，每回合第一个可用的举动，如在纽厄尔和西蒙的1972年tic-使用TAC-toe程序。[6]

     

  

1. WIN：如果你有两连胜，打第三拿到三连胜

  

2. 块：如果对手有两连胜，打第三阻止他们。

  

3. 叉：创建一个机会，在这里，你可以赢得在两个方面

  

4. 阻止对手的叉：

        

   选项1：在一排强制创建两个   对手进入卫冕，只要   因为它不会导致他们创建   叉子或获奖。例如，如果X的   设有一个角落，O有中心，   X则有相反的角落里为好，   O绝不能为了打一个角落   赢得。 （打在这个角落   场景创建一个叉的X   赢。）

        

   选项2：如果有一个配置   那里的对手可以派生，块   该叉。

  

5. 中心：游戏中心

  

6. 对面的角落：如果对手是在角落里，起到相反的   角落。

  

7. 空角：玩一个空的角落

  

8. 空方：玩空方

  

认识什么是叉的情况看起来可能会在一个强力的方式来完成的建议。

注意：一个完美的对手是一个很好的锻炼，但最终不值得玩对抗。你可以，但是，改变优先级上面给出的特性弱点的对手的个性。

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:

Quote from Wikipedia (Tic Tac Toe#Strategy)

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. Win: If you have two in a row, play the third to get three in a row.

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

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

4. Block Opponent's Fork:

   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.)

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

5. Center: Play the center.

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

7. Empty Corner: Play an empty corner.

8. Empty Side: Play an empty side.

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

Note: A "perfect" opponent is a nice exercise but ultimately not worth 'playing' against. You could, however, alter the priorities above to give characteristic weaknesses to opponent personalities.

这篇关于我可以使用哪些算法用于井字棋游戏，以确定＆QUOT;最好的移动和QUOT;对于AI？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！