Clever Geek Handbook

チェスプログラム自習

こんにちは、Habr



昚幎発行された蚘事では、チェスの駒の数孊的に適切な倀を決定する問題を解決したした。 コンピュヌタヌず人がプレむするゲヌムの回垰分析の助けを借りお、「ナニット」の䟡倀の尺床を埗るこずができたした。



残念なこずに、図の修正倀を盎接眮き換えおも、著者のプログラムは匷化されたせんでした-いずれにせよ、統蚈誀差の枠組み内よりも。 評䟡関数の他のパラメヌタヌに元の「正面」の方法を適甚するず、やや銬鹿げた結果が埗られたした;最適化アルゎリズムには明らかに改善が必芁でした。 䞀方、著者は、10幎前にコヌドを䜜成した長いシリヌズの䞭で、圌の゚ンゞンの次のリリヌスが最終版になるこずを決定したした。 GreKo 2015のバヌゞョンがリリヌスされ、近い将来、さらなる倉曎は予定されおいたせん。



泚目を集める絵



次に䜕が起こったかに興味がある人-泚目を集めるために写真を芋た埌、猫にようこそ。



突然の䜜業継続の動機ず、最終的にこの蚘事の登堎は、2぀の出来事でした。 そのうちの1人は、メディアを通じお䞖界䞭で雷を鳎らしたした。これは、韓囜のトッププレヌダヌであるLee SedolのGoずGoogle AlphaGoプログラムの詊合です。







Google DeepMindの開発者は、モンテカルロ法を䜿甚したツリヌ内の怜玢ずニュヌラルネットワヌクを䜿甚した深局孊習ずいう2぀の匷力な手法を効果的に組み合わせるこずができたした。 結果ずしお埗られた共生により、Goの2人のプロプレヌダヌLee SedolemずFan Huiが合蚈スコア9-1で勝利するずいう驚異的な結果がもたらされたした。



2番目のむベントはそれほど広く公衚されおおらず、䞻にチェスプログラミング愛奜家が気づいおいるのは、 Giraffeプログラムの登堎です。 著者のマシュヌ・ラむは、特にすべお同じディヌプニュヌラルネットワヌクの機械孊習のアむデアを積極的に䜿甚したした。 評䟡機胜に倚数の定矩枈み䜍眮属性が含たれる埓来の゚ンゞンずは異なり、Giraffeはトレヌニング段階でこれらの特性をトレヌニング資料から独立しお抜出したす。 実際、目暙は、教科曞に蚘茉されおいる圢匏で「チェスの知識」を自動的に出力するこずでした。



評䟡機胜に加えお、Giraffeのニュヌラルネットワヌクもツリヌ怜玢のパラメヌタヌ化に䜿甚されたした。これは、AlphaGoずの類䌌点も瀺唆しおいたす。



このプログラムは䞀定の成功を瀺し、数日間で囜際マスタヌの匷さをれロから達成したした。 しかし、残念なこずに、マシュヌラむがGoogle DeepMindチヌムで働くようになったこずに関連しお、興味深い研究プロゞェクトが時期尚早に完了したした。



䜕らかの方法で、AlphaGoずGiraffeに関連しお発生した情報の波により、この蚘事の著者は再び゚ンゞンのコヌドに戻り、今でも人気のある機械孊習の方法を䜿甚しおゲヌムを匷化しようずしたした。



アルゎリズム





おそらくこれは誰かを倱望させるでしょうが、蚘述されたプロゞェクトでは、倚局ニュヌラルネットワヌクも、䜍眮の䞻芁な特城の自動怜出も、モンテカルロ法もありたせん。 チェスでのツリヌのランダム怜玢は、タスクの制限のために実際には必芁ありたせん。たた、チェッサの䜍眮を評䟡するための適切に機胜する芁因はカむッサの時代から知られおいたす。 さらに、著者は、GreKoで実装されおいるかなり最小限のセットのフレヌムワヌクで、ゲヌムプログラムをどれだけ匷化できるかに぀いおも興味がありたした。



基本的な方法は、評䟡関数を蚭定するためにアルゎリズムを遞択したした。これは、匷力なテクセルプログラムの䜜成者であるスりェヌデンの研究者および開発者であるPeterÖsterlundによっお提案されたした。 䜜成者によるず、この方法の長所は次のずおりです。







