内容导航:
什么意思?
“井字棋”游戏(又叫“三子棋”),是一款十分经典的益智小游戏,想必很多玩家都有玩过。“井字棋”的棋盘很简单,是一个3×3的格子,很像中国文字中的“井”字,所以得名“井字棋”。“井字棋”游戏的规则与“五子棋”十分类似,“五子棋”的规则是一方首先五子连成一线就胜利;“井字棋”是一方首先三子连成一线就胜利。
井字棋(英文名Tic-Tac-Toe)
井字棋的出现年代估计已不可考,西方人认为这是由古罗马人发明的;但我们中国人认为,既然咱们都发明了围棋、五子棋,那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了,暂且不提。
想起小时候上课喜欢玩井字棋,只要一张草稿纸、一支笔、同桌两人就可以玩了。上体育课,也可以拿着树枝在沙坑里玩。但一直感觉这游戏太简单了,后来接触了五子棋,着迷了一阵,但水平总是很差,便也不玩了。
一字棋游戏极小极大分析法
设有九个空格,由MAX,MIN二人对弈,轮到谁走棋谁就往空格上放一只自己的棋子,谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子),谁就取得了胜利。
用叉号表示MAX,用圆圈代表MIN。
比如右图中就是MIN取胜的棋局。
为了不致于生成太大的博弈树,假设每次仅扩展两层。估价函数定义如下:
设棋局为P,估价函数为e(P)。
(1) 若P对任何一方来说都不是获胜的位置,则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)
(2) 若P是MAX必胜的棋局,则e(P)=+∞。
(3) 若P是B必胜的棋局,则e(P)=-∞。
比如P如右图示,则e(P)=6-4=2
要注意利用棋盘位置的对称性,在生成后继节点的位置时,下列博弈结局
都是相同的棋局(在博弈中,一宇棋的分枝系数比较小起初是由于对称性,而后是由于棋盘上未布子的空格减少所致)。图3.15画出了经过两层搜索生成的博弈树,静态估值记在端节点下面,倒推值记在圆圈内。
由于右图所示位置具有最大的倒推值,它应当选取为MAX的第一步(正好是MAX的最好的优先走步)。
现在我们假设MAX走了这一步,而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋,他一定没有采用好的搜索策略)。下一步,MAX又在新的格局下搜索两层,产生如图3.16所示的搜索图。
现在图中MAX有两个可能“最好的”优先走步,假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步,从而产生如下棋局:MAX再次搜索,产生如图3.17所示的树。
在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜,因此它们的估值为—∞。当这些估值被倒推回去时,可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在,MIN可以看出MAX必然在他的下一走步中获胜,因此,MIN只好认输。
按极大极小算法编程下一字棋的演示(右图,可以点击操作)...
我们就利用Visual Basic编写一个“井字棋”的小游戏。
【设计思路】
首先,我们要知道,“井字棋”游戏是一款典型的棋类游戏,游戏时一方式是电脑,另一方是玩家。所以,这类游戏在开始时有两种方式:一种是玩家先走;另一种是电脑先走。这是我们要考虑的第一个问题。
其次,由于与玩家对战的是计算机,所以我们要编写一个过程(Chuqi),它可以使程序模拟人的思维与人下棋(其实就是“人工智能”的体现),这个Chuqi过程也是本游戏软件的关键。此外,我们还要编写两个过程(Lianxian和Shuying),Lianxian过程用来时刻判断棋盘中是否有三个棋子连成一线;Shuying过程用来判断如果有三个棋子连成一线,是哪一方连成一线的,即判断哪一方获胜。
以上几个问题就是该“井字棋”游戏实现的关键思路。....
http://family.chinaok.com/2005-12/15745.htm
井字棋可能是最简单的棋类游戏了,它简单到了成年人之间玩几乎总是平局的地步。因此,这个游戏貌似最多只能哄哄小孩子。不过,对井字棋游戏中所有可能的情况进行一番细致的分析,你会发现一个你或许不会料到的惊人结论——先手的最优策略不是稳坐正中央,而是先占一个角! 几年前,曾经自己动手写过一个和人下井字棋的电脑程序,运行之后却发现电脑先走时总爱把第一步棋下在角上;检查程序代码许久后才意识到,电脑程序可能并没有问题。人们往往有一个定势思维,认为由于从正中央出发能够得到的连线最多,因此最优策略必然是先占住正中央这块宝地。然而,经验是一回事,实际上就是另一回事了——这个电脑程序看似很没头脑地往角里下棋,但几乎总是在赢。 无独有偶,国外著名的 Geek 漫画 xkcd 最近画了一幅井字棋最优策略完全图,同样给出了这个违反直觉的结论:第一步走在角上才是最佳的策略。 这究竟是为什么呢?不妨让我们看一看,如果第一步真的走角,会发生哪些情况。 先手先占角! 游戏开始后,二话不说先占上一个角(比如左下角吧),那么对方总共有五种本质不同的应对策略:占据靠近你的那条边,占据靠近你的那个角,占据远离你的那条边,占据远离你的那个角(即对角),以及占据正中央的位置。不可思议的是,在这五种策略中,前面四种都是陷阱——如果对方不慎选择了前面四种策略中的任意一种,他就必然输掉。 上图显示了在这四种情况下你可以如何把对方一步步逼上绝路。假设对方走正下方,占据了一个靠近你的边(最左边的那个图),你就可以占据正中央来应对,逼迫对方不得不走右上角。这时,只需要在左上角放下一子,你就赢定了——图中出现了两条只差一子的连线,对方不可能兼顾得了。 右边几个图显示了对方第一步棋的其它几种走法。选择合适的位置应对他,都可以在下一步迫使对方只剩一种走法,接下来你便可以下出“一箭双雕”的棋,让对方无法彻底封s你。 也就是说,当你占据棋盘一角后,在对方下一步棋的八个可选位置中,其中七个位置都是必输的,陷阱摆满了几乎整个棋盘。在面对“先走一角”的诡异开局时,你的朋友说不准就会慌了手脚,没能冷静地占住中间,决定了必败的命运。 对方要是真的走了正中间,你仍然有赢的机会。你可以占住右上角的位置(如上图)。如果对方不幸走了剩下的两个角中的一个(上图左),你便能故技重施,再次取得胜利。只有对方选择了边上的位置(上图右),才能躲过这一系列的陷阱,最终变成平局。 难怪计算机会把角上的位置当作宝地呢。 后手还是先占角! 作为后行者,你遇到的往往是“先走中间”的经典开局。此时,千万别忘了,先占角仍然是一条金科玉律。如果你不慎走了某条边的位置,对方可就赢定了!对方可以向上面的第一幅图那样,在正右方下子应对,逼迫你把下一步棋落在正左方。此时,对方便可占据右上方的位置,同时产生出两条仅差一子的连线。右边三幅图则显示,如果你在角上应对,最终总会是一盘和棋。
井字棋,英文名叫Tic-Tac-Toe,是一种在3*3格子上进行的连珠游戏,和五子棋比较类似,由于棋盘一般不画边框,格线排成井字故得名。游戏需要的工具仅为纸和笔,然后由分别代表O和X的两个游戏者轮流在格子里留下标记(一般来说先手者为X)井字策略,英文名叫Tic Tactics,一个经典的重生!Tic Tactics是一个回合制多人游戏,简单易学,但具挑战性!如果你知道怎么玩井字棋,你已经知道怎么玩Tic Tactics。不同的是你才是决定每一步把你的对手送到哪里的关键。你会为战略的纵深大吃一惊!挑战朋友或者陌生人来提升你的等级,并最终成为Tic Tactics军师!(详细玩法井字棋吧置顶贴有介绍)
简单来说,定义数据结构(比如棋盘数组,棋盘格子以及棋子,双方玩家等相关的数据结构表示),定义规则(比如同一个位置不能放两颗棋子,三颗棋子连线放胜利)。
具体取决于需求,比如图形表示和AI(人工智能)等等。如果你只是想要简单的用命令行和文字输出表示,那么编写一个控制台应用程序就可以。如果需要图形等控制,需要借助一些图形以及UI库等。但是这些外部表示可以跟核心数据结构和规则,算法等分离开来。所以刚开始先用文字表示写出核心代码,后续可以逐渐加上UI图形,AI等。
这里面貌似没什么啊,首先是进行初始化
void inarrdata(chess a) //初始化棋盘编号
{
a[1]='1';a[2]='2';a[3]='3';
a[4]='4';a[5]='5';a[6]='6';
a[7]='7';a[8]='8';a[9]='9';
}
以下是查找一个位置,因为之前inarrdata函数里对数组进行了初始化
要注意的是'1'-48=1
'2'-48=2
int arrfull() //判断还有没有下棋的位置
{
int i;
int arrf=0;
for(i=1;i<=9;i++)
if(i==arr[i]-48) //如果字符arr[i]-48等于i
arrf=1; //那么arrf=1,也就是可以走棋
return arrf;
}
另外程序中还没有进行下棋的算法判定的代码~~