软件开发算法中的一些数学问题分享，ICG游戏

1，石子游戏

题目出处
https://leetcode-cn.com/problems/stone-game/
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
思路：常见的为动态规划算法，轮流去很容易想到递归，然后用动态规划优化，定义二维数组 dp，其行数和列数都等于石子的堆数，元素表示当石子堆的元素剩从i到j时，状态转移方程如下
dp[i][j]=max(piles[i]−dp[i+1][j],piles[j]−dp[i][j−1])

class Solution {
    public boolean stoneGame(int[] piles) {
        int length = piles.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] > 0;
    }}

另一种方法为数学思路
假设有 nnn 堆石子，nnn 是偶数，则每堆石子的下标从 000 到 n−1n-1n−1。根据下标将 nnn 堆石子分成两组，每组有 n2\frac{n}{2}2n 堆石子，下标为偶数的石子堆属于第一组，下标为奇数的石子堆属于第二组。
在此种状态下，作为先手的人可以选择自己拿奇数组还是偶数组（拿第一个还是最后一个），后手只能根据先手的选择来进行选择，无论后手怎么选择，他拿到的都是奇数组或者偶数组，即先手可以选择自己拿奇数组或者偶数组中较大的一组，则先手必赢

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }}

2，黑板异或游戏
https://leetcode-cn.com/problems/chalkboard-xor-game/
黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

思路
对于本题，给定的是判断「胜利」的规则（在给定序列的情况下，如果所有数值异或和为 000 可立即判断胜利，其他情况无法立即判断胜负），那么我们应该优先判断何为「先手必胜态」，如果不好分析，才考虑分析后手的「必败态」。

接下来是分情况讨论：

  1. 如果给定的序列异或和为 000，游戏开始时，先手直接获胜：

由此推导出性质一：给定序列 nums 的异或和为 000，先手处于「必胜态」，返回 True。
2. 如果给定序列异或和不为 000，我们需要分析，先手获胜的话，序列会满足何种性质：

显然如果要先手获胜，则需要满足「先手去掉一个数，剩余数值异或和必然不为 0；同时后手去掉一个数后，剩余数值异或和必然为 000」。

换句话说，我们需要分析什么情况下「经过一次后手操作」后，序列会以上述情况 1 的状态，回到先手的局面。

也就是反过来分析想要出现「后手必败态」，序列会有何种性质。

假设后手操作前的异或和为 Sum（Sum/0），「后手必败态」意味着去掉任意数字后异或和为 000。

同时根据「相同数值异或结果为 000」的特性，我们知道去掉某个数值，等价于在原有异或和的基础上异或上这个值。
则有：Sum′=Sum⊕nums[i]=0

由于是「后手必败态」，因此 iii 取任意一位，都满足上述式子。

则有：

Sum⊕nums[0]=…=Sum⊕nums[k]=…=Sum⊕nums[n−1]=0Sum ⊕ nums[0] = … = Sum ⊕ nums[k] = … = Sum ⊕ nums[n - 1] = 0 Sum⊕nums[0]=…=Sum⊕nums[k]=…=Sum⊕nums[n−1]=0

同时根据「任意数值与 0 异或数值不变」的特性，我们将每一项进行异或：

(Sum⊕nums[0])⊕…⊕(Sum⊕nums[k])⊕…⊕(Sum⊕nums[n−1])=0(Sum ⊕ nums[0]) ⊕ … ⊕ (Sum ⊕ nums[k]) ⊕ … ⊕ (Sum ⊕ nums[n - 1]) = 0 (Sum⊕nums[0])⊕…⊕(Sum⊕nums[k])⊕…⊕(Sum⊕nums[n−1])=0

根据交换律进行变换：

(Sum⊕Sum⊕…⊕Sum)⊕(nums[0]⊕…⊕nums[k]⊕…⊕nums[n−1])=0(Sum ⊕ Sum ⊕ … ⊕ Sum) ⊕ (nums[0] ⊕ … ⊕ nums[k] ⊕ … ⊕ nums[n - 1]) = 0 (Sum⊕Sum⊕…⊕Sum)⊕(nums[0]⊕…⊕nums[k]⊕…⊕nums[n−1])=0

