オセロのAIを実装しています。

将棋を少し離れて諸事情によりオセロのAIを実装しています。将棋に少し関わりがあるので、少しメモを。

いま実装しているのは必勝読みルーチン、読みきりルーチンです。df-pnを勉強しつつ単純なpnsを実装しています

df-pn探索(depth first, proof number)あたりは日本語の文献がいくつかあるのだけど、どれもがなんか木で鼻をくくったような、もしくは一見さんお断りなような解説が多く、なかなかとっつきが悪そうに思えます。色々読み込んでいくうちにその理由も見えてきて、複雑で実装をやり切るのが大変だと。実装し切るのにエネルギーを使い果たしてしまうのではないでしょうか。 Bonanzaにも実装されているのですが、Bonanzaの実装は実戦特化のスピード重視で長手数読み用ではなくて、実戦で自明な罪を早く見つけるために使用されているようです。コードを読んでいないので実際に所はわかりません。

参考文献

PNS

そこでいまはオセロ用のPNS (proof number search) を実装しています。参考にしているのはchessprogramming - Proof-number searchです。少し引用すると

void PNS ( Node root ) {
  evaluate( root );
  setProofAndDisproofNumbers( root );
  Node current = root;
  while ( root.proof != 0 && root.disproof != 0 && resourcesAvailable() ) {
    Node mostProving = selectMostProvingNode( current );
    expandNode( mostProving );
    current = updateAncestors( mostProving, root );
  }
}

これが骨子の部分で

evaluate
setProofAndDisproofNumbers
selectMostProvingNode
expandNode
updateAncestors
generateChildren

の5関数を実装するとこのアルゴリズムが動きます。Node構造体は

expanded: Bool
proof, disproof: Integer
type: enum {AND, OR}
value: enum {proven, disproven, unknown}
children: [Node]
parent: Maybe( None )
misc data (for evaluation)

という感じです。miscの部分以外はこのPNS探索に必要で、misc dataはevaluateでvalueを設定するのに必要です。evaluate関数以外はwikiに実装のpseudo-codeが掲載されていますが、evaluateはありません。evaluateだけはゲームに依存するからです。オセロの場合、evaluateは局面が積みかどうかを判定します。endgameデータベースを使う時もこの中でlookupすることができます。

今回はすこしふわっとした内容ですが、実装できたらまたアップデートしようと思います。

Joel on softwareのこと

<a href="http://www.joelonsoftware.com/items/2006/06/16.html">My First BillG Review - Joel on Software</a>

My First BillG Review - Joel on Software

日本語訳はこれ: はじめてのBillGレビューのこと - The Joel on Software Translation Project

この中でJoelがBillgについて評した部分で

It was a good point. Bill Gates was amazingly technical. He understood Variants, and COM objects, and IDispatch and why Automation is different than vtables and why this might lead to dual interfaces.

My First BillG Review - Joel on Software

のところ。いまさらなのだけど、ここのところの理解があやふやだったので、参考資料をメモしておく。

自分の理解だとvtableはコンパイルタイム解決でIDispatchはランタイム解決かな、と思っていたので、詳しい説明は

あとは言わずと知れたDr. GUI: