检测卡片游戏中计算机播放器中的循环

Question

前段时间我创建了一个小卡片游戏网页应用程序,以获得乐趣.播放器与电脑对战,大多数情况下都能正常工作.有时虽然电脑玩家进入了一个循环,但游戏的目的是失去你所有的牌,如果你没有一张牌可以玩,你就可以获得一堆牌.有时候电脑会播放x,y,z,拍桩,玩x,yz,拍桩等.

我跟踪我所做的动作,所以在任何时候我都有一个看起来像这样的数组:[C2,D5,H2,S4,C5,H2,S4,C5,H2,S4,C5 ]

在这种情况下,我可以看到我已经进入了玩H2,S4,C5的循环,然后进行了堆积然后重复.

那么,广义问题是,检测列表中重复模式的最佳方法是什么？我可能用一个简单的for循环来鞭打一些东西,试图找到我要玩的卡片,如果我在x位置找到那个,那么我可以检查x到n的模式是否在位置x-(nx)重复到x,但这似乎是一种可以有一个很好的算法的问题.鉴于以下函数签名,您将如何编写代码:

function findLoops(previousMoves, nextMove, maxPatternLength) {
    //Return [loopLength, loopCount] or null if there are no loops
}

ps这不是家庭作业,游戏存在,如果有人有兴趣,请访问http://www.idiot-cardgame.com :)

Answer 1

首先是一般性问题：您建议的方法

尝试找到我要打的牌，如果我在位置 x 找到该牌，那么我可以检查从 x 到 n 的模式是否在位置 x-(nx) 到 x 处重复，

看起来真的很好。我建议基本相同。它的时间复杂度为 O(n)，需要固定数量的存储，而且很简单：您还想要什么？

其次：如果您保留所有先前游戏状态的哈希表（完整状态，没有遗漏），则通常可以检查游戏中的重复情况。每次你到达一个新状态时，都会查找它是否在哈希表中，如果它在其中：你的游戏状态正在循环。

在 Javascript 中，你有内置的 hastables，所以使用类似的东西很容易做到这一点：

 new_state = next_move(old_state);
 new_encoded_state = encode(new_state);  // make it into a string
 if (allstates[new_encoded_state]) {
       // we are looping!
 } else {
       allstates[new_encoded_state] = 1;
       // no looping
 }

该变量allstates不是数组，而是对象类型。您可以使用字符串进行类似数组的访问，这将对象用作哈希表。