我在CodeReview上发布了这个问题,但我开始意识到这不是一个Haskell问题,因为它是一个算法问题.
Haskell代码可以在我的github repo上找到,但我认为代码并不像一般概念那么重要.
基本上该程序计算出卡拉哈(瑞典变体)游戏中最佳的第一组动作.只考虑第一个"转弯",所以我们假设你开始并且没有计算从对手开始移动的任何东西.
Kalaha董事会http://www.graf-web.at/mwm/kalaha.jpg
董事会从空店开始,每个锅中都有相同数量的弹珠.
你开始轮到你选择一个非空的锅,从锅中取出所有的大理石,然后在通过锅时丢下一块大理石在板上移动.如果你的最后一块大理石落在商店里,你会再转一圈.如果你降落在一个非空的非商店锅里,你就拿起那个锅的所有内容然后继续.最后,如果你落在一个空锅中,转弯将传递给对手.
到目前为止,我已经通过挑选所有可能的路径解决了这个问题,然后根据商店中大理石的数量对它们进行排序.一条路径意味着从你的一个花盆开始,做所有必要的拾取和移动,看看你是在商店里还是在空锅里.如果你在商店降落,你可以继续,现在有很多新的分支,因为你身边有非空的花盆.
问题在于,如果你从花盆中的五个大理石开始,它已经是相当多的路径.跳到六,ghci内存耗尽.
我无法弄清楚如何降低成本的原因是因为我认为在计算过程中每条路径都是必需的.虽然我在生成的数千(或数百万)中只需要最多三条路径(最好的路径),但其余路径需要通过检查它们是否实际上比以前更好.
如果一个更长(通常更好)那么这是好的,但成本高.如果它比任何先前的路径短,那么程序仍然必须计算该路径才能找到它.
有没有办法解决这个问题,还是计算定义所需的所有路径？
我有一个Kalah求解器的工作实现,这是一个计算游戏第一回合最佳连续动作的应用程序.
我正在重新实现这个应用程序,虽然这次是一个测试套件和(希望)更漂亮的代码,它利用了更有趣的结构,如monoids或monad.
正如你在原始代码中看到的那样(或者不是,它是非常复杂的,这就是我重写它的原因)我已经定义了一个"移动",如下所示:
Pot我的董事会名单,以及我在董事会一侧的起始位置.Pot.[Pot]),我手里拿着多少个大理石,一个ADT表示我是否应该去另一圈(LapResult).问题是我怀疑如果我用一些聪明的数据结构表示我可以作为输入参数传递给一个函数并且具有相同的数据结构的板状态,我就不需要将一个移动分成几圈.作为回报值.至少这是我的猜测,我的想法是,董事会状态让我想起了我读过的关于幺半群的内容.
因此,如果我将一个"移动"定义为所有拾取弹珠直到你落入空锅或商店,是否有一些明显的方法来重写代码以便"移动"如何工作？
可以在此处找到重新实现的当前状态.