Schemeの課題 --- (kadair)

コンピュータゲーム

ここでは，二人確定完全情報ゲームをコンピュータに行わせる方法について考える． 二人のプレイヤで行うゲームで，すべての情報が二人のプレイヤに公開されていて，さらに偶然の要素が入り込まない場合，そのゲームを二人確定完全情報ゲームと呼ぶことにする． たとえば，将棋，チェス，囲碁がその代表である． トランプゲームのように，公開されていない情報がある場合は，完全情報ゲームではない． また双六のようにサイコロの目によってゲームが左右されるようなゲームは確定ゲームではない． なお，ゲームはいつか決着がついて，必ず勝敗(あるいは引き分け)が決まるものとする．

ゲーム木

二人完全情報ゲームの進行状態は，木によって表すことができる．

木のノード(節)は，ゲームのある時点での状態を示す． 白と黒は，二人のプレイヤを表す． つまり，白ノード，黒ノードは，それぞれ白プレイヤの手番，黒プレイヤの手番でのゲームの状態を示す． あるノードから下のノードにエッジ(枝)が張られているときは，上のノードから一手進めることで，下のノードの状態に移行することを示している．

図で一番上の白手番からは，3本のエッジがでている．これは，この時点で，白が打つ手は，3通りあることを示している．また，白が左の手を選択した場合，次の黒は，3通りの手を選択可能，白が中央の手を選択した場合，黒は2通りの手を選択可能，白が右の手を選択した場合には，黒は4通りの手を選択可能である．

原理的には，開局から終局まで可能な手をすべて挙げていけば，完全なゲーム木を構築して，ゲームの進行状態をすべて表現することができる． なお，ゲームを異なる手順で進めていって，同じ局面になる場合があるが，ゲーム木では，これらは別々のノードで表現される． すなわち異なるノードは必ずしも異なる局面を表しているとは限らない．

MIN-MAX法

人間がゲームを行う場合，頭のなかで，いくつかの候補を考えて，何手か先まで局面を進めてみて，その中の最善手を選択する． これは，ゲーム木を調べて，最も有効と思われる手を選択することと同等である． したがって，局面の善し悪しをうまく評価できれば，ゲーム木の解析を行うことで，同様の選択をコンピュータで行うことも可能である． 基本的なゲーム木の解析法として， MIN-MAX法 がある．

MIN-MAX法を実現するために，まず局面を評価して，その形勢の良さを数値で表す局面評価関数を与える． たとえば，勝利が確定する局面には，最も高い評価値を与え，敗北が確定する局面には最も低い評価値を与えればよい． それ以外の形勢の局面においても，さまざまな要素を考慮して，状況に応じて，評価値を与えるものとする．

次に，この局面評価関数を用いて，着手を決める方法について述べる． 例として，黒の手番で三手先までのゲーム木と，それぞれの局面の評価関数の値が次の図のように得られている状況を考える．

黒の第一手の選択は2手あり，このどちらかを選ぶことになる． 次の白の第二手は5通りある．その次の黒の第三手は全部で10通りある． 黒としては，三手先までの段階では，一番右の評価値9の局面にたどり着く場合が最も有利である． そこで第一手として右側を選ぶことにしたとする． ところが，次の白の手番では，黒の有利となる手は打たないだろうから，白は，黒の評価値が3か2になる左側の手を選ぶだろうと予想される． すると，黒は，評価値3,2の手のうちから，評価値3の手(右から4番め)を選ぶしかないことになる． つまり，第一手として右側を選んだ結果は，評価値9ではなく評価値3を得ることになる．

二人のプレイヤがお互いに最善を尽くして手を進めるものとして，黒が選ぶべき手を機械的に決めるには，次のようにすればよい． まず第一にゲーム木の先端の局面の評価値を全て決める． 次に黒の第三手を選ぶ五つ局面に関して，いずれの局面でも黒は最善の手を打つものとして，それらの局面の評価値を，それぞれの局面で最大の評価が得られる手を選んだときの局面の評価値とする． すると，次の図で，赤で示されているような評価値を得る． つづいて，いま得られた五つの局面の評価値を元にして，白の第二手を選ぶ二つの局面の評価値を決める． ここでは，白は黒にとって最も不利になる手を選ぶものとして，二つの局面それぞれの評価値を，最小の評価値をもつ手を選んだときの局面の評価値とする． 図では，青で示されている評価値を得る． 最後に黒の第一手として，いま得られた二つの局面の評価値の中から最大のものを選ぶ． 左側の手は評価値5,右側の手は評価値3であるから，この場合は，結果として，評価値5の左側の手を選ぶことになる．

つまり，自分の手番で現在の局面の評価値を決めるには，一手先の局面の評価値を全て決めて，それらのうち最大値をとればよい． 一手先の各局面は，相手の手番であり，それらの局面の評価値は，それぞれの一手先の各局面の最小値で決まることになる． またその先の局面は，自分の手番であり，さらに一手先の局面の評価値の最大値を選ぶことになる． さらに手を進めていって，予め決めておいた手数まで読んだときの局面では，評価値は局面評価関数で直接決める． このように評価値が，交互に最大値と最小値をとることで再帰的に決められることから， この手法がMIN-MAX法と呼ばれるわけである．