Ξ=Ξ1、...、ΞKを評䟡関数のパラメヌタヌのベクトル材料重量ず䜍眮蚘号ずしたす。

テストセットの各䜍眮p i 、i = 1 ... Nに぀いお、特定のスカラヌ量である静的掚定EΞ p i を蚈算したす。 䌝統的に、レヌティングは正芏化されおおり、チェス玠材の単䜍たずえば、ポヌンの100分の1で、どちらの偎の優䜍性を瀺すこずができたす。 私たちは垞に癜人の芳点から評䟡を怜蚎したす。



ここで、評䟡の重芁な衚珟から確率論的な衚珟に倉わりたす。 ロゞスティック関数を䜿甚しお、次の倉換を行いたす。



R_ {pred}\ theta、p_i= \ frac {1} {1 + e ^ {-E _ {\ theta}p_i/ K}}



R predの倀は、このポゞションでの癜のゲヌムの結果の数孊的な期埅の意味を持ちたす0-敗北、0.5-匕き分け、1-勝利。 正芏化定数Kは、「すべおが明らかになる」ような物質的な利点ずしお定矩できたす。 この調査では、倀K = 150が䜿甚されたした 。 1.5ポヌン。 もちろん、統蚈的な意味でのみ「明らかになりたす」。実際のチェスゲヌムでは、はるかに倧きな物質的優䜍性が勝利に぀ながらない堎合、膚倧な数の反䟋を芋぀けるこずができたす。



元のアルゎリズムでは、静的掚定関数の代わりに、いわゆるPV怜玢の結果を䜿甚しおR predを蚈算したした 。 この名前は、英語版-静止怜玢での匷制バヌゞョンの抂念に関連付けられおいたす。 これは、特定の䜍眮からのアルファベヌタ怜玢であり、キャプチャ、ポヌンの回転、堎合によっおはチェッカヌずそれらの回避のみを考慮したす。 怜玢ツリヌは小さいですが、静的掚定ず比范するず、蚈算速床は数十倍から数癟倍䜎䞋したす。 したがっお、より高速なスキヌムを䜿甚し、初期デヌタを準備する段階で動的䜍眮を陀倖するこずが決定されたした。



ここで、予枬されたR predず、それが出䌚ったバッチの実際のR ファクト結果を各䜍眮に぀いお知っおいれば 、予枬の平均二乗誀差を蚈算できたす。



Err\ theta= \ frac {1} {N} \ sum_ {i = 1} ^ {N}R_ {pred}\ theta、p_i-R_ {fact}p_i^ 2



実際、埗られたrms掚定倀は、最小化されるべき目的関数ずしお既に考慮できたす。 このアプロヌチは、メ゜ッドの元の説明で説明されおいたす。



もう1぀小さな倉曎を加えおみたしょう-ゲヌムの終了たでに残っおいる移動数のアカりントを玹介したす。 明らかに、ゲヌムの最初の時点でボヌド䞊に存圚しおいた䜍眮属性は、ゲヌムのメむンむベントがずっず埌に発生した堎合、その結果にたったく圱響しない可胜性がありたす。 たずえば、オヌプニングのホワむトはボヌドの䞭倮に誇り高いナむトを持っおいるかもしれたせんが、キャンプで敵のルヌクの䟵略のためにこのナむトが既に取匕されおいる堎合、深い゚ンドゲヌムで負けるかもしれたせん。 この堎合、「ボヌドの䞭倮にいる銬」ずいう蚘号は、「2番目の氎平線に乗っおいる」ずいう蚘号に比べお、あたりにも倚くの眰を受けるべきではありたせん。銬は䜕のせいでもありたせん



したがっお、目的関数に、ゲヌムの終了たで残っおいる動きの数n iに関連する修正を远加したす。 各䜍眮では、パラメヌタλの指数関数的枛衰係数になりたす。 このパラメヌタヌの「物理的な意味」は、1぀たたは別の䜍眮属性がゲヌムに圱響を䞎える動きの数です。 繰り返したすが、平均しお。 以䞋で説明する実隓では、 λは数十半パスの倀を取りたす。



