NIM博弈
给定n堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以把一堆取光，但是不能不取。取走最后一件物品者获胜。两人都采用最优策略，问先手能不能获胜；
上面的博弈过程中，第一个行动的人称之为先手，第二个行动的人称之为后手，博弈的中间状态称为局面，而采用最优策略指的是，在当前面临的状态下选择某一步会使得在后续采用最优决策的情况下使得自己一定能够获胜的局面，否则一定失败；
那么如何判断在某一种状态下到底是先手获胜还是后手获胜呢？
显然从原问题到最终问题是一个循序渐进的过程，那么我们就可以从结果反推最初局面，这样我们就可以以子问题扩充到原问题，得到合理的规律；
这也可以称之为考虑博弈问题甚至许多其他问题的法宝，我们总是可以从逆向思考，避免问题无从下手；
简要分析
先说结论，对于A1xorA2xor…xorAn!=0的情况，先手必胜；
这可以用归纳假设来证明，对于A1xorA2xor…xorAn!=0的局面，我们假设A1xorA2xor…xorAn=v>0，那么我们总可以寻找到一堆石子Ai，使得Ai>v，那么我们从Ai中拿取一定量的石子使得Ai中的石子数变为Aixorv，那么此时A1xorA2xor…Aixorv…xorAn=0;此时后手操作后，所有物品异或值一定不等于零，这样先手又可以在下一个局面让所有物品的异或值等于0，依次类推知道最终物品为0；
现在我们反过来用归纳法证明该问题；
①当只有一堆物品时，此时A1!=0,此时先手必胜，结论成立；
②当有两堆物品时，同时A1xorA2=0，此时先手必败，因为后手总可以维持与先手一样的操作；
③当只有两堆物品时，同时A1xorA2!=0,此时先手可以取出物品较多的一堆物品中的物品，使得两堆物品数相等，这样问题转化为②，结论成立；
④假设当有k堆物品时结论成立；
⑤当有k+1堆物品时，此时A1xorA2xor…xorAk+1!=0，那么按照上面的分析，先手总可以下一个局面中所有物品的异或值等于0，我们只需要保证当某一刻物品堆数变成k堆时，如果剩余k堆物品的异或值不为0，则当前局面一定是后手在操作；否则为先手操作；
考虑到每个人每次只能操作一堆石子，而先手总可以使得剩余物品异或值为0，而如果某一个时刻k+1堆物品中，有k堆物品的异或值为0，那么此时一定是先手操作，这样先手可以将多出的一堆直接全部拿掉，这样先手一定可以获胜。结论成立；
如果某一时刻只剩余k堆物品，那么此时这k堆物品的异或值不为0，所以此时一定为先手操作，这样先手依然获胜，综上解决成立，同理可以证明k+1堆物品，同时异或值为0的情况；
当然以上证明看不明白也可以这样理解，由于操作过程中石子数目一定是不断减少的，而如果初始局面中所有元素的异或值不为0，那么它总可以使得下一局面的异或值为0，而异或值为0的局面如果还可以取物品，那么它不可能将所有物品一下子都去掉，那么局面又会转变成为所有元素异或值不为0的情况，知道不存在任何元素时，此时所有元素异或值为0，证明最后一步一定是先手操作的，那么命题的证；
问题抽象
任何公平组合游戏都可以抽象为有向图游戏，抽象过程其实与搜索时描述的搜索图结构是一致的，本质上这种游戏也是一种搜索，不过类似于A*算法的搜索算法，因为每一步搜索都是未来估价最优的状态下的选择。