高分求算法:关于井字棋(三子棋)的算法!!面谈感谢!!!
发布网友
发布时间：2022-04-24 14:56
共2个回答
热心网友
时间：2022-04-19 02:01
“井字棋”游戏（又叫“三子棋”），是一款十分经典的益智小游戏，想必很多玩家都有玩过。“井字棋”的棋盘很简单，是一个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过程用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。
以上几个问题就是该“井字棋”游戏实现的关键思路。....
QQ:744192659
邮箱:zhuwentao1996@live.cn
热心网友
时间：2022-04-19 03:19
井字棋最先来源于“牢棋”，牢棋就是囚犯下的棋。井字棋有时能决定两人不同的命运。中国版的不是走格，而是走点，围棋一样。而现代象棋并不在“棋经“内，宋朝之前的象棋没有这么多棋子，中国式井字棋升级后再形成象棋。现今象棋已脱离“牢棋”的范畴之内。
