クマ将棋のバイナリ・ソース
最終更新:2012/5/7
開設日:2011/12/31
簡単な将棋プログラム「クマ将棋(別名:simk)」のページです。将棋所などのUSI対応ソフトに登録して実行できます。
第22回世界コンピュータ将棋選手権バージョン(2012/5/7)
クマ将棋で初参加。一次予選7位で通過、二次予選19位。
大会HP:http://www.computer-shogi.org/wcsc22/
アピール文書:http://www.computer-shogi.org/wcsc22/appeal/Kuma_Shogi/kuma.pdf
大会二日目バージョンのバイナリです(90MBあります。win7-64bit+将棋所で動きます。25分切れ負け設定)
大会では序盤で、通常探索のイタレーション14、中盤以降は8〜10くらいでした。
これに静止探索や延長(王手、0.5手延長)が加わります。詰めルーチンは入っていません。
ソース(本体+学習部)はもう少し整理してから公開します。
バージョン1(2011/12/31)
駒得のみの簡単なプログラムです。ソースも公開しています。
Core2Duoマシン・前半は深さ12、中盤以降は深さ8程度読めるようです。
実行&圧縮ファイル:siimple_shogi_1231.zip
Microsoft Visual C++ 2010 Express(無料)でコンパイルできます。
VS上で「CUI」をコマンド引数に指定して実行すると「検討モード」として実行できます。
検討モード
2011年の8月頃にふと、youtubeかニコニコ動画かでNHKの番組「運命の一手 渡辺竜王VS人工知能・ボナンザ」を見た。
番組の内容は、化学の人が作った将棋ソフト「ボナンザ」が2006年の将棋選手権に初出場・初優勝、しかも、ワークステーションなどの
高性能PCの参加者が多い中、ボナンザはノートパソコンで出場というもの。えらく衝撃を受けた。
なんでも機械学習を将棋に取り入れたのが成功の秘訣だったらしい。
というわけで、将棋ソフトに興味をもったので、作ってみようと思ったのが9月ぐらい。
最初は、αβ法と駒割のみ(駒に点数をつけて、駒の枚数で形勢を評価する方法)で作ってみたが、
深さ3〜5くらい読むのが限界だった。一方で、ボナンザは一気に深さ13以上読むので不思議でならなかった。
その後、池氏の「コンピュータ将棋のアルゴリズム」と小谷先生の「ゲーム計算メカニズム」という本を購入。
参考に改良したが、自分が将棋アルゴリズムに対して理解も浅いのもあって、あまり読みの深さは変わらなかった。
10月半ばからボナンザのソースを見ながら作りなおした。Magicビットボードも使ってみた。
東大の将棋サーバfloodgateにも投入してみたら1800くらいレートがついた。でも、ボナンザの評価関数(fv.bin)
をそのまま使っている割には弱すぎる。ということで、また最初から作りなおしたのが12月半ば。
ビットボードで作るのは大変なので(OSに依存するしデバッグしにくい)、今度は簡単な配列版で作ってみた。
今度は詰めルーチンも入れなかったが、ビットボード版とそんなに強さは変わらなかった。
よっぽど、前のバージョンが駄目だったのだろう。
基本的にボナンザの劣化コピーなので、ソフト自体に価値はない。ということでソースを公開します。
このソースでは駒割のみですが、ボナンザのfv.binを入れるのも簡単にできると思います。
このページでは、その配列版の将棋ソフト(simk)の開発にあたってのメモを記します。参考になれば幸いです。
Simkの特徴
1. C++(ほとんどCに近い)で書かれている。
2. ビットボードを使わない単純な配列での盤面管理。
3. 詰めルーチンはない。
4. 駒得のみ。
探索ルーチンはボナンザを参考(というか、殆どそのまま)にしています。
オーダリング
・ハッシュ参照、ハッシュ手
・キラー手
・history heuristic
・SEE(駒の交換値)
探索・枝狩り
・history reduction
・null move pruning
・NegaScout(PVサーチ)
・futility cut
・βカット
・hash cut
9×9の盤面上の駒(駒種:14種類×2プレイヤー)と持ち駒情報(7×2プレイヤー)の情報をcharの配列で待たせている。
王の位置もよく使うので持たせている。
struct kyokumen_t
{
// 盤面
char kifu[81 + 14];
// 王の位置
char king_pos[2];
// ハッシュキー
uint64
hash_key;
// 駒割
int material;
};
全体的に変数名は変ですが気にしないでください。
Simkでは、最初に手を全て生成してから、ループを回している。ボナンザでは、最初に駒を取る手、移動する手、駒を置く手などに
小分けに生成しているが、大変そうなのでやっていない。
ただし、simkでは王手の時には王手を回避する手を、静止探索では駒を取る手のみを生成するようにしている。
したがって、手を生成するルーチンは以下の3つのみ。詰めルーチンを入れるならば、王手をかける手を作成する必要があるが、
これはかなり困難なので作っていない。
■全ての手を生成(gen_all_moves)
駒を移動する手と駒を置く手の全て。駒種毎に、利きのテーブルを用意して、手を生成している。
面倒なのは、飛車、角、香などの跳び駒で、駒を起点に上下左右ほかの駒にぶつかるまでfor文を回して
手を生成している。
■駒を取る手(gen_cap)
基本的にgen_all_movesを少し変えれば簡単にできる。
■王手を回避する手を生成(gen_evasion)
これが結構厄介だった。王手をかけた駒をとるパターンと、王が移動して避けるパターンがある。
2か所から同時に王手(両王手)をかけられた場合は、王を移動させる他ない。
全般的に、手の生成は面倒くさい割に、間違った手を生成していても(or 生成すべき手を生成していない)気づかない場合がある。
すなわち、正解の手は、普通わからないので確認のしようがない(自分は仕方ないのでボナンザの生成した手と比較してチェックしていた)
実行しても、違法な手はわかることもあるが、ほとんどが微妙にプログラムが弱くなるだけなので気づかない。
とくに、simkでは王手を回避する手の生成を失敗して、終盤に急に弱くなるパターンが多かった。
ボナンザと同じく、通常探索+静止探索を行っている。
静止探索では、駒を取る手(交換値が負になる手と、王手をかける手は省く)のみで探索する。
simkでは最初は、「交換値が負になる手と、王手をかける手は省く」を行っていなかったので
静止探索がえらく重かった気がする。
探索では、深さを制御するために、残り深さrdepthと、探索回数plyを関数に渡している。
αβ探索を効率よく行うためには、なるべく最善手から探索しなければいけない。しかし、最善手はわからない(わかっていれば探索する必要はない)ため、
それらしい手から探索する。たとえば、評価値の変動が大きな、駒を取る手、成る手などを優先的に探索する。
逆に、明らかに駒損する手や、端っこに歩を置く手などは後回しにしたほうがよい。このように、差し手を評価して探索順を決めることを
オーダリングと呼ぶ。オーダリングは将棋の知識に基づいた経験的な方法である。
オーダリングはかなり強力なようで、ここを良くすると格段に深く読めるようになった。しかし、先の教科書にはあまりオーダリングの
重要性に触れられていない模様。SEEで並び変えるだけでもかなり違う。
探索と枝狩りは以下を用いている。ほとんどがボナンザと同じ。
アスピレーションサーチとextended futilityは使っていない。
・history reduction
・null move pruning
・NegaScout(PVサーチ)
・futility cut
・βカット
・hash cut
ボナンザのコンパイル方法:bonanza.htm
何かあれば、gou_koutaki@twitter に連絡ください。