日本のチェスをプレイするためのAIの構築における機械学習の使用（将gi）

良い一日。

かなり長い間、友人のゴルコフと私は将giをするのが好きでした 。 そして私たちはあまりにも夢中になったので、この素晴らしいゲームのために独自のボットを書くことにしました。 この記事は、ボット開発プロセスの詳細な説明です。ボット開発プロセスは、いくつかの中断を伴いながら、数か月間行われてきました。

アルファベータクリッピングについて、または動きをソートすることが重要である理由

チェス（伝統的および日本語）、チェッカー、三目並べなどの拮抗ゲームでどの動きを行うかを決定するために、アルファ-ベータクリッピングと呼ばれる最適化を伴うミニマックス戦略が使用されます。
このアルゴリズムは、私の友人の記事と他の記事の両方で、Habréで繰り返し検討されました。
次の写真でその本質を簡単に思い出します。



四角の数字は、対応する一連の動きを行った後の位置の評価を示します。

この例では、ノードがクリップされ、その値には疑問符が付けられています。
ノードbの値を計算する式を作成することにより、このようなカットオフの有効性を検証できます。

b =最小（c、d）=最小（最大（4,6）、最大（7、X））

明らかに、式max（7、X）は7以上であるため、この式の値はXに依存しません。したがって、 max（4,6）より大きく、 bの値はb = 6に等しくなります。

したがって、アルファ-ベータクリッピングアルゴリズムにより、既に取得されているものよりも意図的に悪い結果を与えるブランチを考慮しないことが可能になります。
したがって、最初のより有望な動きを考慮すると、アルゴリズムが加速されます。 どの動きがより有望かを判断することが、この記事の目的です。

仮説

ゲームでは、特定の動きを考慮する必要がないことは人にとってしばしば明らかです。 たとえば、対戦相手がルークを攻撃した瞬間にボードの端に立っているポーンを移動するには。
コンピューターの場合、「明白な」という概念は存在しません。すべての可能な動きを順番にチェックし、その後、ボートを食べることが正しい決定であると結論付けます。
何らかの方法で、ルークのキャプチャが最初に考慮されるように移動の考慮が順序付けされている場合、アルファ-ベータカットオフアルゴリズムはすぐに終了し、ルークを取るときよりも明らかに評価が悪いブランチをすべて破棄します。

この例では、移動の考慮の順序のヒューリスティックな選択の特別なケースが考慮されており、プログラムで個別に使用することはほとんどできません。 特殊なケースのセットを手動で説明するのは非常に面倒で、さらに、ルークが攻撃を受けているオプションの一部のサブセットでは、ポーンの動きが唯一の正しいものになる可能性が常にあります。

これは、すでにプレイされたゲームから有望な動きに関する情報を自動的に取得する可能性のアイデアが出てくるところです。 この場合、機械学習法の使用は、同様のパラメーター（以下のパラメーターについて）で移動すると同様の結果が得られるという仮説によって正当化されます。

トレーニングサンプル

機械学習を使用するときに解決する必要がある最初の質問は、トレーニングサンプルを取得することです。これにより、動作の品質が決定されます。
奇妙なことに、通常のチェスと比較して将giの人気が劣っていたにもかかわらず、これは最小の問題であることが判明しました。

ウェブ上にはplayok.comがあり、他のプレイヤーとさまざまなボードゲームを無料でプレイする機会を提供しています。 提供されるゲームの中には将areがあります。 さらに、このサイトでプレイされるすべてのゲームはkifu形式で保存され、パブリックドメインにあるため、必要な数のゲームをダウンロードする簡単なスクリプトを作成できます。

このサイトに保存されているゲームの数は非常に多い（数百万）ので、ゲームとムーブのパラメーターのローカルストレージ用のデータベースを作成することにしました。
データベースを操作するプロセスでは、パーティ番号ごとの移動を取得するために多数の操作が必要になるため、このようなデータを保存するタスクはそれほど簡単ではありません。
つまり SQLの場合、数百万行を含むテーブルから数十行の選択。
MongoDBなどのNoSQLデータベースを使用する可能性を検討しました。 NoSQLの場合、そのような操作は単純なポインタージャンプに要約されます。 このNoSQLの利点にもかかわらず、現在の実装ではPostgreSQLが使用されており、移動テーブルにはバッチ番号によるインデックスがあります。

