ギャモンの伝言板や望月プロのブログでワンチェッカーバックギャモンが話題になっています。ルールはチェッカーの枚数が1枚ずつになる点以外は普通のギャモンと同じです。ジャコビールールが適用されるマネーゲームです。
さて、チェッカーが互いに1枚しかないので全局面における期待値をコンピュータを使ってゴリ押しで計算できるんじゃないかと考えました。ところがこれが以外に難しい。。ノーコンタクト(互いにすれ違った状態)の局面なら漸化的に計算できるのですが、コンタクトのある局面だと元の状態に戻り得るので漸化的に求められないのです。
よく考えてみると、このゲームは数学の題材として結構面白いです。こんな問題を作ってみました。
問題1:両者が如何なる戦略を取ったとしても、ムーブ数の総和を増やし続ければ、勝敗が未決着でいる確率は限りなく0に近づくことを示せ
問題2:ノーコンタクトの局面の期待値を求めるアルゴリズムを示せ
問題3:期待値を最大化する最適な戦略が唯一つ必ず存在することを示せ
問題4:全局面の期待値を求めるアルゴリズムを示せ(実時間で終了しなくても構わない)
問題5:全局面の期待値を実時間で求めるアルゴリズムを示せ
※戦略とは任意の局面に対してキューブアクションとチェッカープレイを規定した一連のリストを意味する。
いまのところ問題1,2がわかっていて、問題4はおそらく解けました。問題3は自明に思えますがちゃんと証明しようとすると以外に難しいです。問題5は実時間の定義があいまいですが一般的なPCで数時間で解ける程度ならいいです。問題5を解くことが最終ゴールですがこれ本当に難しいです。わかる人誰かいませんか?なおモンテカルロ法などで近似的に求めるのはなしとします。
|
| |||
XGID=a------------------------A:0:0:1:00:0:0:0:0:10 | ||||
![]() |
eXtreme Gammon Version: 2.10
さて、チェッカーが互いに1枚しかないので全局面における期待値をコンピュータを使ってゴリ押しで計算できるんじゃないかと考えました。ところがこれが以外に難しい。。ノーコンタクト(互いにすれ違った状態)の局面なら漸化的に計算できるのですが、コンタクトのある局面だと元の状態に戻り得るので漸化的に求められないのです。
よく考えてみると、このゲームは数学の題材として結構面白いです。こんな問題を作ってみました。
問題1:両者が如何なる戦略を取ったとしても、ムーブ数の総和を増やし続ければ、勝敗が未決着でいる確率は限りなく0に近づくことを示せ
問題2:ノーコンタクトの局面の期待値を求めるアルゴリズムを示せ
問題3:期待値を最大化する最適な戦略が唯一つ必ず存在することを示せ
問題4:全局面の期待値を求めるアルゴリズムを示せ(実時間で終了しなくても構わない)
問題5:全局面の期待値を実時間で求めるアルゴリズムを示せ
※戦略とは任意の局面に対してキューブアクションとチェッカープレイを規定した一連のリストを意味する。
いまのところ問題1,2がわかっていて、問題4はおそらく解けました。問題3は自明に思えますがちゃんと証明しようとすると以外に難しいです。問題5は実時間の定義があいまいですが一般的なPCで数時間で解ける程度ならいいです。問題5を解くことが最終ゴールですがこれ本当に難しいです。わかる人誰かいませんか?なおモンテカルロ法などで近似的に求めるのはなしとします。
※コメント投稿者のブログIDはブログ作成者のみに通知されます