Hit and Blow

Hit & Blow

Java授業で出された課題で、
「数当てゲームで,まず最初にお互いに4桁の正の整数を設定（数字の重なりはないものとする)し,一方が推測した数字を伝えると相手は場所 が合っている数字の数(ヒット)と場所は異なるが数字がある数(ブロー)を答える．最終的には先に完全な数字を当てた方が勝ちとなる．」
という問題について人間側とCPU側双方を作れというものが出た。

作ってみる

期限は2週間。とりあえず、作ってみた。とある経緯で最強は特に目指すつもりはないなるべく強いものを作りたい。
根幹部はほとんど既に作ってあるので、ほとんどCPU側のアルゴリズムを作れと読みかえていい。
来年もこの課題が出るかもしれないし、外のプログラムを写す輩がいると頑張った人が興醒めなので、ソースはここに書かないが、次のようにやってみた。すなわち、

1.配列を使い、int型の10000個のデータ領域を取る

数字の重なりはないので、10000個用意する必要はないのだが、参照が楽になる。
この中には得点を入れることにする。得点をどう使うかは追って見る。
ここではこの配列を探索テーブルと呼ぶ

2.探索テーブルで数字の重なりのあるものには0点、ないものは1点を代入していく。

早い話が、数字の重なりがあるモノは判定側に聞いても仕方ない(というか、当たらないし無駄)ので、
判定側に渡す数に選択しない。"0点"は以降選択されないように組む。

3.ランダムな値を判定側に渡す

これは初めだから、当たりをつける意味で、ランダムな値を取ることにしている。
当然、探索テーブルから0点でないことを確認する。
だったら定数でも構わないのだが、人間側に出題傾向があったら判定に影響しそうでやだ。

4.得点操作

たぶんこのプログラムで最も重要なところ。
int型の配列、{ヒット数,ブロー数}で返ってくる。

ヒット数が0のとき、任意の桁に指定された数は必ずその桁に入らない。
探索テーブルから任意の桁に指定された数があるものを探し、すべて得点を0点にする

ヒット数がi(i≠0)のとき、任意の桁に指定された数はその桁に入っている可能性がある。
探索テーブルから対象となるものを取り出し、それが0点でなければ得点をi点加算する。

ブロー数が0のとき、その数に含まれるものは解答にも含まれない。
探索テーブルからその数が含まれるものを探し、すべて得点を0点とする。
ここで注意したいのは例えがブローが0でもヒットしているかもしれないこと。
探索テーブルと桁が同一のものは0点にしない。

ブロー数がiのとき、その数に含まれるものは解答に含まれる。
探索テーブルからその数が含まれるものを探し、すべて得点をi点加算する。

5.ターン進行

得点が高いものから判定にかける。得点が同じならどれを選んでもよい
渡したら4の行程へ。

テスト

Javaで組んで1000回試行してみた。結果、平均13手、1000回中の最高手数は30回だった。
なお、このCPU側のプログラムは一つのクラスとなっていて、改行(メソッド間は1行開けるなど)を含めて83行となっている。
(人間側と共有するプログラム部分があるので一部機能を分割して別クラストした部分があるが、これは10行程度のものであり、総じて90行ちょっとである)

他の人はどのくらいの結果を出すか。

例えば、東京大学の伊庭先生のプログラム、
http://obi-wan.cure.to/programming/c/strongest.c
は、「これより強いプログラムはありません」とコメントに書かれている。
平均は5.21回だそうだ。これは人間相手でもスパスパ勝てそうだ。
定跡を全て書いており、プログラムが大きく感じる。

またやってみたい

5行程で「得点が高いものから判定にかける。得点が同じならどれを選んでもよい」と書いたが、これは選択的に値をとれる気がする。たとえば探索テーブルを桁ごとにみて、頻度の高いものを優先的に選ぶとか。

ちなみにボツにしたが、ヒットとブローではヒットの方が起こりにくいからi点ではなく重みをつけてみたが、i点が最も手数平均が少なく済んだ。下手なことはするな、ということか。