nimをプレーするコンピューター・プログラム/02

外部仕様の定義によって、作成しなければならないシステムの要求が*1明らかにできました。次は、どのように実現するか、実現のための課題は何かを分析します。

まずは、制作する完璧版AIがとるべき戦略について分析しましょう。

↑

AIの動きを検討しやすくするため、準備をしておきます。

この準備では、プロトタイプを制作するための基礎となるソフトウェアを作成します。プロトタイプ・プログラムは、素早く記述ができて、後のシステムでも利用できるようにrubyを用います。

プロトタイプ・プログラムの構成

これで、人対人をコマンドラインでプレーできるnim盤ができました。 aiの実装をnim_ai.rbにおこない、適時nim.rbを書き換えて、動作を確認していきます。

プロトタイプ・プログラムは、

ruby nim.rb

で実行できます。

↑

将棋やオセロなどは、必勝手順が見つかっていないので、局面毎に状態を評価し、自分の手番で評価値が最大になり、相手の手番で相手が最善手を指した場合を想定して、読みを進める戦略を取ります。そのためAIは、局面毎の状態を保存しておく必要があります。

nimの場合、正型にも逆型にも言えることですが、必勝の手順が決まっており、いずれの局面でも勝ち負けが明確に判断できます。そのため、必勝のためのAIは、局面状態の保存と先読みは必要ないといった特徴があります。

必勝のためのAIは、以下の戦略でプレーするようにプログラムを組み込みます。

安定な状態かどうかを判断するには、すべての山を2進数で表し、すべての山の値を排他的論理和で足しあげ、その結果が0であれば安定な状態と言えます。

不安定な状態から、安定な状態を作るには、均衡していない組の2進数のもっとも大きな桁を持つ山から、適当な数の石を取ることで均衡な状態にします。

分かりにくいので、例を見てみましょう。左の数字は、山の番号、括弧内の数字が石の数を表しています。

0( 1): *
1( 2): **
3( 6): ******

この局面は、次のように、(1の組=1つ, 2の組=2つ, 4の組=1つ)で不安定状態と判断できます。

0( 1): 1
1( 2): 22
3( 6): 444422

ここで、均衡の取れていない山3の4の組に注目して、全体が均衡するように石を3個取れば、安定な状態を作ることができます。

0( 1): 1
1( 2): 22
3( 6): 221

この操作をプログラムにすると、次のようになります。(注釈はプロトタイプからの修正箇所)

nim1.rb: 後手にAIを選択します。AIに盤面情報を渡すため、playerメソッドにnim_boardオブジェクト引数を追加
nim_board1.rb: インスタンス変数 @board の読み取りを外部からできるように修正
nim_human1.rb: AIに盤面情報を引き渡すために、playerメソッドに仮引数を記述
nim_ai1.rb: 今回のAI実装パート。(前述の戦略のRubyでの実装方法を照合してみてください。bit演算を用いることで、効率的に局面判断をしています。)

動かしてみて、問題がないか確認しましょう。問題があれば、デバッグ・ライト文を入れて何が原因か追求します。まだ、プログラムが十分に小さいので、デバッガや他の外部ツールを使わなくてもだいじょうぶです。

これで、正型nimのためのAIプロトタイプが完成しました。

...つづく (2009/4/2)

↑

SEE ALSO †