数当てゲームMOOの最小質問戦略と最強戦略
数当てゲーム MOO の固定戦略のうち質問回数の平均を最小にする戦略(最小
質問戦略)を完全探索(exhaustive search)によって求めました. これに関して
は, 第3回ゲームプログラミングシンポジウム(1996/9/20-22, 箱根)で発表しました．
MOO は, Hit & Blow, Cow & Bull などさまざまな名で呼ばれ, 親しまれて
きた数当てゲームです. ゲームのルールは以下のようになっています.
- 2人の対戦者が互いに異なる数字からなる4桁の数(以下MOO数という)を
紙に書いて, 両方の見えないところにしまっておく. "0586"のように最初の
桁に0が来ても良い.
- 対戦者は相手の書いた数を当てるために, 交互に質問としてMOO数を
提示する. 質問に対して出題した側は紙に書いたMOO数とのbull (場所も数字
も同じもの)，cow(数字は同じだが場所が異なるもの)の数を答える. 2つのMOO
数からbull, cowの数を計算する操作を以下ではMOO積という. 相手の書いた
MOO数を当てると4 bullとなる.
- 4 bullとなるまでの，質問回数が少い方が勝ちとなる. 質問回数が等し
い場合には引き分けとなる.
このゲームを固定戦略に基づいてプレイするプログラムのうちで, 質問回数
の平均が最小となる戦略と, 固定戦略の中で最強の戦略を完全探索を用いて求
めました.
その際,
- 高速化に適したデータ構造の採用
- 対称な質問の排除
- 前処理により良い推測関数を求める
といったテクニックを用いました.
MOO数の集合が与えられた際, 総質問数の下限を見積もるための探索プログラ
ムは, estimate.c (集合中に10種類の数字が出
現する場合)と, estimate_n.c (それ以外の
場合)となっています.
最小質問戦略を求めるプログラムは find_sol.c
です. 最小質問戦略による総質問回数(5040通りのすべての入力に対する)は
26274なので，平均質問回数は5.213となります．これ以前に報告された最良の
戦略では総質問回数は26347(平均質問回数 5.226)なので，数値の改善は少し
ですが，これより小さい戦略が存在しないことが証明されたことに意義があります．
このプログラムを用いて得た最小質問戦略は
こちらにあります. 最小質問戦略を用いたMOOプレイプログラムをJAVAで書い
たものをこちらに置きます. ソースは
moo.java , mootable.java
の2つです．
最小質問戦略に対する勝率を最大にする固定戦略を求めるプログラムは, こちらです. これで得られた戦略は最小質問
戦略とは異なっていますが, 固定戦略の中では最強の戦略(この戦略に対して勝
率0.5を超える戦略はない)になっています. この最強戦略は
こちら にあります.
find_sol.c ,
find_sol_next.c に共通に使われるヘッダファイル hit.h は こちら にあります．