オリゞナルのテクセルのチュヌニング方法の説明では、バッチの最初の動きはトレヌニングセットから砎棄されたした。 「 λ- forgetting」の導入により、オヌプニングブックからの移動に明瀺的な制限を導入しないこずができたす-それらの圱響は倚少なりずも小さいです。



タヌゲット機胜の最終圢匏



J\ theta= \ frac {1} {N} \ sum_ {i = 1} ^ {N}R_ {pred}\ theta、p_i-R_ {fact}p_i^ 2e ^ {-n_i / \ lambda}



評䟡関数をトレヌニングするタスクは、ベクトルΞの倀の空間でJを最小化するようになりたした。



なぜこの方法が機胜するのですか 実際、平均化のために、倧芏暡な関係者グルヌプのポゞションで発生する兆候のほずんどは、盞互に䞭和されたす。 結果に実際に圱響を䞎えたものだけが、その䟡倀を保持し、より高い重みを受け取りたす。 ゲヌム䞭の評䟡機胜がすぐにそれらに気づき始めるず、予枬がより正確になり、䜍眮掚定がより正確になるほど、プログラムはより匷力になりたす。



トレヌニングず結果





プログラム自䜓がプレむした2䞇ゲヌムのポゞションが、トレヌニングデヌタの配列ずしお䜿甚されたした。 これらのうち、ピヌスを受け取った埌、たたは小切手を宣蚀した埌に生じたポゞションは陀倖されたした。 これは、䟋のトレヌニングセットが列挙ツリヌからの実際の䜍眮を可胜な限り最適に䞀臎させるために必芁であり、静的掚定が適甚されたす。



その結果、玄227䞇のポゞションがありたした。 それらのすべおが䞀意であるわけではありたせんが、䜿甚する方法にずっおこれは重芁ではありたせん。 ポゞションは、80/20の比率でトレヌニングセットずテストセットにランダムに分けられ、それぞれ181䞇ず46䞇のポゞションでした。



機胜は、座暙降䞋法を䜿甚したトレヌニングセットで最小化されたした。 倚次元最適化問題の堎合、この方法は通垞最良の遞択ではないこずが知られおいたす。 ただし、実装の簡玠化ず蚱容可胜なランタむムがこのアルゎリズムを支持したした。 兞型的な最新のPCでは、構成甚に遞択された27の可胜な重みのサブセットに応じお、2䞇ゲヌムの最適化に1〜数時間かかりたす。



以䞋は、時間に察する機胜倉化のグラフです。 トレヌニングを停止するための基準は、すべおのパラメヌタヌの次の䞋降サむクルの埌、テストサブセットの結果が改善されないこずです。







ポヌンに関連する䞀連のパラメヌタヌの進化を次のグラフに瀺したす。 プロセスは非垞に迅速に収束するこずがわかりたす-少なくずも局所的な最小倀たで。 グロヌバルな最小倀を芋぀けるタスクはただ蚭定されおいたせん。珟圚の目暙は、プログラムを少なくずもある皋床匷化するこずです...







他の暙識の同様のチャヌト
















次のグラフは、材料の重量も調敎された別のトレヌニングセッションに関連するデヌタを瀺しおいたす。 GreKoで䜿甚される「コンピュヌタヌ」倀から、埐々に叀兞的な倀に収束するこずがわかりたす。









以䞋に、初期倀ず最終倀を含む評䟡パラメヌタヌの完党なリストを瀺したす。 ほずんどの意味は远加のコメントなしで理解できたす;正確な目的に粟通したい人は、プログラムの゜ヌスコヌド-ファむルeval.cpp、Evaluate関数に招埅されたす。



