euphonictechnologies’s diary

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

follow us in feedly

Haskellで将棋 - 探索と指し手生成の改善について考える

Haskell コンピュータ将棋

現状のコード

現状の探索と指し手生成は、実際にコードを見るほうが早いので早速見てみると

Search.hs:

minmax :: Int -> Board.Bd -> Result
minmax 0 bd = Result (Eval.eval bd) []
minmax dep bd = maximumBy (compare `on` va) nexts
    where
        nexts = map next $ MoveGenerator.mvGenFull bd
        next mv = conv mv . minmax (dep - 1) $ Board.bdDo bd mv

Move.hs

mvGenFull :: Board.Bd -> [Move.Mv]
mvGenFull bd = allInNoCheck bd ++ dropMvs bd

という感じで、ものすごく素朴だ。指し手を（合法手じゃない合法手も含めて:前回記事を参考）すべて生成するので、ものすごく効率が悪い。Wikipediaも

ミニマックス法はすべての局面に対してしらみつぶしに探索を行うため、実際には読む必要のない（評価しなくても支障がない）手も読むことになり探索効率が悪い。ミニマックス法 - Wikipedia

といっている。私もそう思う。 改善について考えてみる。

Bonanzaはどうやってるのか

優れたソフトウェアを参考にするのが手っ取り早い。 Bonanzaの開発者、保木氏のスライドを見ると、

力任せの探索は簡単・高性能！

Minimax法 : 80^n

Minimax法 + beat cut : (\sqrt{80})^n = 8.9^n

Minimax法 + beat cut + null move pruning や hash cut : (\frac{1}{4}\sqrt{80})^n = 8.9^n

Minimax法 + beat cut + null move pruning や hash cut + Futility pruning : \frac{1}{4}(\frac{1}{4}\sqrt{80})^n = \frac{1}{4} 2.23^n

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

(レイアウトの崩れ等はご容赦ください。正確には原文参照)

という感じで、minimaxを枝刈りしていくとどんどん良くなっていく。

とりあえず最初は野望を小さく、beta cutを導入してみるところを目指してみたい。

アルファ・ベータ法

ゲーム木における分枝限定法だ。分枝限定法はたとえば巡回セールスマン問題なんかを解くのに使われるアルゴリズムだ。 巡回セールスマン問題とは、典型的なNP問題のひとつで

都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。 巡回セールスマン問題 - Wikipedia

という問題だ : Traveling Salesman Problem -- from Wolfram MathWorld

一筆書きでグラフをなぞって一番距離が短くなるようにするなぞり方はどういうものか？と言うのはNP困難問題だ。 この問題を解くときに、辿る都市をツリー上に展開していく。一つの末端ノードまでの道が存在する、ということはとりあえず一筆書きで辿れるルートが有るということ。当然そのルートでたどった時の合計距離が得られているはずだ。

このページでGoogle Mapを使って遊ぶことができるようだ : Die schnellste Route durch Oberhessen

たとえば別の都市を選びながら半分ほどたどったところでさっき完成した一つの一筆書きの距離をすでに上回っている場合、このたどり方はこの先どうやっても答えになることはない、のでもうこのたどり方は「ダメ」のシールを張って封印しておいてよい。これが分枝限定法。早めに非常によい距離の上限を得ておくと、無駄なたどり方をバッサリとカットできるので、そこが肝になる。分枝限定法はたいてい答えの上限を別の方法で探しておいてから始めることが多い（たとえば別の近似解法を当てはめてそこそこ良い答えを予め得ておくとか、グラフとか問題の性質を利用してこれ以上にはならないという数字を得ておくとか : LKH (Keld Helsgaun)）。

アルファ・ベータ法もこれと一緒だ。

アルファ・ベータ法の場合は答えの上限だけでなく、下限も必要だ。つまり、敵の答えの上限と、自分の答えの下限。なので2つのアルファとベータをつかって範囲を絞りながら探すのが良い、というだけ。

分枝限定法と同じように、予めあまり意味のない手をバッサリとカットできるようなアルファとベータを得ておくのが良い枝刈りをするコツだ。

現状のように闇雲にすべての指し手を生成してアルファ・ベータ法を適用するよりは（当然minimaxよりは効率は良いが）、ある程度生成する指し手について戦略を持って展開するのが肝要だ。

で、Bonanzaはどうやっているのか。

2009-11-08 - Bonanzaソース完全解析ブログ によるとBonanzaは

1) は駒を捕獲しない指し手(generate no captures)

2) は駒を捕獲する指し手(generate catures)

3)は駒を打つ手(generate drop)

4)は王手になる手(generate check)

5)は王手を回避する手(generate evasion)

と5つのルーチンを持っているそうだ。1と2と3は互いにmutual exclusiveな手を生成するため1 + 2 + 3ですべての指し手になっているとのこと。ここで1と2はさらに盤面の評価値をそれほど変動させない手（駒を取らないものの中でも大駒の成りは生成しないとか）と盤面の評価値を大きく動かすことが予想される手（駒を取る手と大駒の成り）を生成するそうだ。

この戦略はぜひ採用したい。まず2を生成して探索を始める。そこで枝刈りが発生すれば駒を打つ手と駒を捕獲する手は評価しなくても良いはずだ。2によって良いアルファとベータを得ることによって1と3の指し手をバッサリとカットできるという目論見がある。

さらに

2でまずすべてを生成するよりは、2をcoroutineのように使って(PythonやRubyでいうジェネレータ、yieldみたいな感じ)、必要な指し手だけを生成して行くことによって更に無駄な手の展開を減らすことができそうだ (参考:将棋プログラムに何故coroutineが必要なのか - Bonanzaソース完全解析ブログ、2011-12-15 - Bonanzaソース完全解析ブログ)。 Haskellの利点がここで生きてくる。coroutineとか、conduitとか、streamとか、Extensible Effects はモナド変換子に対する救世主になり得るか？ - konn-san.comとか、その手の枠組には事欠かない。ただ野心的なことは後回しにして、とりあえず、指し手を1と2と3で生成を分けるところまでにして、その後のことを考えることにする。

つまり、次やることは？

指し手生成関数の部分をbreakdownすること。生成関数をいじるのでまずはテストを書いて生成が正しくできていることを証明しよう。