[Kings Table]

* HISTORY [#g1b6b202]
nimは、古くから(どれくらい前からかはよくわかりません)遊ばれている石取りゲームです。
おそらく中国が発祥だろうと考えられていますが、確かではありません。

類似のゲームも古来から、数多く存在しています。

マーチンガードナーの数学ゲームによると、1901年に、米国ハーバード大学の Charles L. Bouton
がゲームの分析を発表したときに、このゲームをnimと命名したのだそうです。この名は、Boutonが英語の古語のnim=取るの意味か、ドイツ語のnimmから取ったのではないかとガードナーは推察しています。

* DESCRIPTION [#e9e21b16]
** SETUP [#o33fcd05]
任意の数の石を、任意の列並べます。

** MOVE [#r65958ef]
任意の一つの列から、一つ以上好きなだけ石をとります。

パスはできません。

** GOAL [#o0a5a9bb]
二つのルールがあります。
+ 最後の石を取ったプレーヤーが勝ち (正型)
+ 最後の石を取ったプレーヤーが負け (逆型)

* STRATEGY [#ub2c7cae]
''正型''のnimと''逆型''のnimで、戦略上の難しさが異なります。

** 正型 [#k9932535]
正型のnimでの必勝手順は、それぞれの山を二のべき乗個にべき数重ならないように分類し、
すべての山について同じべき数を持つものの合計が、いずれも偶数個になるように石を取って
いきます。この状態を安定な状態と呼びます。

#ref(./nim_strategy.gif,60%)

自分の手番で安定状態を作れれば、勝ちのパターンに入っているわけです。

** 逆型 [#x363c88b]
とすると、逆型のnimはその反対の戦略をとればいいかと考えますが、実はそれほど簡単ではありません。
正型のnimの勝つ状態(手番で安定な状態にした)が負ける状態。負ける状態が勝つ状態に、必ずしも単純にはならないのです。

もし、どの山も一つの石しか持たなければ、正型の勝ち状態が負けの状態になります。しかし、
いずれかの山に二つ以上の石がある場合は、状態が逆転します。

そこで、逆型のnimに勝つための戦略を立てると
+ いずれかの山に二つ以上の石が残っているうちは、正型の時と同じ戦略でゲームを進め
+ すべての山が一つの石しかない状態になると、相手の手番に奇数個の山が残るように石を取ります ((正型のときは逆))

☆☆ ☆☆ ☆☆
//山の数が奇数であれば、手番のプレーヤーが勝ちになります。

戦略の詳細は、[[nimをプレーするコンピューター]]で記載します。

//戦略
//グランディー数
//証明?

// 正型と逆型の方が分かりやすいのでは?

* NOTE [#ib41bfdc]
nimのルールは単純ですが、奥深いゲームです。

数学的には、戦略と理論が完全に整理されていて、対等な二人ゼロ和完全情報で必ず決着のつく((引き分けのない))ゲームの典型としてあつかわれる重要なゲームでもあります。
必ず決着のつく対等な二人ゼロ和完全情報ゲームに分類されるものは、すべてnimと数学的に同等なことが確かめられています。

// nim系のゲームと言える特徴
// 二人零和 
// 完全情報  
// 着手対称  先手と後手の可能な着手が同じ(石や駒に色の区別がない)
// 着手収束  手数の上限が有限で、着手ごとに可能な着手の範囲が狭まる
// よって、与えられた局面からの着手に、先手・後手の区別がなく、帰納的な分析が可能

// nim系のゲームの分類
// 代数nim  局面を数列(各山の個数)で表現可能、着手条件が不等式(3個以下)
// 幾何nim  局面が盤面上の石の配置、着手条件が図形的(隣接して置けない、長方形に切り取る)
// 位相nim  局面が位相グラフ、着手条件が頂点の接続状況

* SEE ALSO [#c81848a1]
[[nimをプレーするコンピューター・プログラム]]

TOP   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS   [Privacy Policy]