playok.comからバッチをダウンロードしてデータベースに入力するスクリプト、およびデータを準備するスクリプト（つまり、実行時間が重要ではない関数）は、Rubyで記述されています。 この言語は、高速のコード記述を提供し、データベースを操作するために必要なすべてのコンポーネントも備えています。 ソースコードへのリンクは、記事の最後に記載されています。

動きの説明について

機械学習手法の適用を可能にするには、一連の機能を使用して各動きを記述する必要があります。 奇妙に思えるかもしれませんが、そのような記述はオブジェクトの機能記述と呼ばれます。

特性記述は値のベクトルであり、値のベクトルは属性空間内のポイントの座標です。
たとえば、ボックスの寸法と重量は、説明として役立つ場合があります。 したがって、2 x 3 x 1メートルで重量が10キログラムの箱には、標識の4次元空間に特徴の説明（2,3,1,10）があります。

異なる当事者の指定による同じ動き（e2e4）が反対の結果につながる可能性があるという事実のため、動きの特徴的な説明にボード上の他の人物の位置に関する情報を含む標識を含める必要があります。
標識の場合、トレーニングセットでは黒と白の両方の動きが良いため、動きをした部分の色に関する不変性を観察する必要があります。 たとえば、移動の水平方向の数は、開始位置までの水平線の数に置き換える方が適切です（この場合、黒は水平9から始まり、白は水平1から始まると考えられています）。

使用される特性記述のバリアントは、以下のパラメーターで構成されています。

分類アルゴリズムの選択について

問題の記述は、動きを有望なものとそうでないもの（良いものと悪いもの）に分類することを意味しますが、アルゴリズムにはいくつかの追加条件も課されます。

• 動きを最高から最低にランク付けすることが可能であるべきです。
• ツリーを表示する各段階で分類（およびソート）を行う必要があるため、高速を確保する必要があります。

分類アルゴリズムの中では、 最近傍法がタスクに適しています。
この方法は、属性空間で分類されたオブジェクトに最も近いクラスのオブジェクトが誰であるかを判断することで構成されます。
この方法は、検討中の2つの動きのうちどちらが良いかを自然に決定するため、優れています。 これを行うには、距離を最も近い隣人と比較するだけで十分です。
ただし、この方法には重大な欠点もあります。最も近いオブジェクトが見つかったと主張する前に、多数のオブジェクトをチェックする必要があります。

この問題を解決する1つの方法は、クラスタリングを使用することです。
開始点のセットをクラスターの中心である点のセットで置き換えると、オブジェクトの分類に必要な操作の数が大幅に削減されます。 このような置換は明らかに分類の品質を低下させ、出力セットにあるクラスターが少ないほど品質が低下します。 したがって、クラスターの数は、精度と速度の間の妥協を反映する値です。

動きの選択について

当事者の処理に進む前に、どの動きが良いと見なされ、どの動きが私たちのベースとして悪いと判断する必要があります。 いくつかのオプションがすぐに思い浮かびます：

• 物質的な優位性をもたらした動き。
• マットにつながった動き。
• 高評価のプレーヤーが移動します。

少し考えてみると、最初と2番目のオプションが良いことを保証されていないことが明らかになります。
第一に、強い人物の犠牲者がその後犠牲者を受け入れたプレーヤーの損失につながるプレーヤーがいる状況があるからです。
第二に、負けているプレイヤーの不注意のためにチェックメイトを置くことができます。これは非常に頻繁に起こります。
レーティングが高いプレーヤーがゲームに勝った場合、彼は明白に愚かな動きをしなかったと言うことができます（あくびは十分なレベルで敗北につながることが保証されています）、私たちのタスクは、特定の状況で絶対に正確な動きを確立しないことです、ソートは平均して品質で移動します。
上記の議論に基づいて、私たちは問題を解決するために当局を信頼する必要があると考えています。

現在の実装では、移動は次のように選択されます。

• 下限と上限の評価しきい値が設定されます。
• 勝者の評価が上限のしきい値より高い各ゲームで、勝者の動きの最後の2/3が選択され、良好としてマークされます。
• 評価が下限しきい値以下の各ゲームでは、敗者の最後の2/3の動きが選択され、悪いとマークされます。

最初の動きのスクリーニングは、パーティーのデビューには他のより効果的なアルゴリズムがあり、その考慮は記事の範囲を超えているという事実によって正当化されます。

クラスタリングについて

ゲームツリーを表示する各ステップで実行する必要のある分類とは対照的に、この場合、クラスタリングに対する要件はそれほど厳しくありません。
まず、クラスタリングは1回だけ行う必要があります。これにより、ゲームの時点で必要な時間よりも多くの時間を必要とするアルゴリズムを使用する権利が与えられます。

