jyanjayakaの日記

はやめのリリース、しょっちゅうリリース

Numeron（数当てゲーム）最強アルゴリズム

Numeron（数当て）アルゴリズム

ゲームの分析

ゲームの分析を通して、適切な用語や記号を導入する。

 

ゲームのルール

Numeronというゲームについての説明はここ。ゲームのルールは次の通り：*1

  • それぞれのプレイヤーが、0-9までの数字が書かれた10枚のカードのうち3枚を使って、3桁の番号を作成する。カードに重複は無いので「550」「377」といった同じ数字を2つ以上使用した番号は作れない。
  • 先攻のプレイヤーは相手の番号を推理してコールする。相手はコールされた番号と自分の番号を見比べ、コールされた番号がどの程度合っているかを発表する。数字と桁が合っていた場合は「EAT」（イート）、数字は合っているが桁は合っていない場合は「BITE」（バイト）となる。例として相手の番号が「765」・コールされた番号が「746」であった場合は、3桁のうち「7」は桁の位置が合致しているためEAT、「6」は数字自体は合っているが桁の位置が違うためBITE。EATが1つ・BITEが1つなので、「1EAT-1BITE」となる。
  • これを先攻・後攻が繰り返して行い、先に相手の番号を完全に当てきった（3桁なら3EATを相手に発表させた）プレイヤーの勝利となる。

簡単にいえば、このゲームは「数当てゲーム」である。

相手の数を推測し、そのフィードバックを得る。そしてその情報を元に新しい推測を行う。それまでに得た情報からより良い推測を行うことが鍵となる。

 

ゲームの流れ

ゲームの流れを簡潔に述べ、同時に幾つか用語を定義しておく。

  1. 二人のプレイヤーが自分の数を設定する
  2. 先攻後攻を決める
  3. 先攻のプレイヤーが相手の数を推測し発表する
  4. 先攻のプレイヤーは相手プレイヤーから推測に対するフィードバックを得る
  5. 後攻のプレイヤーが相手の数を推測し発表する
  6. 後攻のプレイヤーは相手プレイヤーから推測に対するフィードバックを得る
  7. 3へ戻る
  8. 最初に相手プレイヤーの数を当てたプレイヤーが勝者となる

 

定義1

  • ゲームをプレイする二人をp1, p2とする。p1が先攻、p2が後攻とする。
  • p1, p2が設定した自身の数をa1, a2とする。
  • プレイヤーが相手プレイヤーの数を推測し発表することをコール (call) と呼ぶ。また、piのj回目のコールで発表された数をcijと表す。
  • cijに対して得られるフィードバックをfijと表す。fijはcijとEAT, BITEの数の組みとして表す。fij = (cij, eij, bij).

 

 

ゲーム攻略の本質

このゲームに勝利する上で本質的重要性を持つのは、それまでに与えられた相手の数についての情報（それは自分がコールした数とそれに対するEATとBITEの数として与えられる）から、次にどんな推測を行うのか、その戦略である。

上で定義した用語を用いると次のような問いを考えることになる：piにとってcijをそれまでに得たフィードバックの系列fi1, fi2, fi3,...,fi(j-1)からどのように定めるのが最善か。*2

 

定義2

任意のフィードバックの系列fi1, fi2, fi3,...,fi(j-1)に対して数cを対応させる写像のことをpiの戦術と呼ぶ。

 

戦術の優劣は相手の数に到達するまでのコール数の期待値で決まる。

理論的に最善の戦術を求めるのも面白そうだが、ここでは（最善とは限らない）簡単な戦術を考え、それをアルゴリズム化してpythonによって実装することを目標とする。*3

 

ゲームの簡略化

アルゴリズムを考える上で、議論を簡単にするため、ゲームを簡略化する。プレイヤーは一人（コンピュータ）であり、彼が答えの数を推測してゆくというゲームにする。このゲームの流れは次のようになる：

  1. 答えの数が決定される
  2. プレイヤーが数を推測する
  3. プレイヤーは推測に対するフィードバックを得る
  4. プレイヤーが数を推測する
  5. 答えの数が当たるまで続ける

 

