ヘックス入門

読んだ本の感想。

半沢英一著。2013年3月20日 第1刷発行。



第1章 ウールワース
ウールワースは以下のように、上8枡、下6枡の二段の棒状の枡目で行う。




①二人のプレイヤーが先手◎、後手〇を動かす
②各プレイヤーは、上下二段の内、一個だけを動かせる
③〇は右方向に、◎は左方向に任意の空き枡だけ動かせる
④パスや相手の丸を飛び越える事は出来ない
⑤動かす丸が無くなったプレイヤーの負け

このゲームは先手必勝で、◎が左に二枡移動すれば良い。その胆は対称戦略で、相手に等間隔の対称形を渡す。左に二枡◎が移動すると、上下二段の〇と◎の感覚が等しくなり、〇のプレイヤーは対称を崩さなければ丸を移動出来ないため、◎のプレイヤーが対称を維持するように駒を動かし続ければ勝利が確定する。

<ウールワースの必勝戦略>
上下二段の間隔が等しくない時は先手必勝。上下の間隔が等しい形で相手に渡し続ければ良い。

第2章 ニム
三山崩しと呼ばれる。基本的にはウールワースと同じ。コインやマッチ棒等で三つの山を作り、以下のように行う。

①二人のプレイヤーで行う
②各プレイヤーは、交互に山から一個以上の数だけ石を取る
③石を取る山は、毎回いずれかの一山
④パスは許されず、最後の石を取ったプレイヤーの勝利

ニムも、各山の石の数を同数にして渡したプレイヤーが勝利する。

<二進分解>
二進法に直す直前の二進数の和への分解を二進分解と呼ぶ。

ニムで考えると、三つの山の石の数を二進分解した時に、三つの山の石の数を合計して二進数が偶数個出現する場合は二進対称と呼ばれ、一つでも奇数個の山があれば二進非対称と呼ばれる。

例:
三つの山に含まれる石の数が(9、3、10)の場合9 = 2の三乗 + 2の0乗、3 = 2の一乗 + 2の0乗、10 = 2の三乗 + 2の一乗であり、二進数が偶数個(2の三乗、2の一乗、2の0乗が各二個)出現するため二進対称である。

仮に山の数が二つであった場合、二進対称である事と、二進数の数が同数でなければ二進展開にならない。

<ブートンの定理>
ニムの負け形は二進対称、勝ち形は二進非対称であり、必勝戦略は二進対称形にして相手に渡す事を続ける事。

例:
三つの山の石の数が(11、7、13)である場合、二進数が2の三乗、2の二乗、2の一乗が各二個あるが、2の0乗が三個あるために二進非対称。

そのため、先手が2の0乗 = 1を三つの山のどれかから取れば、先手の必勝形が完成する。

第3章 ツェルメロの定理
ヘックスは、二人でプレイし、ゲームの情報が完全に与えられる2人完全情報ゲームというだけでなく、有限の選択肢、有限回の着手で決着する特徴を持つ(有限ゲーム)。

ツェルメロの定理では、全ての有限ゲームには先手必勝法があるか、後手必勝法があるか、引き分けに終わるかのどれかである。

言い換えると、任意の自然数nについて、全ての手数nまでのゲームには先手必勝法があるか、後手必勝法があるか、引き分けに終わるかのどれかである。

その考えでは、ニムは三つの山の石の数をnとした「手数nまでのゲーム」になり、ヘックスは六角形の枡の数をnとした「手数nまでのゲーム」になる。

<帰納法による証明>
①n = 0の場合
手数0のゲームは既に決着が付いているゲームであり、命題は成立している。

②n = k で成立していれば、n = k + 1でも成立する
手数がk + 1までのゲームとは、手数がkまでのゲームに一手足したもの。n = kのゲームに必勝法があれば、一手足したゲームにも必勝法がある。

第4章 ヘックス
正六角形の枡目を菱形に並べた盤で行われる。盤の大きさは任意に変更可能であり、以下のルールで行われる。

①二人のプレイヤーが黒石(先手)と白石(後手)を交互に置く
②黒石で左上辺と右下辺を結ばれれば黒の勝ち
③白石で右上辺と左下辺を結ばれれば白の勝ち
④菱形の頂点をなす四つの枡は黒白双方の辺につながる

ヘックスは1942年にデンマークの数学者ピート・ハインによって考案され、1949年にジョン・ナッシュによっても再提起されナッシュのゲームとも呼ばれる。ジョン・ナッシュはヘックスに先手必勝形がある事を証明した。

<ヘックスの証明>
以下を証明する。

①ヘックスには引分けが無い
②ヘックスには後手必勝法が無い

ヘックスに引分けが無いとは、以下である事。

(1)一方がつながれば他方はつながらない
(2)枡が全て埋まれば必ず一方はつながっている

ヘックスに後手必勝法が無いとためには、相手を真似る戦略について理解する必要がある。それには以下の条件が必要。

(1)ゲームが対称性を持つ
(2)先手・後手の形の相違が真似る事に影響しない

ヘックスに後手必勝法があった場合、先手は後手必勝法を真似る戦略を取れる。それでは先手が勝利してしまい、後手必勝法と矛盾する。上記の相手を真似る戦略が可能である事から、ヘックスに後手必勝法は無い事になる。

ただし、対称性を壊した非対称のヘックスは後手必勝に出来る(本書内では5×6の歪んだ菱形を図にしている)。それは非対称ウールワースの対称戦略に似ている。ヘックス盤を左右に分けて、左右対称になるように、枡目に同じ番号を付けておき、先手が置いたのと同じ番号に後手が石を置いておけば勝てる。

厳密な証明は良く分からなかった。

人気ブログランキングへ
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

ABCDEFG

Author:ABCDEFG
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード