コンピューター将棋の構造 - 合法手生成

コンピューター将棋の評価関数はよく話題にも上りますがそれを支えるのが合法手生成モジュール(move generator)です。

その分担は「ある局面から手番に応じて合法手のリストを製作」…とまあ何とも地味な存在です。これは誰がやってもおなじ結果になりますので(でないと困る)、いかに短時間に処理できるかがポイントになります。当然反則手(例・二歩)は除去しなければなりません。

超例外として連続王手での千日手は反則ですがこれは(我は)別のところで処理します。

以下の数字は無明の合法手生成ベンチマークです。初期盤面から先手の合法手生成(30手)を一万回繰り返しました。現実的ではありませんがスピードを計るにはこれでよしとします。

MOVES: 3000000
TIME: 4.829000
RATE: 621246.634914 moves/sec
RATE: 1.6096666666666666E-6 sec/move

3百万手を生成するのに4.83秒…一秒当たり62万手生成しています。これはCPU一つだけ使用の結果なので並列化(2個以上のCPUを使う)すれば更に引き上げられます。「二人で頑張れば出来高2倍」が(完全ではないが)通用する世界です。

前に「合法手生成モジュールは一日で書ける」と書きましたが、やはり「単純なものほど奥が深い」ようでして…誕生当時は一秒当たり20万手のスピードでした。コツコツと血を吐く思いをして(ウソツケー)ここまで引き上げることができました。これが他の将棋ソフトと比較してどの程度なのかは調べていませんが、

http://www.geocities.jp/bonanza_shogi/

『Bonanza Version 1.0 の性能を列挙します....* 現在の家庭用 PC における思考の速さ約 30 万局面/1秒』

「30 万局面/1秒」は局面評価込みのスピードなので比較はできませんが、ギリギリ十分なのではないかと思われます。(もっと速くする陰謀進行中)

一秒当たり62万手生成…これってどの程度有効な速さなのでしょうか?

イワユル「三手の読み」には...

持ち駒が有る局面には候補手が増え、序盤には少ないので一概には決められませんが…100候補手がある局面を仮定します(計算が楽だから)。

1手目 100候補手
2手目* 100 x 100 = 10000候補手

*1手目の100候補手のそれぞれが100候補手に枝分かれします。以下同様。

3手目 100 x 100 x 100 = 1000000候補手

総合して 100 + 10000 + 1000000 = 1010100手掛かります。

これを先ほどの62万で割り算すると、

1010100 / 620000 = 1.629秒…なんとか及第。

少し欲をだして五手まで頑張ると、

4手目 100^4 = 100000000候補手
5手目 100^5 = 10000000000候補手

総合して 10101010100

…ととんでもない数字になります。

62万で割り算すると、10101010100 / 620000 = 16291.95秒程掛かります。

分に直すと 16291.95/60 = 271.5325分...4時間超となり評価関数を持ち出すまでも無く「使えません」。

(結論)しらみつぶしでの検索方法はいくら時間があっても足りません。

(続)

投稿者: 紫外線 投稿日時: 日, 07/05/2009 - 13:03 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

私がボナちゃんに勝ったのは・・・

完全に「偶然であった」のかもしれませんね・・・

昔のコンピュータ将棋は、とにかく弱くて長考しました。一手に30分以上考えることがほとんどで、しかも弱かった。

90年代半ば以降でしょうか、しばらく将棋から遠ざかっていた私は驚きました。早くて強くなっていました。 どこかで突然強くなったという印象があるのですが、これはコンピュータの性能によるところも大きいのでしょうか?

注; 酔っ払いの独り言なので、詳しく反応なさらなくてもいいですよ~

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。