読者です 読者をやめる 読者になる 読者になる

euphonictechnologies’s diary

Haskell超初心者の日記です。OCamlが好きです。

follow us in feedly

Haskell オセロ - Small update - Haskellオセロ始めました

Swiftが遅いので

Haskellでオセロプログラムを書いて、それをSwiftから呼び出します。一連のghc-iosの実験はそのためのものなのでした。

blog.euphonictech.com (などGHC for iOSシリーズの記事)

今やHaskellの関数をiPhoneアプリケーションに簡単に組み込むことができます。なので書きやすい方で大事なところを書いて、Swiftはフロントエンドに集中させようと思います。

blog.euphonictech.com

一応動くものができたので、記録を残しておこうと思います。

ソースコードは

github上にあります。名前はHamletといいます。

github.com

動いている様子

同じディレクトリにあるsubproc.pyというプログラムで2つのEdaxプロトコル準拠のオセロプログラムの対戦ができます。こんな感じで対戦をさせます:

f:id:euphonictechnologies:20150521151751p:plain

単純に標準出力を聞いてパーズしてやったことを相手方に標準入力で伝えているだけです。土管です。いまのところ世界最強のオセロプログラムに60石以上の大差をつけてボロ負けできます。

基本的なアルゴリズムは

Haskell将棋で用いているものと"全く同じ"です。ソースコードはコピーアンドペーストで動きました。参照透明すばらしい。型さえ合っていれば全くそのままで動きます。プログラムはクライスリ圏の射ですね。

blog.euphonictech.com

指し手生成とビットボード

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に全滅負けしなくなると思われます。

次のステップは?

当然評価関数になってくると思います。古典的評価関数の概形を作り、簡単な強化学習で係数を学習させてみたいと思います。

参考資料

grafi-tt/tatsuki · GitHub

edax.c - edax-reversi - A strong othello program - Google Project Hosting

強いオセロプログラムの内部動作 - Gunnar Andersson