ところで，終局時点での評価値が，ゲームの勝敗によって確実に決められるならば，理論的には，開局から終局までの完全なゲーム木を構築して，MIN-MAX法を適用すれば，二人確定完全情報ゲームにおいては，ゲームをやる前からゲームの勝敗は決まることになる． しかし実際には，終局までの手数がかなり少なくない限り，ゲーム木は極めて大きくなるため，完全なゲーム木を解析することは，現実的には不可能である． したがって，実際のゲームにMIN-MAX法を適用する場合，一定の手数だけ読んで， その局面での形勢で手を決めることになる．

また一般に，この手法で選択する手は必ずしも最善手とはならない． これには次のような要因が考えられる．

• 局面評価関数が「正しい」とは限らない．
• 自分と相手が同じ局面評価関数を用いていると仮定している．
• 相手が必ず最善手を打つものと仮定している．
• 局面の状態によらず，すべて一定の手数で読みを打ち切っている．

さらにMIN-MAX法では，可能な手をすべてチェックするが，中には読んでも無駄な手があることも考えられる． 人間は，明らかに無駄な手を選択肢から省いたり，いわゆる手筋を使うなどして有望な手を優先的に調べたりすることができる． このような知識を用いてゲーム木を解析することは，まさに人工知能の問題である． 知識を用いない場合でも，MIN-MAX法を改良する余地はある．そのような方法と してよく知られているものに αβ法 がある．興味がある者は，調べてみるとよい．

コンピュータリバーシプログラムの作成

リバーシ(Reversi)とは，一般にオセロの名で知られているゲームを呼ぶのに使われる名称である． オセロはイギリス発祥のリバーシを改良して発明されたゲームである．オセロという名前は，ツクダオリジナルの登録商標であるため，オセロゲームを表すのに一般にリバーシという名称が用いられている．

リバーシにおいて，ある局面と手番(白，黒)，および局面評価関数が与えられたとき，MIN-MAX法によって，着手を決定する3引数関数を作成せよ．

 (min-max bw board eval-func)

ここで，bwが手番(白，黒)，boardが局面，eval-funcが局面評価関数とする． なお，MIN-MAX法で読む手数は，適当な変数(*depth*)として別に与えておくものとする．

着手は，次のようにマスを表す盤面の位置で返すものとする．

(i j)

これは，上からi列，左からj列のマスを示すものとする． たとえば，次の図で一番上の黒の位置は，(2 3)である．

なお，次のファイルにリバーシを実行するために必要な枠組はほとんど用意してあるのでこれを用いてよい．

reversi.rkt(コードを指定せずにwebブラウザで表示すると文字化けすると考えられる)

但しこれはDr.Racket用のファイルであり、array関係の函数をファイルの 最後の部分で記述している。 これらの函数をユーザが記述しなくてよい場合には、 それらをコメントアウトするか、 あるいは次の一般のScheme処理系用のファイル「resersi.scm」を用いる。 こちらのファイルでは該当部分を分離してある。

両者ともにファイルの先頭に，利用可能な関数とデータの説明がある．

reversi.scm

array.scm(array関係の関数定義)

なお，これらのファイルは， 自分で作成するファイルからloadして使うこと．

  (load "scheme/reversi.rkt")

Dr.Racketの処理系が動いているカレント・ディレクトリからの相対パスを指定している。

ちなみに，上記ファイルをロードしてから，次のような式を評価すると，人vs人でリバーシの対戦ができる． ただしこの際，仮想端末の日本語文字コードを正しく設定していないと文字化けが起きる． 例えばGNOME仮想端末の場合には「端末」メニューの「文字コードの設定」から設定できる．

	==> (game man-move man-move)

手の入力は，表示されるプロンプトにつづいて，次のように行う．

 black>> (i j)

ゲームを途中で終了するには， [Ctrl]+[d] を入力すればよい． 関数min-maxが作成できたら，さらに次のような関数を定義してみよ．

;;
;; COMプレイヤ関数
;; 評価関数として eval-by-countを与える
;; これは単純にプレイヤbwの石の数を評価値とする関数である
;;
(define (com-move bw board)
  (let ((hand (min-max bw board eval-by-count)))
    (display (list (players-name bw) hand))
    (newline)
    (do-move bw hand board)
    #t))

;;
;; eval-by-count == p-count
;;   p-countは，プレイヤbwの石の数を返す関数(reversi.scmで定義済み)
;;
(define (eval-by-count bw board) (p-count bw board))

これにより，以下のような対戦が可能となる．

        ;; black=人，white=コンピュータ
	==> (game man-move com-move)
        ;; black=コンピュータ，white=人
	==> (game com-move man-move)
        ;; black=コンピュータ，white=コンピュータ
	==> (game com-move com-move)

Have fun!