作者：lvyanbo | 来源：互联网 | 2023-02-11 09:58
题目:有一种NM或者最后者输的博弈游戏，其玩法如下：开始有9枚硬币，两人轮流取出1，2或3枚，取出最后一枚者为输，使用搜索树证明后起步者总能取胜。我知道后起步者只要保存
题目:有一种N/M或者"最后者输"的博弈游戏，其玩法如下：开始有9枚硬币，两人轮流取出1，2或3枚，取出最后一枚者为
输，使用
搜索树证明后起步者总能取胜。
我知道后起步者只要保存4+4+1就能搞定对手了,可是我无法用
搜索树证明。人工智能书上有个
九宫格的博弈问题的搜索例题,不过我发现我解决这题不能用那些格子棋的算法，所以请大家帮帮我。
4 个解决方案
就是把那个branching factor为3的树全部展开，然后用min-max原理一个一个算必胜必败。
是NIM问题么?一般可以用dp来解。
LZ给出的，似乎用mod 4就可以了！这里问题的资料网上挺多的，LZ可以搜索一下！
兄弟们要像我学习，做个文明的回答者。
什么branching factor,min-max我也知道，全不展开说的容易，动笔画下看看怎么样。
总不可能把
S0
S1 S2 S3
这样一直分支下去把，要证明出来啊，所以来点规范的，继续努力！
用三叉树吧，根为9，然后，第一层为8，7，6，这样构造下去。在构造过程中
1，对于奇数层，也就是先拿的一方，看这层的三个分支A，B，C，对于A，若为1 ，置FLAG_A为FALSE，若不为1 ，继续向下构造，对于A，B，C这三个分支，用同样的方法可以找到FLAG_A,FLAG_B,FLAG_C,对这三个分支求交返回
2，对于偶数层，也就是后拿的一方，设这层的分支也有A，B，C，对于A，若为1，置FLAG_A为TRUE,若不为1，继续向下构造，对于A，B，C这三个分支，用同样的方法可以找到FALG_A,FLAG_B,FALG_C，对这三个求并返回
最后返回的若是TRUE,则证明后拿的必能取胜
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 