井字游戏规则算法
井字游戏
EE-551 Python 项⽬
客观的:
这个 EE-551 项⽬旨在使⽤ python 开发⼀个 Tic Tac Toe 游戏。它主要包括开发和实现⼀个计算机程序,该程序可以与另⼀个玩家玩Tic Tac Toe。
为了了解什么是井字游戏以及如何玩游戏,以下是说明。
游戏说明:
Tic Tac Toe 是⼀种两⼈游戏(其中⼀个由计算机或⼈类玩)。在这个游戏中,有⼀个 3 x 3 ⽅格的棋盘。
两名玩家轮流在 3x3 棋盘上打分。Tic Tac Toe 游戏的⽬标是成为在 3 x 3 ⽹格上⽔平、垂直或对⾓线获得三个相同符号的玩家之⼀。最先获得 3 个他/她的符号(标记)的玩家 - 垂直、⽔平或对⾓线赢得游戏,另⼀个玩家输掉游戏。游戏可以由两个玩家玩。玩家有两种选择:(a) ⼈类 (b) 计算机
游戏规则:
玩家可以与对⼿在两个符号之间进⾏选择,通常的游戏使⽤“X”和“O”。
1. 先上场的玩家将获得“X”标记(我们称他/她的玩家为 1),第⼆位上场的玩家将获得“O”标记(我们称他/她为玩家 2)。
2. 玩家 1 和 2 轮流⾛棋,玩家 1 玩标记“X”,玩家 2 玩标记“O”。
3. 玩家⽤他的标记(“X”或“O”)标记任何 3x3 ⽅格,他们的⽬标是创建⼀条⽔平、垂直或对⾓线的直线,有两个意图:
a. ⼀名玩家连续获得三个他/她的分数(垂直、⽔平或对⾓线),即该玩家赢得游戏。
湾 如果没有⼈可以⽤⾃⼰的标记创建⼀条直线,并且棋盘上的所有位置都被占⽤,则游戏以平局/平局结束。
实施计划:
本项⽬的实施⼯作流程如下:
为了可视化定义的游戏规则和描述,游戏如下图所⽰。
⾸先,游戏将从空棋盘开始。笑红尘歌词
然后玩家 1 将通过在该板上打标记“X”来移动。然后玩家 2 将通过在该板上打标记“O”来移动。这将继续下去,直到棋盘上满是分数。然后程序将检查是“X”的玩家 1 获胜还是“O”的玩家 2 获胜,并且该场景将如下:(可以是垂直、⽔平或对⾓线)。
如果没有玩家获胜,程序将检查平局。
曾晖所有这些决策都是通过使⽤ Minimax 算法完成的。
极⼤极⼩算法
Minimax 是⼀种应⽤于两⼈ Tic Tac Toe 游戏的⼈⼯智能算法。这种游戏被称为零和游戏,因为在数学表⽰中:⼀个玩家赢(+1),另⼀个玩家输(-1)或两个⼈都输(0)。
Minimax 是⼀种递归算法,⽤于选择导致 Max 玩家赢或不输(平局)的最佳移动。它考虑游戏的当前状态和该状态下的可⽤移动,然后对于它播放的每个有效移动(交替最⼩和最⼤),直到到最终状态 - 赢、平或输。
它的⽬标是最⼩化最⼤损失,即最⼩化最坏情况。
举例说明
为了应⽤这⼀点,让我们举⼀个游戏快结束时的例⼦,轮到我了。我是 X。显然,我在这⾥的⽬标是最⼤化我的最终游戏得分。
如果这张图⽚的顶部代表轮到我时的游戏状态,那么我有⼀些选择,我可以玩三个地⽅,其中⼀个明显导致我获胜并获得 10 分。如果我不这样做,O 很容易获胜。⽽且我不希望 O 赢,所以我在这⾥的⽬标,作为第⼀个球员,应该是选择最⼤的得分动作。
高考结束的祝福语但是O呢?
我们应该假设 O 也在玩赢得这场⽐赛,但相对于我们,第⼀个玩家,O 想要选择给我们带来最差分数的移动,它想要选择⼀个可以最⼩化我们最终的移动分数。让我们从 O 的⾓度来看事情,从上⾯的另外两个游戏状态开始,我们不会⽴即获胜。
选择很明确,O 会选择任何导致得分为 -10 的动作。
描述极⼩极⼤
Minimax 算法的关键是两个玩家之间的来回,其中“轮到它”的玩家希望选择得分最⾼的移动。反过来,每个可⽤移动的分数由对⽅玩家决定其可⽤移动中的哪个具有最低分数来确定。对⼿玩家移动的分数再次由试图最⼤化其分数的轮流玩家决定,依此类推,⼀直到移动树到结束状态。
算法的描述,假设 X 是轮到玩家:
如果游戏结束,从 X 的⾓度返回分数。
否则,获取每个可能移动的新游戏状态列表。党员个人自我评价
创建分数列表。
对于这些状态中的每⼀个,将该状态的极⼩极⼤结果添加到分数列表中。
如果轮到 X,则返回分数列表中的最⾼分数。
如果轮到 O,则返回分数列表中的最低分数。
让我们⽤完整的⾛法树来看看算法的执⾏过程,并从算法上看,如何选择即时获胜的⾛法:
轮到 X 进⼊状态 1。X ⽣成状态 2、3 和 4,并在这些状态上调⽤ minimax。
状态 2 将 +10 的分数推送到状态 1 的分数列表,因为游戏处于结束状态。开学一周
状态 3 和 4 不在结束状态,因此 3 ⽣成状态 5 和 6 并对其调⽤ minimax,⽽状态 4 ⽣成状态 7 和 8 并对其调⽤ minimax。
状态 5 将 -10 的分数推送到状态 3 的分数列表,⽽状态 7 也会发⽣同样的情况,将 -10 的分数推送到状态 4 的分数列表。
状态 6 和 8 ⽣成唯⼀可⽤的移动,即结束状态,因此它们都将 +10 的分数添加到状态 3 和 4 的移动列表中。
因为在状态 3 和状态 4 中轮到 O,所以 O 将寻求到最⼩分数,并且在 -10 和 +10 之间进⾏选择时,状态 3 和 4 都将产⽣ -10。
最后,状态 2、3 和 4 的得分列表分别⽤ +10、-10 和 -10 填充,寻求最⼤化得分的状态 1 将选择得分为 +10 的获胜棋步,状态2。
让我们通过查看可能的移动树来看看这⾥发⽣了什么:
给定棋盘状态 1,其中两个玩家都玩得很完美,⽽ O 是计算机玩家。O 在状态 5 中选择了移动,然后当 X 在状态 9 中获胜时⽴即失败。
但是如果 O 像状态 3 那样阻⽌ X 的胜利,那么 X 显然会阻⽌ O 的潜在胜利,如状态 7 所⽰。
如状态 10 和 11 所⽰,这为 X 带来了两次确定的胜利,因此⽆论 O 在状态 7 中选择哪⼀步,X 最终都会获胜。
该算法的另⼀个重要因素是深度。
该算法的关键改进是考虑到游戏结束的“深度”或回合数,⽆论棋盘安排如何,完美的玩家都会完美地玩。基本上完美的球员应该完美地打球,但尽可能地延长⽐赛时间。
所以每次我们调⽤ minimax 时,深度都会增加 1,当最终计算结束游戏状态时,分数会根据深度进⾏调整。
广东第二师范学院怎么样由于这是⼀个⾮常复杂的算法,我们有⼀台计算机来执⾏这个算法。
代码实施
为了运⾏此代码,需要安装 pygame 库。要安装它,请打开命令提⽰符并键⼊“pip install pygame”。
运⾏完整代码 TicTacToeGame.ipynb。
运⾏代码后,屏幕上将显⽰以下窗⼝(空板):
游戏包含两个按钮 - vs Human 和 vs AI,以便我们可以选择我们的对⼿。⼀旦我们点击按钮,通过点击游戏板开始玩游戏。由于我们先玩,我们将被定义为玩家 X。
游戏结束后,游戏屏幕上将显⽰获胜者姓名(X 或 O)或抽奖游戏的消息。
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论