研究室の課題で作ってたオセロを一応完成とした。というかこれ以上の改善は自分には無理(笑)。
-実装した機能
--探索
コンピュータが次の手を捜すとき、まずは登録してある定石集から探す。具体的には現在の局面をキーとして定石集を線形探索、見つけた手の中から評価値がもっとも大きいものを次の手とする。
定石が見つからなかった場合、現在の手数によって中盤探索か終盤探索を行う。
---中盤探索
あらかじめ決めた深さnによって、n手読みをする。リーフノードの近くでは単純なアルファ・ベータ探索(実際にはネガアルファ探索)を行う。それ以外では、move orderingをし、置換表を用いたネガスカウト探索を行う。
----move ordering(中盤)
中盤探索では、一手読みをし、その評価値によって手をソートする。
----置換表を用いたネガスカウト探索
まず置換表を参照し、現在の局面が登録されているか探す。発見した場合は次の手、評価値を返す(一意に決まらない場合もある)。
発見できなかった場合は、ネガスカウト探索を行う。最探索をする場合も置換表があることによって、探索にかかる時間を短縮できる。
---終盤探索
手数があらかじめ決めた値に達したら終盤探索を行う。最後まで読みきり、石差を評価値として返す。中盤探索と同様にリーフノードの近くでは単純なアルファ・ベータ探索(ネガアルファ探索)を行う。それ以外ではmove orderingをし、置換表を用いたネガスカウト探索を行う。
----move ordering(終盤)
開放度によってソートする。開放度が等しい場合は一手読みをし、その評価値によってソートする。
--学習
強化学習(教師なし学習)を行う。プログラムが自分自身と対局し、その勝敗によって対局中に現れた局面を評価する。評価値はパターンによる評価値を用いる。局面を評価するとは、正確には全てのパターンの重みを学習するということ。
ちなみに定石は手動登録。
とまぁこんな感じで完成。本当はMPCとか実装したかったけど、自分には難しすぎて理解できませんでした。
研究室内オセロ大会に向けて目下強化学習中!!
-関連語句
アルファ・ベータ(α-β)探索
ネガアルファ探索
null window search
move ordering
開放度(mobility)
強化学習
2009年6月3日水曜日
2009年5月8日金曜日
[オセロプログラム]定石実装
やっと定石実装できた。。。
http://www.es-cube.net/es-cube/reversi/sample/index.html
いつも通り上のページを参考にして作ったけど、cからjavaに移植するの結構つらい(自分の能力だと)。
unsignedがないし、メモリ管理がどうなってるかとかいまいち理解してないし。
だめだめですねぇ
まぁそれはそうと、定石があると思考時間が一気に削減できるからなんか快感(笑)
手動で定石を登録していくんだけど、オセロの定石なんかわからん。どこから持ってこようか。
・マルチスレッド化
・相手の探索中(入力待ち時間)に探索
http://www.es-cube.net/es-cube/reversi/sample/index.html
いつも通り上のページを参考にして作ったけど、cからjavaに移植するの結構つらい(自分の能力だと)。
unsignedがないし、メモリ管理がどうなってるかとかいまいち理解してないし。
だめだめですねぇ
まぁそれはそうと、定石があると思考時間が一気に削減できるからなんか快感(笑)
手動で定石を登録していくんだけど、オセロの定石なんかわからん。どこから持ってこようか。
・マルチスレッド化
・相手の探索中(入力待ち時間)に探索
2009年5月5日火曜日
オセロプログラムの作成
大学の研究室の課題としてオセロプログラムの作成があるから作ってみた。
http://www.es-cube.net/es-cube/reversi/sample/index.html
上のページを参考にしてjavaで実装した。
すごく丁寧な解説があって、よくまとまっていて、とても参考になります。
minMax探索やらnegaMax探索やらα-β探索といった定番の探索アルゴリズムで実装したけどそれなりに強い。
強化学習恐るべし・・・
プログラム作成の期日までにあと定石ぐらいは実装しよう。
当然だけど既に自分で作ったプログラムに自分で勝てない(笑)
・定石の実装
・マルチスレッド化
・相手が思考している間に探索
http://www.es-cube.net/es-cube/reversi/sample/index.html
上のページを参考にしてjavaで実装した。
すごく丁寧な解説があって、よくまとまっていて、とても参考になります。
minMax探索やらnegaMax探索やらα-β探索といった定番の探索アルゴリズムで実装したけどそれなりに強い。
強化学習恐るべし・・・
プログラム作成の期日までにあと定石ぐらいは実装しよう。
当然だけど既に自分で作ったプログラムに自分で勝てない(笑)
・定石の実装
・マルチスレッド化
・相手が思考している間に探索
登録:
投稿 (Atom)
