详解Tic-Tac-Toe人工智能实现

Tic-Tac-Toe又称井字棋,即在3 x 3的棋盘上,双方轮流落子,先将3枚棋子连成一线的一方获得胜利。

Tic-Tac-Toe变化简单,只有765个可能局面,26830个棋局,因此常成为博弈论游戏树搜寻的教学例子,同时也是人工智能的一道好题目。

关于棋盘:

无标题 画图 2012 08 02 18 53 21 详解Tic Tac Toe人工智能实现

井字棋棋盘坐标版

整个棋盘可以连接出8条线无标题 画图 2012 08 02 19 12 42 详解Tic Tac Toe人工智能实现(如右图)—->

在中心的位置(2,2)有四条线穿过。

在所有棱位(1,2),(2,1),(2,3),(3,2),均有两条线穿过。

在所有角位(1,1),(1,3),(3,1),(3,3),均有三条线 

如何实现人工智能:

在下棋过程中,任何一方无非处于四种状态:

  1. 开局落子
  2. 第二步棋(先角原则)
  3. 垃圾时间

想要实现人工智能,让AI和人正常对弈,必须让AI理解这5种状态。

开局落子:

无标题 画图 2012 08 02 19 26 48 详解Tic Tac Toe人工智能实现

井字棋 AI先手

开局时,分为两种状况,一是AI先手,二是AI后手。AI先手时,毫无疑问,让AI落子在(2,2)位置(以X表示AI)。如图:

 

而当AI后手时,玩家可能落子情况有分为三种:

  1. 中心位置
  2. 棱位
  3. 角位

1、玩家落子在中心位置:

无标题 画图 2012 08 02 19 34 15 详解Tic Tac Toe人工智能实现

图1

此时,AI需要落子在角位。原因在于,如果落子在棱位,将出现如下必输的情形,示例如下,AI此时落子在(1,2)位置:玩家只需要在(3,1)或(3,3)位置落子,如图在(3,1),下一步则必须落子在(1,3),对手跟进落子在(1,1),

无标题 画图 2012 08 02 19 39 59 详解Tic Tac Toe人工智能实现

——则AI大势已去!

2、棱位  3、角位

这两种情形,AI指需要落子在(2,2)位置,便可保无虞,甚至反守为攻

第二步棋(先角原则):

无标题 画图 2012 08 02 19 12 42 详解Tic Tac Toe人工智能实现由上可知,当中心被玩家占据,需要避免上边提到的“必输的情形”跟进落子在角上,而非棱上。

而如果,自己占据中心,玩家落子在棱上,根据“必输情形”,此时也应该落在角上,而且如上图图1,应该落子在玩家棋子对面的角位上,此时“必输情形”将属于玩家。

 

攻:

任何己方两枚棋子连接在一起,且连线有空位时,落子在空位。

守:

任何玩家两枚棋子连接在一起,且连线有空位时,落子在空位。

垃圾时间:

由于棋盘大小限制,下棋过程中,很容易陷入双方均无法获胜的情况,此时,只需要找个空位随便落子即可。

特殊情况:

在以以上方式实现AI时,出现了一种比较特殊情况。即玩家先手,落子在角位以(1,1)为例,AI根据“开局落子”的原则3,落子在(2,2)。而玩家在第一步棋子位置(1,1)的对角(3,3)位置落子,

无标题 画图 2012 08 02 20 13 02 详解Tic Tac Toe人工智能实现

井字棋 特殊情况

依据“角先原则”,AI将落子在(1,3)或(3,1),对方将在(3,1)或(1,3)封堵AI,此时AI便已输了。无标题 画图 2012 08 02 20 14 49 详解Tic Tac Toe人工智能实现

所以,唯有此种情况不能执行“角先原则”。

代码实现:

其中,以二维数组t[3][3]表示棋盘,-1表示AI棋子X,1表示玩家棋子O,

dropPiece(Position p)方法表示落子,Position(int f ,int x,int y)表示棋盘位置,x,y表示坐标值,f取值范围为(-1或1)表示AI或者玩家。下面是AI主要代码:

 

 Tic-Tac-Toe-AI Jar文件

Tic-Tac-Toe-AI 源码

 

本文由 Baham 投稿于伯乐在线。也欢迎其他朋友投稿。提示:投稿的朋友,如果有新浪微博账号的话,记得标注一下哦 :-)

【如需转载,请标注并保留原文链接、译文链接和译者等信息,谢谢合作!】

 

收藏 4 评论

关于作者:Baham

Baham\'s Blog站长,Java初学者。With the Java platform,We can do anything.(新浪微博:@BahamBlog ) 个人主页 · 我的文章

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部