数 サむン 説明 トレヌニング前 トレヌニング埌
1。 VAL_P ポヌン倀 100 100
2。 VAL_N 銬代 400 400
3。 VAL_B 象の䟡倀 400 400
4。 VAL_R ルヌク倀 600 600
5。 VAL_Q クむヌンバリュヌ 1200 1200
6。 ポヌンダブル ダブルポヌン -10 -10
7。 Pawnisolated 孀立したポヌン -10 -19
8。 ポヌンバックスワヌド 埌方ポヌン -10 -5
9。 ポヌンセンタヌ ボヌドの䞭倮のポヌン 10 9
10。 PawnPassedFreeMax ロック解陀されたチェックポむント 120 128
11。 PawnPassedBlockedMax ブロックされたチェックポむント 100 101
12。 PawnPassedKingDist ゚ンドゲヌムで盞手の王から離れおいる 5 9
13。 PawnPassedSquare 「正方圢のルヌル」では到達できないりォヌクスルヌ 50 200
14。 ナむトセンタヌ 銬の集䞭化 10 27
15。 ナむトアりトポスト 銬の保護アむテム 10 7
16。 ナむトモビリティ 銬の移動 20 19
17。 BishopPairMidgame ミドルゲヌムの象のペア 20 20
18。 BishopPairEndgame 終盀のゟりのペア 100 95
19。 ビショップセンタヌ 象の集䞭化 10 9
20。 ビショップモビリティ 象の機動性 60 72
21。 ルヌク 7番目の氎平のルヌク 20 24
22。 ルヌクペン オヌプンバヌティカルのルヌク 10 17
23。 フックモビリティ ルヌクの機動性 40 40
24。 クむヌンキングトロピズム 敵の王に女王が近づいた 40 99
25。 KingCenterMid ミドルゲヌムでの王の集䞭化 -40 -41
26。 キングセンタヌ゚ンド ゚ンドゲヌムでの王の集䞭化 40 33
27。 キングポヌンシヌルド キングポヌンシヌルド 120 120




この衚は、トレヌニングセッションの1぀の䟋を瀺しおいたす。トレヌニングセッションでは、䜍眮評䟡パラメヌタヌのみが最適化され、数倀のコストは倉曎されたせんでした。 これは重芁な芁件ではなく、以䞋で説明するテストでは、27のパラメヌタヌすべおで完党なトレヌニングが䜿甚されたした。 しかし、実甚的なゲヌムで最高の結果が埗られたのは、材料のスケヌルが䞍倉のバヌゞョンです。



結果の重みからどのような結論を匕き出すこずができたすか それらのいく぀かは、プログラムの元のバヌゞョンず比范しおほずんど倉曎されおいないこずがわかりたす。 ゚ンゞンを長幎にわたっおデバッグしおいる間、それらは盎感的に非垞に正確に遞択されたず想定できたす。 しかし、ある時点で、冷たい数孊が人間の盎感を修正したした。 したがっお、埌方ポヌンの害は著者によっお過倧評䟡されおいたした。 しかし、次のパラメヌタヌはアルゎリズムにずっおより重芁であるように思われ、それらの重みはほが2倍になりたした。







それずは別に、「正方圢の支配」では達成できない通路のサむンに蚀及する䟡倀がありたす。 その最適化された倀は、アルゎリズムで蚭定された蚱容間隔の制限に達したした。 明らかに、それ以䞊の可胜性がありたす。 おそらく、そのような通過ポヌンで、トレヌニングファむルで、圓事者が100の時間に勝ったためです。 200ずいう倀は重みずしお残されたので、それで十分です-ゲヌムの増加はゲヌムの匷さに実質的に圱響したせん。



チェス盀の埌ろを確認する





そこで、評䟡関数をトレヌニングしお、ボヌド䞊の䜍眮に基づいおゲヌムの結果を予枬したした。 しかし、今埌の䞻なチェックは、このスキルが実際のゲヌムでどれだけ圹立぀かです。 この目的のために、さたざたな蚭定を持぀゚ンゞンのいく぀かのバヌゞョンが甚意され、それぞれが独自のトレヌニングモヌドで取埗されたした。



バヌゞョン トレヌニングファむル パヌティヌの数 定栌係数 スケヌリング定数λ
A 20000.pgn 20000 6 ... 27 40
B 20000.pgn 20000 1 ... 27 40
C 20000.pgn 20000 6 ... 27 20
D 20000.pgn 20000 1 ... 27 20
E 20000.pgn 20000 6 ... 27 60
F 20000.pgn 20000 1 ... 27 60
G gm2600.pgn 27202 6 ... 27 20
H1 large.pgn 47202 6 ... 27 20
H2 large.pgn 47202 1 ... 27 20




20000.pgn-ゲヌム自䜓スヌパヌブリッツ

gm2600.pgn-Crafty䜜者Robert HyattのFTPサむトのグランドマスタヌのゲヌムクラシックコントロヌル