定義3

  • この簡略化したゲームを1人数当てゲームと呼ぶ
  • 答えの数をaで表す
  • ゲームのプレイヤーをpで表す
  • プレイヤーがi回目のコールで発表する数をciで表す
  • ciに対して与えられるフィードバックをfiと表す。
  • ciに対して与えられるEAT, BITEの数をそれぞれei, biと表す。よってfi = (ci, ei, bi)
  • 任意のフィードバックの系列f1, f2, f3, ..., f(i-1)に対してciを対応させる写像をプレイヤーの戦術と呼び、Tで表す

 

次の問題を提起する：プレイヤーpにとって最善の戦術とは何か

ただしここでは冒頭で述べたように、この問題の解決を目指すのではなく、適当な（実装のし易い）戦術を考え、それをpythonによって実装することを目標とする。

 

道具立て

適当な戦術を考えるために便利な概念を定義する。

 

定義4

プレイヤーpがi回目のコール行う前に、答えの数として可能性のある数全体をPiと表す。

 

Piはフィードバックの系列f1, f2, f3, ..., f(i-1)によって定まるから、厳密にPiを書けばP(f1, f2, f3, ..., f(i-1))である。

 

例

P1は0~999までの自然数の集合と一致しない。実際、例えば000はルール上除外されるから、P1には含まれない。要はP1は0~999の数の中でルール上許される数の全体である。*4プレイヤーは最初のコールをする前であっても、答えの数についての情報「答えの数はゲームのルールに従う」を持っているわけである。

 

ゲームの流れに沿って、Pは（大抵の場合）小さくなる。P1から１回目のコールを行うことで答えの数の可能性は絞られるから  P_1 \supset P_2となる。同様に考えれば

 

P_1 \supset P_2 \supset \dots \supset P_{i} \supset \dots

 

が成立していることが分かる。

 

幾つかの戦術

T0

最も単純な戦術はP1から予め一つ数cを選んで、常にそれをコールをし続けるものである。つまりc = c1 = c2 = ... これをT0と呼ぶ。T0は明らかに最も弱い戦術である。もしコールする数として選ぶ数が正解でなければ、永遠に答えに達することがない。T0のような戦術は理論的には考察の対象となるかもしれない（実際それはこのゲームが終了しないことがあるという一番簡単な例となっている）が、今の考察の立場からすると、考えるに値しない戦術である。

 

T1

次に考えられるのはT0を少し改善して、ciをP1からランダムに決定する戦術である。これをT1と呼ぶ。T1は明らかに弱い戦術である。実際T1はそれまでに与えられているフィードバックを全く考慮しない。与えられている情報を活用出来ていない。

 

T2

T1を改良して、ciをPiからランダムに決定する戦術をT2と呼ぶ。ここまで来ると、ある程度フィードバックの情報を活かしていると言える。しかしT2が最善の戦略と言えるかどうかはかなり疑問である。実際次のような点は考慮に値する：

  • ciをPiからランダムに決定するよりも、良い決定方法があるのではないか？　例えばPiの各要素に対して得られるP(i+1)の大きさの期待値を計算し、それが最小になるようなciを選ぶとか。
  • ciをそもそもPiから選ぶ必要もない。Piに含まれていなければ確かに答えとしてあり得ないが、可能性を絞る上ではPiのどの要素より優れているということはあり得る。

 

T2'

T2の亜種として、ciをPiの一番小さな数として決定する戦術T2'を考える。*5

T2やT2'には上で述べたような疑問点はあるにせよ、今回はT2'を実装することを目標とする。

*1:他にも追加ルールが存在するが、今回は無視する。そうしてもゲームの面白さは変わらないと思える。

*2:問題を分析し、適当な記号と用語を導入し、議論を整理する。これだけで非常に大きく前進したことになる。最初から適切な記号や用語を導入したり、問題の過不足ない分析ができるわけではない。まずとにかく分析を始めてみる。そうすると少しずつ議論でネックになる部分が分かってくる。それはよく出てくる単語や概念だったりする。次にそれに名前や記号をつける。すると議論の見通しがよくなり、少し遠くまで見通せるようになる。そしてまたネックが分かってきて...というように進んでゆく。最初から完璧にやろうと思わないことだ。地道に地盤を固めてゆくしかない。

*3:この問題を考え始めたのは数学的な動機からではなく、プログラミングを練習する上で何か良い題材がないか探していたから。

*4:|P1| = 720である。

*5:ランダムに決定するプログラムを実装するのが面倒だった。