Tic-Tac-Toe之最强的对手

megablue

最近突然有开发游戏的动力所以特地去寻找了一点AI相关的资讯。电脑其实是很“笨”的工具，电脑没有了软件连一部黑白电视都不如。那么为何我们平时玩的游戏，电脑角色看起来是那么的聪明，甚至会自行做出决定呢？

其实它们不是聪明，只是设计者有耐心，它们拥有不是人类的“智慧”，不会像人类那样思考。

他们有的只是预设的行为(predefined behaviors)。

if A happens do something
if B happens do something
if C happens do something

再复杂一些的游戏甚至在游戏引擎里加入了剧本系统，让关卡设计者在不需要改动游戏引擎的代码的情况下可以改变游戏的内容。设计师没预设，它就什么都做不了了。又或者说设计师预设错了，即使是叫它去送死，它也会义无反顾，眼睛都不眨一下（除非你叫它眨）立刻去死。

以上的种种，都有赖于游戏或关卡设计者去定义电脑的每一个决定。就以tic-tac-toe 来说，3x3的九宫格你的确可以预设每一步对电脑最有利的决定。

就以下面的九宫格为例，

1. 1 2 3
   
2. 4 5 6
   
3. 7 8 9

复制代码

123, 456, 789, 147, 258, 369, 159, 357.
这几个组合都是胜利的条件，只要一方填满后，他就是赢家。

稍微有点脑的玩家都知道，tic-tac-toe这游戏，开局很重要，也是胜负的关键。人类可以凭经验知道如何在开局争取最大的胜利条件。但对与电脑来说每一局都是全新的开始，它没有所谓的“经验”。所以这个时候就要靠你，伟大的游戏设计师去给予电脑所需要的“经验”。

if is MYTURN AND round = 0 AND slot[5] is empty, fills slot[5]
if is MYTURN AND round > 0 AND slot[5] is MYSLOT AND slot[1] is EMPTY,  fills slot[1]
if is MYTURN AND round > 0 AND slot[5] is MYSLOT AND AND slot[1] is MYSLOT AND slot[9] is EMPTY,  fills slot[9]
...以此类推

你预设的每个条件都是决定电脑胜负的关键...只有9格的标准tic tac toe, 只要有点耐心，要把所有的关键步预设不难。

可是...如果规则同样是对3格，换成是是4x4的呢？（好吧，可能你的耐性真的比一般人强），那5x5，6x6？你要如何预设呢？
即使是只剩一步就可以胜利，如果你没预设这一步... 它也不会去补上。

Game Tree
这时候，我们就不能只靠预设的步伐了，至少要这游戏里给予电脑有更宽阔的思考能力。可是...要如何达到这一点呢？那就得靠神奇的Minimax（其实不神奇，了解后其实不外乎是look-ahead + heuristic eliminations)。

首先不得不提一提在游戏人工智能里扮演着相当重要角色的Game Tree。Game Tree, 也称作 Decision Tree - 顾名思义-决策的分歧点，也就是“决策树” 。
某个科幻电影曾经说过，我们每做出一个决定，宇宙就会分裂出一个平行世界，在哪，我们就会做出另一个决定。而Game Tree就是呈现这个概念最好的工具了， Game Tree 通过棋盘的现状演算出游戏里所有可能的可能性，让电脑可以窥视所有的平行“未来”， 从而选择对头最有利的下一步棋。

就以下面的tic-tac-toe布局来说，

gamedev gametree

x有3个格可选 ---> 选择后延伸出2个o可选的格 ---> 然后再延伸出X可选的最后一格。

下面这组代码就是gametree的最基本运作了。 它是通过recursive function 一直延伸直至有人胜利或和局出现。

1. void gametree(boolean turn, int[] board){
   
2.                 int status = getBoardStatus(board);
   
3.                 int newmove = (turn == COMTURN) ? COMSLOT : HUMANSLOT;
   
4.                 int slot = EMPTYSLOT;
   
5.                                                 
   
6.                 //if the board has winner, draw or no longer has possible branch
   
7.                 if(status != INPROGRESS){
   
8.                         return;
   
9.                 }
   
10.                
    
11.                 for(int i = 0; i < board.length; i++){
    
12.                         slot = board[i];
    
13. 
    
14.                         //if move is possible
    
15.                         if(slot == EMPTYSLOT){
    
16.                                 int[] newBoard = board.clone();
    
17.                                 newBoard[i] = newmove;
    
18.                                 gametree(!turn, newBoard);
    
19.                         }
    
20.                 }
    
21.         }
    

复制代码

以上的代码及解释纯属让大家对GameTree有比较清晰的概念，还未加入如何让电脑从gametree中选出最有利的选择。


PART 2
TO BE CONTINUED....

megablue

PART 2 保留

megablue

PART 3 保留

flashang

可以把优先的位置放入 array

然后在内部先下一子，做判定。

而构想中的 （没有做） 应该是这样：


1. 保留目前的棋盘

2.

1. 
   
2. for ( i=0; i < 目前可以下的 n 步; i++ ) {
   
3.         电脑 下一步
   
4. 
   
5.         换边
   
6.         for ( j=0; j < 目前可以下的 m 步; j++ ) {
   
7.                 下一步，做判定胜负优势
   
8.         }
   
9. }
   

复制代码

这样子做接下来几步的判定。


3. 根据众多的 2 结果，选出最优的。

richie86