再结合 SumSumSum 为原序列的异或和可得：

(Sum⊕Sum⊕…⊕Sum)⊕Sum=0,Sum≠0(Sum ⊕ Sum ⊕ … ⊕ Sum) ⊕ Sum = 0 , Sum \neq 0 (Sum⊕Sum⊕…⊕Sum)⊕Sum=0,Sum=0

至此，我们分析出当处于「后手必败态」时，去掉任意一个数值会满足上述式子。

根据「相同数值偶数次异或结果为 0」的特性，可推导出「后手必败态」会导致交回到先手的序列个数为偶数，由此推导后手操作前序列个数为奇数，后手操作前一个回合先手为偶数。

到这一步，我们推导出想要出现「后手必败态」，先手操作前的序列个数应当为偶数。

那么根据先手操作前序列个数为偶数（且异或和不为 0），是否能够推导出必然出现「后手必败态」呢？

显然是可以的，因为如果不出现「后手必败态」，会与我们前面分析过程矛盾。

假设先手操作前异或和为 XorXorXor（序列数量为偶数，同时 Xor≠0Xor \neq 0Xor=0），如果最终不出现「后手必败态」的话，也就是先手会输掉的话，那么意味着有 Xor⊕nums[i]=0Xor ⊕ nums[i] = 0Xor⊕nums[i]=0，其中 iii 为序列的任意位置。利用此性质，像上述分析那样，将每一项进行展开异或，会得到奇数个 XorXorXor 异或结果为 0，这与开始的 Xor!=0 矛盾。

由此推导出性质二：只需要保证先手操作前序列个数为偶数时就会出现「后手必败态」，从而确保先手必胜。

综上，如果序列 nums 本身异或和为 0，天然符合「先手必胜态」的条件，答案返回 True ；如果序列 nums 异或和不为 0，但序列长度为偶数，那么最终会出现「后手必败态」，推导出先手必胜，答案返回 True。
对于这两种题型的共同点为很容易想到dp，但是仔细想想会发现有点类似于井字棋，都存在先手必胜或必败的情况，具体描述引用如下，

百度搜索ICG博弈, ICG博弈是这类博弈的总括性理论. 这类博弈的核心特征在于, 只根据初始状态就可以判断双方的输赢情况
看对一些同学有帮助, 顺便把我自己的总结放在这里.
经典的Bash, Wythoff 以及Nim博弈问题, 都属于所谓的公平组合博弈(Impartial Combinatorial Games, ICG), ICG具有的的特征/性质如下(用局势(position)描述游戏中的一个状态):
两人参与, 轮流进行, 有限步内结束.
position空间只能划分为两个部分: 奇异局势(P-position)空间和非奇异局势(N-position)空间.
面对同一position, 两人具有相同的合法操作集合; 即选手的操作只与position有关而与选手无关.
对于任一P-position, 任意的合法操作都会使其变成N-position; 对于任一N-position至少存在一种合法操作使其变为P-position. (position空间的划分要满足此性质)
结束局势(E-position)定义为N-position空间中的一些, 面对它的选手赢; 或者定义为P-position空间中的一些, 面对它的选手输. (面对是指上一位选手操作完毕, 轮到当前选手, 而当前选手还未操作)
如果一个游戏满足上述性质, 即为ICG游戏. 那么由于P-position/N-position之间的这种转换关系(性质4), 我们就能, 只根据初始局势就可以判断双方的输赢情况. 通常判断先手是否赢, 先手赢的条件是初始局势为N-position.
启示: 面对一个博弈论(Game theory)问题, 我们可以大胆猜测它是一个ICG问题. 然后通过输赢关系找出一些N-position和P-position, 并尝试划分出各自的空间. 最后, 证明第4个性质. 当然在比赛中, 如果比较难证明, 我们可以直接通过提交代码来测试.

赞 (0)

相关推荐