ニム和
ニム和(にむわ、英: Nim sum)は、3山くずしゲーム(ニム)、色1種類の線分消去ゲームなどの2人交互型ゲームで必勝法を使う際に必要となる、0以上の整数m,nに対する、特別なルール付きの加算で、ニム和(m,n)と表記する[1]。ビットごとの排他的論理和とも呼ぶ。 ニム和(m,n)はm,nを2のべき乗の和で表したときの片方のみに出現する2のべき乗の合計である。 例えば、ニム和(6,12)=ニム和(2+4,4+8)=2+8=10である。2のべき乗である2と8は片方のみ、4は両方に出現している。 3個以上の整数のニム和の計算は結合則が成り立つので、結合順番を省略でき、ニム和(m,n,k)と書くことができる。 ニム和は交換則が成立し、さらにニム和の逆演算であるニム差(m,n)はニム和(m,n)と一致する。 3個以上の整数のニム和は、それぞれの整数を2のべき乗の和で表し、同じ2のべき乗が2個あれば必ず0に置き換えるという規則の加算となる。
ニム和 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
1 | 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 |
2 | 2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 |
3 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 |
4 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
5 | 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
6 | 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
7 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
ニム和計算を用いる必勝法
[編集]自分の番で打てる手のない人を負けとする標準型2人交互型ゲームでは、両者が最善の手を選択すれば、ニム和=0の局面をもらった本人の負け、相手の勝ちであり、ニム和>0の局面をもらった本人は勝ち、相手の負けである。理由はニム和=0の局面をもらった人はいかなる手を選択してもニム和>0の局面になり、ニム和>0の局面をもらった人は適切な手を選択すれば必ずニム和=0の局面にでき、終了局面はニム和=0だからである。
例 3山くずしゲームで、6個,12個,9個の山を持つ局面(6,12,9)では、ニム和(6,12,9)=ニム和(2+4,4+8,1+8)=1+2=3 > 0 なので、どれか1つの山を1以上減らしてニム和を0にすることができる。 ニム和(6,12,9)=1+2の最大の2のべき乗である2を持つ山6にニム和(6,12,9)をニム和加算すると、 ニム和(6,ニム和(6,12,9))=ニム和(2+4,1+2)=1+4=5 となる。 したがって局面(6,12,9)で、6個の山から1個減らして、局面(5,12,9)に移行すると、ニム和(5,12,9)=0となる。
ニム和表の作成方法
[編集]方法1 ビットごとの排他的論理和を用いる。整数を2進数表現に変換し、ビットごとの排他的論理和を計算する。
例 ニム和(6,12)の場合、十進数6は0110で、十進数12は1100で、これらのビットごとの排他的論理和は1010で、十進数10となる。
方法2 未使用最小整数を用いる。0以上の整数m,nに対し以下の関数Gを計算し、 ニム和(m,n)=G(m,n)とする。すなわちゲームの局面の値は、次のゲームの局面の値として未使用の0以上の最小の整数であるというグランディ値の定義を利用する。
- G(0,0)=0。
- 正のmについて、G(m,0)はG(m -1,0),...,G(0,0)に値として使われていない最小の0以上の整数。
- 正のnについて、G(0,n)はG(0,n -1),...,G(0,0)に値として使われていない最小の0以上の整数。
- 正のm,nについて、G(m,n)はG(m,n -1),...,G(m,0),G(m -1,n),...,G(0,n)に値として使われていない最小の0以上の整数。
例 G(1,0)はG(0,0)=0に値として使われていない最小の0以上の整数なので1。同様にG(0,1)は1。 G(1,1)はG(1,0)=1 と G(0,1)=1に値として使われていない最小の0以上の整数なので0。
方法3 以下のニム和表の再帰的構成法を用いる[2]。サイズの表は0以上以下の整数m,nに対するニム和(m,n)表の値部分のことである。サイズ1の表4枚でサイズ2の表が、サイズ2の表4枚でサイズ4の表が、サイズ4の表4枚でサイズ8の表ができる。
- サイズ1の表は 値0 である。
- サイズの表は4枚のサイズの表を次のように配置する。
(左上)サイズの表の値+0 (右上)サイズの表の値+
(左下)サイズの表の値+ (右下)サイズの表の値+0