Tic Tac Toe 有 formula的
1) Check if any solving move (致胜的走法)
2) Block opponent wining move (阻止对方致胜)
3) Check if any fork move (寻找可以制造2个致胜的Move,比如1,9,3...3,7,9...etc)通常是角落的
4) Block opponent fork move, 阻止对方制造Fork
5) 选中间(5)
6) 选对方对面的Corner
7) 选空的Corner
8) 选空的其他

1-8走,哪一个可以走就走, 你只有2个结局
1) 赢
2) 和局
永远不会输

看Wiki的
A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table[3].
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.

megablue

richie86 发表于 29-3-2013 09:13 AM
Tic Tac Toe 有 formula的
1) Check if any solving move (致胜的走法)
2) Block opponent wining move ( ...

理论上所有的两个人的deterministic games都是solvable 的，无论游戏有多复杂，只要双方都是无限聪敏，然后100%无错误（也就是所谓的perfect play) 都有“不败之道”。可是我这篇文章不是教大家如何solve tic-tac-toe （相信这里的诸位都能达到perfect play)...  tic-tac-toe 只是用于做示范，因为它够简单，game tree 也不必画到傻 当游戏更复杂的时候(如Chess, 象棋), 就没有你所谓的方程式了， 只有看双方的策略了。

anyhow, 你贴的资料对没入门者来说是很不错的，至少他们可以先往这个方向开始写游戏。

richie86

是的, 到现在我都很佩服以前玩Nitendo的象棋AI,那个algorithm就不懂怎么写了, 可能也是一个类似流程的
1) 寻找将军方式(结束游戏)
2) 寻找反将军方式
3) 寻找攻入方法
4) 寻找阻挡方法
5) etc etc
每个流程都用score 方式判断哪一个是最好的选择, 比如让AI可以放弃炮,换对方车等等...

PS..我才发现LZ是鼎鼎大名的megablue... blueserver!!!

flashang

我试试看用其他比较简单的游戏来解释。

http://baike.baidu.com/view/24242.htm
黑白棋，又叫反棋 （反/翻 转棋）（Reversi）、奥赛罗棋（Othello）

8 x 8 的棋盘，总共 64 - 4 步，

最简易的 AI，用优先下法

就是优先下 4 个角头，A1, H1, A8, H8
然后是 边 C1 - F1， A3 - A6， H3 - H6， C8 - F8
然后是其他步，最差的 8 个位置是 B1， G1， A2， A7， H2， H7， B8， G8


而一般的判定是

1. 电脑搜寻可以下的各种可能步，
2. 测试每一个可能
3. 判定结果，选出最佳的那一步

而更高明的算法是：
1. 电脑搜寻可以下的各种可能步，
2. 测试每一个可能
3. 电脑搜寻 对手 可以下的各种可能步，
4. 测试每一个可能
5. 判定结果，选出最佳的那一步

当然，如果 1 -- 4 可以算更多回合，那么 5 的结果就更好。

平凡魔术师

tic tac toe应该算是低级别的AI, 我很佩服那些写象棋，西洋象棋的，一般来说应该要有一个象棋高手在旁边一起编织游戏吧

megablue

平凡魔术师 发表于 30-3-2013 10:24 AM
tic tac toe应该算是低级别的AI, 我很佩服那些写象棋，西洋象棋的，一般来说应该要有一个象棋高手在旁边一起 ...

一理通，万理彻。
Tic Tac Toe 的AI和中西象棋的AI本质上是一样, 你甚至可以直接用我接下来要介绍的minimax 演算法在你自己写的中/西象棋里。当然，单单靠minimax 演算法是不足以战胜大师级的棋手，还要配合上许多技巧甚至是预设的棋谱。

megablue

richie86 发表于 29-3-2013 11:33 AM
是的, 到现在我都很佩服以前玩Nitendo的象棋AI,那个algorithm就不懂怎么写了, 可能也是一个类似流程的
1)  ...

Famicom/NES? 有老人跟小孩那个？那个的确很厉害下，当是的CPU只有1.6Mhz   RAM只有2048bytes... 代码要非常优化才能实现象棋AI.

megablue

flashang 发表于 29-3-2013 11:43 PM
我试试看用其他比较简单的游戏来解释。

http://baike.baidu.com/view/24242.htm

优先下法就是所谓的棋谱、dictionary。从技术角度来看，好像有点cheating的感觉了 。感觉上就是一面下棋一面在翻棋谱。

megablue

richie86 发表于 29-3-2013 11:33 AM
是的, 到现在我都很佩服以前玩Nitendo的象棋AI,那个algorithm就不懂怎么写了, 可能也是一个类似流程的
1)  ...

的确，我刚才的回复也有提到。

P/S: 谢谢你的支持咯

flashang

megablue 发表于 30-3-2013 01:48 PM
优先下法就是所谓的棋谱、dictionary。从技术角度来看，好像有点cheating的感觉了 。感觉上就是一面 ...

棋谱是许多人经过多次的计算，认证，而记录下比较有效的步骤。

在 AI 的考虑中，
也可以用 “算法” 把最好的几种结果储存起来，变成优先算法，也就是棋谱。

比如说，象棋里面第一步 兵五进一 或者 帅五进一，除非遇到初学者，不然包输，
这个电脑计算几步后发现结果不好，就被排除掉。

而其他的通用步法，例如开始几步，通过计算结果比较有效的，
就直接储存下来，以后就不必每一次都计算。