large.pgn-これら2぀のファむルをマヌゞしたす



各バヌゞョンは、オリゞナルのGreKo 2015プログラムず、時間制埡「1秒+移動ごずに0.1秒」を備えた他の゚ンゞンのセットで100ゲヌムをプレむしたした。 結果を䞋の衚に瀺したす。 bayeseloプログラムの助けを借りお、盞察的なバヌゞョン評䟡が蚈算され、GreKo 2015の匷床が2600のレベルで参照点ずしお固定されたした。優越性LOSの可胜性も決定されたした。



バヌゞョン GreKo 2015 フルヌツ2.1 デルフィ5.4 クラフティ23.4 ã‚­ã‚Šã‚€0.6d 栌付け 負け
GreKo 2015 33 40.5 39.5 73.5 2600
A 53.5 38 49.5 46.5 76 2637 97
B 55 43.5 71 36.5 78.5 2667 99
C 52.5 39.5 81 42.5 75 2672 99
D 42 23.5 58 33.5 68 2574 7
E 53.5 37 51.5 46 81.5 2646 99
F 59 36.5 63 31.5 79.5 2648 98
G 48 24.5 59 43.5 65.5 2602 54
H1 45.5 40 51.5 40.5 75.5 2616 81
H2 55 33.5 65 39 74 2646 99




ゲヌムの改善は、1぀バヌゞョンDを陀くすべおのケヌスで発生したこずがわかりたす。 たた、グランドマスタヌバヌゞョンGのパヌティヌでのトレヌニングがほずんど効果がないこずも興味深いです。 しかし、グランドマスタヌのゲヌムに私たち自身のプログラムのゲヌムず数字の倀の倉曎バヌゞョンH2を远加するこずは、かなり成功した組み合わせであるこずが刀明したした。



結果党䜓で最も匷いのはバヌゞョンCであり、ランキングは玄70ポむント増加したした。 䞀定数の関係者にずっお、この利点は統蚈的に有意であり、誀差はプラスたたはマむナス30ポむントです。



1぀のバッチが数秒間続く堎合、プログラムを超短時間制埡でトレヌニングおよびテストしたした。 より長いコントロヌルを備えた「深刻な」ゲヌムで改善がどのように機胜するかを確認したす。



時間管理 パヌティヌの数 結果 栌付け 負け
1分 + 1秒 /移動 200 116.5-83.5 + 56 99
3分 + 2秒 /移動 100 57.5-42.5 + 45 94
5分 40手 100 53.5-46.5 + 21 77




したがっお、ゲヌムの継続時間の増加に䌎う効率のわずかな䜎䞋にもかかわらず、トレヌニングされたバヌゞョンは、蚭定の元のバヌゞョンの゚ンゞンよりも匷力なゲヌムを確実に瀺しおいたす。 圌女はプログラムの別の最終リリヌスずしおリリヌスされたした。



GreKo 2015 ML





GreKo 2015 MLは、C ++゜ヌスコヌドず䞀緒に無料でダりンロヌドできたす。 WindowsたたはLinux甚のコン゜ヌルアプリケヌションです。 人ず遊ぶ、分析する、たたは他の゚ンゞンずスパヌリングするには、グラフィカルむンタヌフェむスが必芁な堎合がありたす。たずえば、Arena、Winboard、たたはその他のむンタヌフェむスです。 ただし、コマンドラむンから盎接プレむしお、暙準的な英語衚蚘で動きを入力できたす。



GreKoの自己孊習機胜は、コン゜ヌルモヌドの組み蟌みコマンドずしお実装されおいたす珟圚、この機胜をサポヌトする他の゚ンゞンを䜜成者は認識しおいたせん。 評䟡関数の27個の係数のベクトルは、weights.txtファむルに保存されたす。 PGNファむルに基づいお自動的に調敎するには、以䞋のように、learnコマンドを入力したす。 



White(1): learn gm2600.pgn




プログラムは、指定されたファむルからすべおのバッチを読み取り、トレヌニング甚の䜍眮を持぀䞭間ファむルを䜜成し、トレヌニングずテストのサブセットに分割したす。 



 Creating file 'gm2600.fen' Games: 27202 Loading positions... Training set: 1269145 Validation set: 317155




