【リバーシプログラム】ムーブオーダリングについて考える

こんにちは～。

突然、落ちついていたリバーシプログラム熱が再燃したかけるです！

はじめに

今回も探索効率の更なる向上を目指すべく、次なる一手としてムーブオーダリングについて考える。

探索の効率を向上させるためには、とにかく枝刈りの量を多くする必要があります。

Alpha-Beta法による探索はその性質上、評価値がより高いと思われる手から先に探索することで枝刈りの量を増やすことができます。

このように枝刈りの量を増やすため、探索の順番を決めることをムーブオーダリングといいます。

前回まではwhile文を用いてA1→A2→…→H8と盤面を左上から右下に向かって探索する実装だったが、ひとまず今回は以下の順で優先度をつけて探索するようにした。

隅(A1, A8, H1, H8)
B打ち(A3, A6, C1, C8, F1, F8, H3, F6)
A打ち(A4, A5, D1, D8, E1, E8, H4, H5)
ボックス隅(C3, C6, F3, F6)
ボックス辺(C4, C5, D3, D6, E3, E6, F4, F5)
中辺(B3, B4, B5, B6, C2, C7, D2, D7, E2, E7, F2, F7, G3, G4, G5, G6)
C打ち(A2, A7, B1, B8, G1, G8, H2, H7)
X打ち(B2, B7, G2, G7)

順番の決め方は極めて単純で「隅を最優先」「隅に隣接する手は悪手」といったような経験則に基づいたものとした。

今回も参考がてら、改善効果のほどを以下に示します。

今回、探索順序について深く考察したわけではないが、上記のような単純な変更だけでも十分すぎるくらいの改善が得られている。

上記の表には出していないが、20手目だと約967.7億→110.8億と大幅に改善できている。ただ、それでも完全探索には程遠いわけですが……。

浅い考えで決めた探索順序でもこれだけの改善が得られた以上、然るべき方法で探索順序を決定したときの改善効果は十分に期待できそう。

究極はムーブオーダリングによって最善な一手を真っ先に探索することであり、それが可能となれば探索の効率も最高となる。

問題はその探索順をどうやって決めるのが良いのか。まだまだ課題は多い……。