我在Java中编写了一个井字游戏,我目前确定游戏结束的方法考虑了游戏结束的以下可能情况:
-
董事会已经满员,尚未宣布获胜者:比赛是平局 .
-
克罗斯赢了 .
-
Circle赢了 .
不幸的是,为了这样做,它从表中读取预定义的一组这些场景 . 考虑到电路板上只有9个空格,这并不一定是坏的,因此表格有点小,但有没有更好的算法来确定游戏是否结束?确定某人是否赢了是问题的关键,因为检查9个空格是否已满是微不足道的 .
表方法可能是解决方案,但如果没有,那是什么?如果董事会的规模不大 n=9
怎么办?如果它是一个更大的董事会,比如 n=16
, n=25
等等,会导致连续放置的项目数量为 x=4
, x=5
等?一个用于所有 n = { 9, 16, 25, 36 ... }
的通用算法?
21 回答
您知道获胜的移动只能在X或O进行最近移动后才会发生,因此您只能使用该移动中包含的可选诊断来搜索行/列,以在尝试确定获胜棋盘时限制搜索空间 . 此外,由于在最后一次移动中,如果它不是获胜移动,则在抽签的Tic-tac-toe游戏中存在固定数量的移动它默认为抽奖游戏 .
编辑:此代码用于n个n板,连续n个赢(3x3板请求连续3个,等等)
编辑:添加代码来检查反诊断,我无法找出一个非循环方式来确定该点是否在反诊断上,这就是为什么该步骤丢失
你可以使用魔方http://mathworld.wolfram.com/MagicSquare.html如果任何行,列或诊断加起来15,那么玩家就赢了 .
这类似于Osama ALASSIRY's answer,但它为线性空间和恒定时间交换恒定空间和线性时间 . 也就是说,初始化后没有循环 .
为每行,每列和两个对角线(对角线和反对角线)初始化一对
(0,0)
. 这些对表示相应行,列或对角线中的块的累积(sum,sum)
,其中当玩家放置一块时,更新相应的行对,列对和对角线对(如果在对角线上) . 如果任何新更新的行,列或对角线对等于
(n,0)
或(0,n)
,则A或B分别获胜 .渐近分析:
对于内存使用,使用
4*(n+1)
整数 .练习:你能看到如何在O(1)时间内进行抽签测试吗?如果是这样,你可以在平局的早期结束比赛 .
这个伪代码怎么样:
玩家在位置(x,y)放下一块后:
我将使用char [n,n]数组,其中O,X和空格为空 .
简单 .
一个循环 .
五个简单变量:4个整数和一个布尔值 .
缩放到任意大小的n .
仅检查当前件 .
没有魔法 . :)
以下是我为javascript中正在编写的项目编写的解决方案 . 如果你不介意几个阵列的内存成本,它可能是你会发现的最快,最简单的解决方案 . 它假设您知道最后一步的位置 .
我刚刚为我的C编程课写了这个 .
我发布它是因为这里没有任何其他示例可以使用任何大小的矩形网格,并且任何数字 N -in-a-row连续标记都可以获胜 .
你会在
checkWinner()
函数中找到我的算法,例如它 . 它不会让我自己说话 .如果电路板是n×n,则有n行,n列和2个对角线 . 检查所有X -763650_的每一个以找到胜利者 .
如果它只需要x <n个连续的正方形来赢,那就更复杂了 . 最明显的解决方案是检查每个x×x平方以获得胜利者 . 这里有一些代码可以证明这一点 .
(我实际上并没有测试过这个咳嗽,但它确实在第一次尝试时编译,对我来说!)
我不太了解Java,但我知道C,所以我尝试了adk's magic square idea(以及Hardwareguy's search restriction) .
它编译和测试很好 .
这很有趣,谢谢!
实际上,考虑到它,你不需要一个魔方,只需要每行/列/对角线的计数 . 这比将一个魔方广义化为
n
×n
矩阵要容易一些,因为你只需要数到n
.在我的一次采访中,我被问到了同样的问题 . 我的想法:用0初始化矩阵 . 保持3个数组1)sum_row(大小n)2)sum_column(大小n)3)对角线(大小2)
对于每次移动,通过(X)将框值减1并且对于每次移动减去(0)将其递增1.在任何点,如果在当前移动中已经修改的行/列/对角线具有-3或3的总和意味着有人赢了比赛 . 我们可以使用抽奖以上方法保持moveCount变量 .
你觉得我错过了什么吗?
编辑:相同可用于nxn矩阵 . 总和应该是3或-3 .
一种非循环方式来确定该点是否在反诊断上:
我在行,列,对角线检查中做了一些优化 . 如果我们需要检查特定的列或对角线,它主要在第一个嵌套循环中决定 . 因此,我们避免检查列或对角线,以节省时间 . 当电路板尺寸更大且未填充大量电池时,这会产生很大的影响 .
这是java代码 .
我迟到了,但是我想指出我发现使用magic square的一个好处,即它可以用来获得对下一回合会导致输赢的方块的引用,而不仅仅是用于计算游戏何时结束 .
拿这个神奇的方块:
首先,设置一个
scores
数组,每次移动时该数组都会递增 . 有关详细信息,请参阅this answer . 现在如果我们在[0,0]和[0,1]连续两次非法播放X,那么scores
数组看起来像这样:董事会看起来像这样:
然后,我们要做的就是获取对哪个方块获胜/阻止的引用是:
实际上,实现需要一些额外的技巧,比如处理数字键(在JavaScript中),但我发现它非常简单并且享受休闲数学 .
我喜欢这个算法,因为它使用了1x9和3x3的电路板表示 .
另一种选择:使用代码生成表 . 达到对称性,只有三种获胜方式:边缘行,中间行或对角线 . 拿这三个并尽可能地围绕它们旋转:
这些对称性可以在你的游戏代码中有更多的用途:如果你已经看到了旋转版本的板子,你可以直接获取缓存值或缓存最佳移动(并将其撤回) . 这通常比评估游戏子树快得多 .
(向左和向右翻转可以帮助相同的方式;这里不需要它,因为获胜模式的旋转集是镜像对称的 . )
这是我提出的解决方案,它将符号存储为字符并使用char的int值来确定X或O是否已赢(查看裁判的代码)
此外,我的单元测试验证它确实有效
完整解决方案:https://github.com/nashjain/tictactoe/tree/master/java
9个插槽的后续方法怎么样?为3x3矩阵(a1,a2 ...... a9)声明9个整数变量,其中a1,a2,a3代表行-1,a1,a4,a7将形成第1列(你明白了) . 使用“1”表示Player-1,使用“2”表示Player-2 .
有8种可能的胜利组合:Win-1:a1 a2 a3(根据哪位玩家获胜,答案可能是3或6)Win-2:a4 a5 a6 Win-3:a7 a8 a9 Win-4:a1 a4 a7 .. ..赢-7:a1 a5 a9赢-8:a3 a5 a7
现在我们知道,如果玩家1越过a1,那么我们需要重新评估3个变量的总和:Win-1,Win-4和Win-7 . 无论哪个'赢 - ?'变量达到3或6首先赢得比赛 . 如果Win-1变量首先达到6,则Player-2获胜 .
我确实理解这个解决方案不容易扩展 .
恒定时间O(8),平均4个短AND . 玩家=短号码 . 需要额外的检查以确保移动有效 .
这是一种非常简单的检查方法 .
}
如果你有考试的寄宿家庭5 * 5,我使用下一个检查方法:
我认为,它更清楚,但可能不是最佳方式 .
这是我使用二维数组的解决方案:
我曾经为此开发了一种算法作为科学项目的一部分 .
你基本上递归地将棋盘划分为一堆重叠的2x2 rects,测试不同的可能组合,以便在2x2的方格上获胜 .
它很慢,但它具有在任何尺寸的电路板上工作的优势,具有相当线性的存储器要求 .
我希望我能找到我的实施