« プログラミング講座(35) ×○ゲーム人対人、クラスもどき | トップページ | プログラミング講座(37) ゲーム木の探索 »

2011/01/18

プログラミング講座(36) ゲームの木

今回はゲームの木についてプログラミングしてみようと思います。参考資料は『思考ゲームプログラミング―オセロゲームのアルゴリズムと作成法 (アスキーブックス)』です。この本はオセロゲームのプログラミングについて書かれた本で、プログラミング言語にはC言語を使用しています。IBMのDeep Blueがチェスのチャンピオンを破った1997年より11年も前の1986年に発行された本です。

Photo
【図31 思考ゲームプログラミング】

ゲームの木とはゲーム開始の局面からすべての局面に通ずる手をグラフ化したものです。初手はA1からC3まで9局面あり、それぞれがルートノードからの1段目のノードになります。2手目が初手A1に対してB2からC3までの8局面あり、初手B1に対しても8局面というように、2段目のノードは計72局面になります。このように終局までをすべてつないでいきます。

Photo_2
【図32 ゲームの木】

ゲームにおいて次の手を考えるということは、ある局面(ノード)から分岐する次の局面(ノード)のどれを選ぶのが一番得かを考えることになります。これをゲーム木の探索と呼んでいます。

このような先読みのプログラムに取りかかる予行演習として、すべての局面を次々と表示するプログラムを作ってみましょう。疑似コードは次のようになります。

【リスト11 すべての局面を表示するプログラムの疑似コード】
Sub SearchNextCross ' 次の×
 For iY = 1 To 3
  For iX = 1 To 3
   盤[iX][iY]が空なら
    そこに×を打つ
    終局でなければ
     SearchNextNought() ' 次の○
    打った手を元に戻す
  EndFor
 EndFor
lExitCross:
EndSub

この疑似コードは先手×の手を打つサブルーチンですが、後手○のサブルーチンも同様の形になります。お互いがお互いを再帰的に呼び出します。

(つづく)

|

« プログラミング講座(35) ×○ゲーム人対人、クラスもどき | トップページ | プログラミング講座(37) ゲーム木の探索 »

Small Basic」カテゴリの記事

私の本棚」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: プログラミング講座(36) ゲームの木:

« プログラミング講座(35) ×○ゲーム人対人、クラスもどき | トップページ | プログラミング講座(37) ゲーム木の探索 »