クラスタリングタスク自体は明確に定式化されていないため、解釈の多くのオプションが提供されます。 次の定義を使用します。

クラスタリングとは、クラスター内のオブジェクト間の距離を最小化し、クラスター間の距離を最大化するような方法で、オブジェクトのセットを互いに素なセット（クラスター）に分割することです。

正式には、この定義は次のように記述できます。


ここで、 K _y-番号yのクラスター
p（x、y）は、指定されたメトリックで距離を決定する関数です
μyは、番号yのクラスターの中心です。
x _i-番号iのオブジェクト

私の実装では、k-meansクラスタリングアルゴリズムを使用しました;詳細な説明は、たとえばWikipediaにあります。
アルゴリズムの特徴は、クラスターへの初期パーティションとしてランダムな値を使用することです。その選択は、さらにパーティション化の結果に強く影響します。これにより、より良い結果を達成するためにクラスタリングを繰り返し実行することが可能になり、この段階での実行時間に制限されません。

たとえば、2次元空間でのランダムポイントのクラスタリングは次のようになります。





クラスタリングの結果として、特徴空間での良い動きと悪い動きのクラスターの中心であるN （私はN = 20を選択しました）ポイントを取得します。
これらのポイントまでの距離は、表示の動きの順序を並べ替えるときに使用されます。

分類について

元のベースに比べてポイントの数が大幅に少なくなったので、これらのポイントへの近接度に基づいて並べ替えを適用できます。

前の段階と同様に、選択の余地があります。 つまり、クラスターまでの距離が計算されるメトリックの選択。
点の座標間の相関を考慮して、通常のユークリッドメトリックとマハラノビスメトリックの両方を適用できます。



どのメトリックが優れており、どのパラメータが別の非常に難しい質問であるので、最初は単純なバージョンであるユークリッドメトリックに焦点を当てます。

移動の並べ替えに使用する値は、次を選択します： （（悪い移動の最も近いクラスターまでの距離）-（良い移動の最も近いクラスターまでの距離）） 。
したがって、示された移動の値が大きいほど、ゲームツリーを構築するときにそれをより早く考慮する必要があります。
他の式を使用して、コースの推定値、たとえば、良い動きのクラスターまでの平均距離などを取得することもできます。

結果

説明した方法の有効性を評価する主な基準は、アルファベータクリッピングプロシージャの再帰呼び出しの数でした。この基準は実装に依存しないため、最も客観的であるためです。
実験により、この方法の有効性はボード上の状況に大きく依存することが示されています。 分類器は実際のゲームで訓練されているため、これは驚くことではありません。したがって、人工的に構築された問題を解決する効果は、攻撃されたピースの重量で動きをソートする単純なヒューリスティックの場合よりもかなり低くなる可能性があります。

メソッドの欠点

• 長い間。

最も近いポイントを計算するプロセスでは、実数による演算が使用され、ゲームツリーの表示時間が大幅に増加します。

• 限られたアプリケーション。

上記のように、状況によっては、機械学習法は単純なヒューリスティックよりも悪い結果をもたらす場合があります。

改善する可能な方法

たとえば、 マンハッタン距離を使用して、材料操作を取り除くことができます。
クラスターの数を減らすことにより、重要なトランザクションの数を減らすこともできます。 このような削減は精度の低下につながり、その結果、アルファベータクリッピングアルゴリズムのパフォーマンスが低下し、動作時間が長くなります。 したがって、理想的には、このパラメーターの最適化問題を解決する必要があります。

機械学習のヒューリスティックの適用可能性の問題を解決するために、次の改善が可能です。

• ボード上の状況のコンテキストでの動きの検討。これには、数字の相互作用のグラフの構築と、このグラフの情報を動きのパラメーターに追加することが含まれます。
• ボード上のさまざまな種類のポジションに異なるクラスターオプションを作成し（攻撃戦略の場合、防御戦略の場合など、ピースの数に応じて）、ゲームの状況に応じて1つまたは別のクラスターセットを適用します。

参考文献と文献

• 機械学習については、K.V。Vorontsovによる素晴らしい講義コースがあります。そこから、使用された方法に関する情報を得ました。 彼の講義は最近Habrに投稿されました。
• Javaで記述されたボット自体のあるリポジトリ： https : //github.com/gorkoff/Shogi/tree/DataMining
• Rubyスクリプトをサポートするリポジトリ： https : //github.com/generall/ScriptsForShogi

ご清聴ありがとうございました。