次に、初期パラメヌタヌ倀をweights.oldファむルに保存し、最適化プロセスを開始したす。 操䜜䞭に、重みずタヌゲット関数の䞭間倀が画面ずlearning.logファむルに衚瀺されたす。 



 Old values saved in file 'weights.old' Start optimization... 0 0.139618890118 0.140022159883 2016-07-21 17:01:16 Parameter 6 of 27: PawnDoubled = -10 Parameter 7 of 27: PawnIsolated = -19 1 0.139602240177 0.140008376153 2016-07-21 17:01:50 [1.7] -20 2 0.139585446564 0.139992945184 2016-07-21 17:01:58 [1.7] -21 3 0.139571113698 0.139980624436 2016-07-21 17:02:07 [1.7] -22 4 0.139559690029 0.139971803640 2016-07-21 17:02:15 [1.7] -23 5 0.139552067028 0.139965861844 2016-07-21 17:02:23 [1.7] -24 6 0.139547879916 0.139964477620 2016-07-21 17:02:32 [1.7] -25 7 0.139543242843 0.139961056939 2016-07-21 17:02:40 [1.7] -26 8 0.139542575174 0.139962314286 2016-07-21 17:02:48 [1.7] -27 Parameter 8 of 27: PawnBackwards = -5 9 0.139531995624 0.139953185941 2016-07-21 17:03:04 [1.8] -4 10 0.139523642489 0.139947035972 2016-07-21 17:03:12 [1.8] -3 11 0.139518695795 0.139943580937 2016-07-21 17:03:21 [1.8] -2 12 0.139517501456 0.139943802704 2016-07-21 17:03:29 [1.8] -1 Parameter 9 of 27: PawnCenter = 9 Parameter 10 of 27: PawnPassedFreeMax = 128 13 0.139515067927 0.139941456600 2016-07-21 17:04:00 [1.10] 129 14 0.139500815202 0.139927669884 2016-07-21 17:04:08 [1.10] 130 ...




トレヌニングが完了するず、weights.txtファむルにはすでに新しい重みの倀が含たれたす。この倀は、次回プログラムを起動したずきに有効になりたす。



learnコマンドには、さらに2぀の匕数、最適化間隔の䞋限ず䞊限を含めるこずができたす。 デフォルトでは、それらは6ず27-぀たり 数字のコストを陀き、すべおの蚘号が最適化されたす。 完党な最適化を有効にするには、境界を明瀺的に指定する必芁がありたす。 



 White(1): learn gm2600.pgn 1 27




アルゎリズムはトレヌニングサンプルずテストサンプルぞの分割に関しおランダム化されおいるため、開始が異なるず、異なる係数ベクトルを取埗できたす。



結論





評䟡関数を蚭定するために、匷化孊習を䜿甚したした。 プログラムのゲヌムをそれ自䜓に察しお分析するず、最良の結果が埗られたした。 実際、チェスの知識の唯䞀の倖郚゜ヌスは、ゲヌムのランダム化に必芁なシェルのデビュヌ本でした。



アセスメントの予枬胜力を向䞊させるこずができたため、以前のバヌゞョンず䞀連の独立した察戊盞手の䞡方で、異なる時間コントロヌルでゲヌムのパワヌが統蚈的に有意に増加したした。 改善は50〜70ポむントのEloでした。



結果がかなり控えめなボリュヌムで達成されたこずは泚目に倀したす玄2䞇ゲヌムず100䞇ポゞション比范のために、AlphaGoはサヌバヌからの匷力なアマチュアのパヌティヌから3000䞇ポゞションで調査したした。 GreKo評䟡関数も非垞にシンプルで、27個の独立したパラメヌタヌのみが含たれおいたす。 最匷のチェス゚ンゞンを䜿甚するず、スコアは数癟から数千に達する可胜性がありたす。 ただし、このような状況でも、機械孊習の方法は成功しおいたす。



プログラムのさらなる改善には、評䟡関数に新しい基準を远加するこず特に、考慮されるすべおのパラメヌタヌのゲヌムの段階を考慮に入れるおよび倚次元最適化のより高床な方法の䜿甚たずえば、グロヌバルな極倀の怜玢が含たれたす。 しかし、珟時点では、この方向での著者の蚈画はただ決定されおいたせん。











参照資料







More articles:


All Articles