[Nine Mens Morris]


分析1

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

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

準備

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

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

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

filenim.rb
mainファンクションを配置するところ。(正型、逆型両方の勝敗判定ができ、playerを自由に設定できるようにしておく)
filenim_board.rb
nimの山と石の状態を管理するクラス
filenim_human.rb
人の手を入力するクラス。(標準入力から指手を入力)
filenim_ai.rb
aiを実装するクラス。(aiを組み込むまで、人と同じプログラムにしておきます)

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

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

ruby nim.rb

で実行できます。

必勝のためのAIについての考察 1 (正型nim)

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

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

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

  1. 自分の手番の後に、安定な状態を作る
  2. 自分の手番の後に、安定な状態を作れない場合、でたらめに、かつ、十分に少ない石を取る

安定な状態かどうかを判断するには、 すべての山を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

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

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

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

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


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

SEE ALSO

Feedback

選択肢 投票
おもしろい 0  
役に立つ 0  
興味ない 0  
理解できない 0  
やってみたい 0  
食べてみたい 0  

*1 ほぼ

TOP   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS   [Privacy Policy]  
Last-modified: 2014-08-23 (土) 17:57:59 (1575d)