ニム和のソースを表示

'''ニム和'''（にむわ、[[英語|英]]: Nim sum）は、３山くずしゲーム（[[ニム]]）、色１種類の線分消去ゲームなどの２人交互型ゲームで必勝法を使う際に必要となる、0以上の整数''m'',''n''に対する、特別なルール付きの加算で、ニム和(''m'',''n'')と表記する<ref>Conway, J. H.; ''On numbers and games'', A. K. press, 2000.</ref>。ビットごとの[[排他的論理和]]とも呼ぶ。
ニム和(''m'',''n'')は''m'',''n''を２のべき乗の和で表したときの片方のみに出現する2のべき乗の合計である。
例えば、ニム和(6,12)=ニム和(2+4,4+8)=2+8=10である。2のべき乗である2と8は片方のみ、4は両方に出現している。
３個以上の整数のニム和の計算は結合則が成り立つので、結合順番を省略でき、ニム和(''m'',''n'',''k'')と書くことができる。
ニム和は交換則が成立し、さらにニム和の逆演算であるニム差(''m'',''n'')はニム和(''m'',''n'')と一致する。
3個以上の整数のニム和は、それぞれの整数を２のべき乗の和で表し、同じ2のべき乗が2個あれば必ず0に置き換えるという規則の加算となる。

{| class="wikitable"
|+ 0以上7以下のニム和表
! ニム和 !! 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
|}

==ニム和計算を用いる必勝法==
自分の番で打てる手のない人を負けとする標準型２人交互型ゲームでは、両者が最善の手を選択すれば、ニム和=0の局面をもらった本人の負け、相手の勝ちであり、ニム和＞0の局面をもらった本人は勝ち、相手の負けである。理由はニム和=0の局面をもらった人はいかなる手を選択してもニム和＞0の局面になり、ニム和＞0の局面をもらった人は適切な手を選択すれば必ずニム和=0の局面にでき、終了局面はニム和=0だからである。 

例　３山くずしゲームで、6個,12個,9個の山を持つ局面(6,12,9)では、ニム和(6,12,9)=ニム和(2+4,4+8,1+8)=1+2=3 > 0　なので、どれか１つの山を１以上減らしてニム和を0にすることができる。
ニム和(6,12,9)=1+2の最大の２のべき乗である2を持つ山6にニム和(6,12,9)をニム和加算すると、
ニム和(6,ニム和(6,12,9))=ニム和(2+4,1+2)=1+4=5　となる。
したがって局面(6,12,9)で、6個の山から１個減らして、局面(5,12,9)に移行すると、ニム和(5,12,9)=0となる。

==ニム和表の作成方法==

'''方法１'''　ビットごとの排他的論理和を用いる。整数を２進数表現に変換し、ビットごとの排他的論理和を計算する。

例　ニム和(6,12)の場合、十進数6は0110で、十進数12は1100で、これらのビットごとの排他的論理和は1010で、十進数10となる。

'''方法２'''　未使用最小整数を用いる。0以上の整数''m'',''n''に対し以下の関数''G''を計算し、
ニム和(''m'',''n'')=''G''(''m'',''n'')とする。すなわちゲームの局面の値は、次のゲームの局面の値として未使用の０以上の最小の整数であるというグランディ値の定義を利用する。 
*''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。 　　　

'''方法３'''　以下のニム和表の再帰的構成法を用いる<ref>徳田雄洋「必勝法の数学」岩波書店、2017年.</ref>。サイズ<math>2^k</math>の表は0以上<math>2^k-1</math>以下の整数''m'',''n''に対するニム和(''m'',''n'')表の値部分のことである。サイズ１の表４枚でサイズ２の表が、サイズ２の表４枚でサイズ４の表が、サイズ４の表４枚でサイズ８の表ができる。
*サイズ１の表は　値0　である。 
*サイズ<math>2^{k+1}</math>の表は４枚のサイズ<math>2^k</math>の表を次のように配置する。 

(左上)サイズ<math>2^k</math>の表の値+0　　(右上)サイズ<math>2^k</math>の表の値+<math>2^k</math> 

(左下)サイズ<math>2^k</math>の表の値+<math>2^k</math>　 (右下)サイズ<math>2^k</math>の表の値+0 

==出典==
{{Reflist}}

{{DEFAULTSORT:にむわ}}
[[Category:数学に関する記事]]
[[Category:数学の問題]]
[[Category:ゲーム理論]]
[[en:Nim-sum]]