Haskell オセロ - Small update - Haskellオセロ始めました
Swiftが遅いので
Haskellでオセロプログラムを書いて、それをSwiftから呼び出します。一連のghc-iosの実験はそのためのものなのでした。
blog.euphonictech.com (などGHC for iOSシリーズの記事)
今やHaskellの関数をiPhoneアプリケーションに簡単に組み込むことができます。なので書きやすい方で大事なところを書いて、Swiftはフロントエンドに集中させようと思います。
一応動くものができたので、記録を残しておこうと思います。
ソースコードは
github上にあります。名前はHamletといいます。
動いている様子
同じディレクトリにあるsubproc.pyというプログラムで2つのEdaxプロトコル準拠のオセロプログラムの対戦ができます。こんな感じで対戦をさせます:
単純に標準出力を聞いてパーズしてやったことを相手方に標準入力で伝えているだけです。土管です。いまのところ世界最強のオセロプログラムに60石以上の大差をつけてボロ負けできます。
基本的なアルゴリズムは
Haskell将棋で用いているものと"全く同じ"です。ソースコードはコピーアンドペーストで動きました。参照透明すばらしい。型さえ合っていれば全くそのままで動きます。プログラムはクライスリ圏の射ですね。
指し手生成とビットボード
Swiftで実装したオセロ用のビットボードをHaskellにほぼそのまま移植しました。
FlatReversi/BitBoard.hs at master · ysnrkdm/FlatReversi · GitHub
多分そのまま動くはず。まだif文が大量に含まれているので、これを分岐なしの形に書き換えることでさらに高速化を図ることができそうです。
指し手生成は基本的に八方向分の置ける場所生成関数内で、ひとつの方向についてはすべて列挙してしまいますが、方向については遅延生成しています。具体的に言うと
getPuttables :: Bb -> Piece.Co -> BitBoard getPuttables bb colour = foldr (\x y -> y .|. (getBitPuttables bb colour x)) emptyBoard directions
あからさまにfoldrで遅延生成になっています。一つの方向を処理しているgetBitPuttables関数内で遅延させるのはあまり効果がなさそうです。ビット演算6発で生成できてしまうので。分岐もないし、うまくGHCがコードを生成してくれれば高速です。
評価関数
評価関数は明らかに手抜きなものがテスト用に入っています。
staticEval :: BitBoard.Bb -> Value staticEval board = openness board + numPieces board + possibleMoves board
というわけで、辺の形もおいてある場所も考慮しない、石の数と開放度と置ける場所の線形和です。Edaxに勝てる理由が見当たりません。おそらくオセロ最弱の私でも勝てます。この部分をどうにかするとEdaxに全滅負けしなくなると思われます。
次のステップは？
当然評価関数になってくると思います。古典的評価関数の概形を作り、簡単な強化学習で係数を学習させてみたいと思います。
参考資料
edax.c - edax-reversi - A strong othello program - Google Project Hosting
