AI解説
Re-va-ruにおけるAIルーチンは、パターン認識とミニマックス法を基本にしています。
パターン認識
Re-ve-ru のAIで使用している思考ルーチンです。局所的な石の形から形勢を判断します。
石の配置を３進数８桁（=10進数6561通り）の数値で表し、予め用意された期待値（勝率）を呼び出します。
36箇所のパターンを判定し、それらの合計値が最終的な形勢判断値となります。
形勢判断
AIを動かすためには、とある局面に対して、黒白どちらが優勢なのかを判断する必要があります。
終局している場合は石の数を比較すれば良いのですが、それがそのまま中盤の優劣基準になるとは限りません。
優劣を決めるポイントになり得る項目を列挙すると、
石の数
次に相手が置ける場所の数
４隅を占めている石の数
ひっくり返りやすさ（開放度）
絶対に裏返ることのない石（確定石）の数
などが挙げられます。複数の要素が複雑に絡み合うため、強いAIへの調整は簡単ではありません。
パターン認識には上述したポイントが内包されているため、精度の高い形勢判断が可能です。
また、パターン認識は処理が簡単なため、思考時間の短縮にも一役買っています。
使用するパターンとして、以下の10通りのパターンを使用しています。
ここまでで、盤面を評価することができました。しかし、これだけではAIは動作しません。
評価した多数の手のうち、どの手を採用するかを判断しなければなりません。
re-va-ruのAIでは、広範に使われているミニマックス法を使用して着手を選択しています。
ミニマックス法
ミニマックス法とは”自分も相手もミスをしない”という前提での最良手を判断する方法です。
自分の手番（赤線）では
数値が最大になる手を選択し、相手の手番（青線）では数値が最小になる手を選択すると仮定します。
左側には13，15，8の数値が並んでいますが、相手は最小値である８を選択します。
一方、右側を調べてみると、
４を選択することが分かります。
よって、自分が左を選んだら期待値は８、右側を選んだ場合は４になります。
左側を選んだほうが数値が大きいので、左側に進むのが合理的だと分かります。
以上より、相手が最善手を打つのであれば左側を選択する方が得であるということが分かりました。
なお、ミニマックス法では相手のミスを期待した先読みは行いません。
思考の高速化
ミニマックス法で探索することで、必ず最良手を見つけることができます。しかし、先読み手数を増やしていくにつれ、
探索に必要な時間も爆発的に増えていきます。リバーシの場合、１手を読むごとに探索数は10倍に膨れ上がり、８手先に
なると1000万局面を探索しなければなりません。これだけの局面を探索することは非現実的です。
AIの思考時間が限られているとき、アルファベータ法（αβ法）を用いると大幅な時間短縮を実現することができます。
αβ法は不要な探索を省略する方法であり、探索の精度が劣化することはありません。ミニマックス法と同じ結果を得る
にも関わらず、思考速度を100倍以上に高速化することができます。
αβ法
先ほどと同じ局面です。左側の探索は終了し、期待値８を得ることが判明しました。
現在右側の探索を行っているのですが、”？”がついた２箇所は探索する必要が無いことを説明します。
右側に進んだ場合、相手プレイヤーは６と”？”の中から低い値を選ぶのです。
”？”の値が６より大きい場合、既に判明している６が選択されます。
一方”？”が６より小さい場合、”？”が採用されます。
つまり”？”の値に関わらず右側の期待値は６以下となります。
そのため、８より大きな値になる可能性はありません。
よって、右側を調べるまでもなく左側が良手であることが確定するのです。
今回の例では２箇所の探索を省略し、33％の高速化を実現することができます。
実際の対局では省略できる選択肢はさらに増え、８手先まで読む場合は100倍以上の高速化が実現できます。
その他の高速化方法
上述したαβ法に加えて、着手リストの導入、コンパイラの最適化、細部の微調整を行った結果、
探索速度を初期の500倍にまで高速化することができた。