组合游戏和博弈论

本文主要是介绍组合游戏和博弈论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Nim游戏和SG值

给定一个有向无环图和一个起始顶点上的一枚棋子，Alice和Bob交替的将这枚棋子沿有向边进行移动，无法移动者判负。问是否有必胜策略。

首先定义 \(\text{mex}\) 运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如 \(\text{mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0}\)。

对于一个给定的有向无环图，定义关于图的每个顶点的 \(\text{SG}\) 函数 \(\text{sg}\) 如下：\(\text{sg(x)=mex{ sg(y) | y是x的后继 }}\)。也就是说，一个点的 \(\text{SG}\) 函数为在它所有后继中都未出现的最小的值。

通过 \(\text{sg}\) 函数，我们可以把所有 \(\text{ICG}\) 游戏转换成 \(\text{Nim}\) 游戏，后手必胜当且仅当 \(\text{sg}\) 的异或和为 \(\text{0}\) 。

过程

1. 把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。

即：

2. 分别考虑没一个子游戏，计算其 \(\text{SG}\) 值。

\(\text{SG}\) 值的计算方法：（重点）

• 可选步数为 \(1\)~\(\text{m}\) 的连续整数，直接取模即可，\(\text{SG(x)=x%(m+1)}\);

• 可选步数为任意步，\(\text{SG(x) = x}\);

• 可选步数为一系列不连续的数，用模板计算。

这篇关于组合游戏和博弈论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！