ニム和

ニム和について

ニム和（にむわ、英: Nim sum）は、特定の数の山や要素から成るゲームにおいて、必勝法を導くための数値です。この数値は、ビットごとの排他的論理和に基づいており、主に3山くずしゲームや色1種類の線分消去ゲームなど、2人のプレイヤーが交互に手を打つタイプのゲームで利用されます。ニム和は、2つの非負整数mおよびnについて、特別な加算ルールを用いて表されます。この計算方法は、ニム和(m, n)と表記され、2のべき乗の和を用います。

ニム和の計算

ニム和(m, n)は、mとnをそれぞれ2のべき乗の和で表した際、片方のみに現れる2のべき乗の合計として定義されます。例えば、ニム和(6, 12)を考える場合、6は2 + 4、12は4 + 8として表すことができます。この場合、ニム和(6, 12)は2 + 8 = 10となります。ここで、4は両方に含まれているため、計算に寄与しません。

3つ以上の整数のニム和も同様に計算でき、結合則が成り立つため、n個の整数についてもニム和を求めることができます。また、ニム和には交換則が成り立つため、任意の順序で計算しても結果は変わりません。さらに、逆演算であるニム差(m, n)は、ニム和(m, n)と同じ値になります。

勝敗におけるニム和の重要性

ニム和を用いた戦略は、特定のゲームの状況において勝敗を決定づけます。具体的には、ニム和が0である局面を選んだプレイヤーは、その局面から最善の手を選んでも常に負けてしまいます。一方、ニム和が0より大きい局面にいるプレイヤーは、適切な手を打つことで相手を0へと誘導することが可能です。

実例

例えば、6個、12個、9個の山から成る局面(6, 12, 9)では、ニム和(6, 12, 9)を計算すると、ニム和(6, 12, 9) = 1 + 2 = 3となります。ここで、3は0より大きいので、プレイヤーはどれか1つの山を減らすことでニム和を0にすることができます。実際には、山6から1つ減らして5にすることで、局面を(5, 12, 9)に変えることで、ニム和(5, 12, 9) = 0となります。

ニム和表の作成

ニム和を計算する方法はいくつかあります。

1. ビットごとの排他的論理和: 整数を2進数に変換し、ビット単位で排他的論理和を計算します。

2. 未使用最小整数法: ゲームの局面の値を未使用の整数として定義する方法です。この方法では、特定の条件に基づいて未使用の数を見つけます。

3. 再帰的構成法: サイズを拡張する形で表を構築していき、特定の値を導出します。これにより、数の規則性を利用した表現が可能です。

このように、ニム和はゲーム理論において重要な役割を果たしており、戦略の構築において不可欠なコンセプトです。

もう一度検索