兄弟に対してチェスゲームをプログラムした方法

これは、私が兄と一緒にチェスのゲームに勝とうとした方法の話です。たった1つのクソゲーム。何がそんなに特別なのですか？私はチェスが得意ですか？どういたしまして。遊んでいるうちに何かを学びましたか？また、いいえ。たぶんこれは、目標ではなく、旅のための旅についての話ですか？あんまり。私もそれを楽しんだのですか？わからない。



これは、世界で最も研究されているゲームの1つで、必要のないソフトウェア開発の経験を使用して、オリジナルを目指した私の試みについての話です。



私のチェスに対する絶対的な愚かさと、ゲームを改善しようとする人々にとってこの記事はまったく役に立たないにもかかわらず、エンジニアリングの原則を問題に適用する独自の方法を共有する価値はあったと思います。私は成功していますか？最後にこれについて学びます。

なぜチェスに関わったのか

2020年のパンデミックの間、私の兄は他の多くの人々と同様に、オンラインチェスに夢中になりました。数ヶ月プレイした後、彼はこのゲームについて非常に刺激的に話し始め、他の家族に挑戦し始めました。私たちの父は電話に出ましたが（彼はデジタルの大失敗に見舞われましたが）、私は諦めませんでした。制限要因の1つは、非常に時間のかかる可能性のある趣味に飛び込むことに抵抗を感じたことです。私はこのゲームについて十分に知っていたので、中級者になるには数千時間とまではいかなくても数百時間を費やす必要があることを理解しました。同時に、私は、当時すでに100以上のゲームをプレイしていた兄に負けるという考えにも触発されなかったことを認めます。私は一人ではありません。



しかしある日、私は彼の挑戦に屈した。言うまでもなく、損失は壊滅的なものでした。子供の頃からゲームのルールや基本を知っていましたが、弟のスキルとは比べ物になりませんでした。後で、chess.comでゲームの分析 を見ると、私の戦術的なラグは、+ 9のマークに達するまで、移動ごとに増加するだけであることがわかりました（これは、不在に対してルーク、ビショップ、ポーンを失うことに等しい）敵の損失の）。その瞬間、すべての希望を失って、私はあきらめました。これについて何かをする必要があることに気付いたとき、同様の状況がさらに2、3のゲームで繰り返されました。



私の最初の決断は、ゲームをより深く掘り下げることでした。

試み1：研究

ゲームの品質を改善するための私の最初の試みは明白でした。他の学生からの推奨事項については、RedditとYouTubeにアクセスしてください。GM Naroditskyからのレッスンの 合間に、Lichessの問題を読んで解決する 間、私はインターネット上でランダムな対戦相手といくつかのゲームをプレイしました。これらすべてにもかかわらず、私の評価は低いままでした（1300〜1400 Rapid on Lichess）。







兄との試合をさらに数回行った後、勝つチャンスがないことに気づきました。私はすべて同じ開発方法（演奏、テクニックの勉強、ビデオの視聴）に従い続けましたが、これに費やす時間は兄よりはるかに少なかったです。当時、彼はすでに月に数百のゲームをプレイしていましたが、私は10歳以下でした。このレートで、私のギャップはますます大きくなりました。



その時、私は非常に重要なニュアンスに気づきました。私はゲーム自体には特に興味がなく、実際、ゲームを改善したくありませんでした。私の主な目標は、ただ一人の人、つまり私の兄弟を倒すことでした。

試み2：敵を研究する

チェスゲームは通常、オープニング、 ミドルゲーム、 エンドゲームの3つのフェーズに分けられ ます。いくつかの基本的な交配パターンを学んだ後 、ゲーム終了段階で大きなアドバンテージから勝利に移行するのは通常「簡単」なので、そのアドバンテージを得ることは私にとって最初の質問でした。



中盤の段階では、通常、長期的な戦略を展開し、戦術を適用することで 利点が得られ ます。ゲームの原理を読んで勉強することで戦略を改善することができ（私はそれが好きです）、戦術は問題を解決することによってのみ開発され ます（私は特に嫌いです）。したがって、私の兄がchess.comで毎日約20のそのような問題を解決したことを考えると、戦術スキルでは間違いなく遅れることを理解しました。私にとって、これは達成不可能な限界でした。したがって、残った機会は1つだけでした。それは、オープニングステージでアドバンテージを得ることです。



オープニングフェーズの背後にある理論は巨大です。同時に、長いシーケンスと動きのバリエーション、そして対戦相手の可能な答えを記憶する必要があります。初心者は多くを覚える必要はありませんが、最も典型的な開口部にある程度精通していると非常に有益です（またはそう言われています）。



それから私は兄のランダムなゲームのいくつかを見て、彼が使用した開口部を理解しようと決心しました。 Lichessのデビューについても勉強しました 「イタリア党」と シシリアン・ディフェンスは、彼らの基本原則を思い出そうとしている。それとは別に、私はたくさんのYouTubeビデオを見ました。



明らかに、私の兄は私の前で（そしてもっと良く）これをすべてやったので、当然私は再び負けました。 （少なくとも私にとっては）意味のないオープニングの動きを覚えることは退屈で疲れるだけであるという事実は言うまでもありません。これはすべて私に決して喜びを与えませんでした。もう一つの問題は、対戦相手が本に規定されている動きから逸脱し始めたとき、私は単に新しい位置を理解していなかったので、どう反応するかを絶対に知らなかったということでした。



一歩下がって考え直す時が来ました。それから、私は実際に兄を倒すのではなく、同じオープニングを完璧にプレイした対戦相手とのゲームを改善しようとしていることに気づきました。もっと方向性を持って行動できたでしょうか？代わりに、彼の兄弟の弱点に対して特別に準備することができたでしょうか？明らかに、このアプローチは彼に対してのみ機能しますが、それは私の目標と完全に一致していました。

試行3：プログラミング

今、私の仕事は別の形をとっています。私の兄弟（以下、PlayerX）が不利な立場にありながら、到達する可能性が最も高い開口部の出口の位置を見つけることです。私たちの誰もがゲームの専門家ではなく、私たちのレベルのプレーヤーはあまり慎重にプレーしないことに注意してください。



良いプレイヤーに対抗する唯一の方法は、本の動きを正確に追うことです。そうすれば、少なくとも対戦相手が何の動きもせず、アドバンテージを得ることができるからです。ただし、クラブレベルのプレーヤーと対戦している場合は状況が変わります。敵がこれに正しく反応する可能性が低く、したがって自分が困難な立場にあることがわかっている場合は、リスクを冒すことができます（つまり、一時的に不利になる）。



兄がchess.comでプレイした500以上のゲームのリストもありました。そして、私はプログラマーなので、この問題を工学的に解決することは私にとって自然なアプローチになりました。



彼がプレイしたゲームをchess.comAPIを使用してダウンロードし、白と黒のゲームに分け始めました。それから、白でプレーするときに自分が望む方向にゲームを向ける可能性が高いと感じたので、兄が黒でプレーするゲームに焦点を合わせました。

import json
import requests

def get_month_games(player, yyyy_mm):
    url = 'https://api.chess.com/pub/player/{}/games/{}'
    r = requests.get(url.format(player, yyyy_mm))
    if not r.ok:
        raise Exception('get_month_games failed')
    games = json.loads(r.content)
    # Format: {games: [{url, pgn}, ...]}
    return games['games']

# ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

import chess.pgn
import io
import json

with open('games.json') as f:
    data = json.load(f)

games = []
for game in data:
    pgn = io.StringIO(game)
    games.append(chess.pgn.read_game(pgn))

black_games = [g for g in games if g.headers["Black"] == "playerx"]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

次に、タスクを次のように定式化しました。「PlayerXが見たすべてのポジションを考慮すると、オープニングの終わりに彼にとって最も収益性が低いと思われるポジションはどれですか。



今回はタスクが明確に定義され、身近な分野で作業が始まりました。再利用可能なツールを作成するという目標がなく、利用可能なデータを調べて1つの解決策を見つけるだけでよいため、Python、つまりJupyterノートブックで分析を行うことにしました 。



Pythonには、チェスを操作するための優れたライブラリがすでにあることが判明しました 。python -chess（移動の生成、評価、視覚化）と pythonstockfishです。（有名なStockfishチェスエンジンを使用してチェスの位置を評価するためのバインディング）。



この方法で問題をグラフに変換しました。ノードは特定のチェスの位置です（FEN表記で説明されてい ます）。エッジは2つのノードを接続しますが、ターゲット位置は許容可能な移動によって最初のノードから到達可能です。すべてのゲームには、1つの同じ開始ノード（開始位置）があります。



次に、PlayerXでプレイされたすべてのゲームのグラフを黒として作成し、対応する移動が行われた回数で各エッジを追加でマークしました。

class GamesGraph():
    def __init__(self):
        self.graph = igraph.Graph(directed=True)

    def add_move(self, start_fen, end_fen, uci):
        vs = self._ensure_vertex(start_fen)
        vt = self._ensure_vertex(end_fen)
        try:
            e = self.graph.es.find(_source=vs.index, _target=vt.index)
            e["count"] += 1
        except:
            e = self.graph.add_edge(vs, vt)
            e["uci"] = uci
            e["count"] = 1

    @property
    def start_node(self):
        return self.graph.vs.find(chess.STARTING_FEN)

    def _ensure_vertex(self, fen):
        try:
            return self.graph.vs.find(fen)
        except:
            v = self.graph.add_vertex(name=fen)
            v["fen"] = fen
            v["turn"] = chess.Board(fen).turn
            return v
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

その結果、次のような重み付き有向グラフ（位置は異なる一連の移動で取得できるため、ツリーではありません）が得られました（合成、実際のグラフはここに収まらないため）：







ここで、開始位置は四角い結び目で示され、色はこの位置で移動するのが白か黒かを示します。



また、Stockfishを使用したホワイトアドバンテージの観点から、各ポジションの評価を取得したいと思いました。何千もの位置を評価するプロセスには時間がかかるため、個別に実行して、一意のFEN位置をそれぞれStockfishの推定値にマッピングするJSONオブジェクトを作成することにしました。

from stockfish import Stockfish

stock = Stockfish(parameters={"Threads": 8})
stock.set_depth(20)
stock.set_skill_level(20)

def eval_pos(fen):
    stock.set_fen_position(fen)
    return stock.get_evaluation()

# fens -     FEN   .
for fen, node in graph.fens.items():
    node.eva = eval_pos(fen)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

アドバンテージの評価は、センチポイントまたは「Xムーブのチェックメイト」として返されました 。ここで、正の数は白のアドバンテージを意味し、黒の負のアドバンテージを意味します。

{"type":"cp", "value":12}    #    12 .
{"type":"mate", "value":-3}  #      .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

100センチポイントは、1つのポーンの対戦相手よりも有利であることを意味し、300は、ビショップのような1つのマイナーピースを意味します。ただし、Stockfishは、ピースの位置に応じてピースに値を割り当てることに注意してください。つまり、ボード上のピースの数が同じでも、1000センチポイントの利点を得ることができる可能性があります。



このスコアを、たとえば0から1までの数値など、処理に便利なものにマッピングする必要がありました。このため、300以上のアドバンテージが1.0で表示され、300以上のラグが0で表示されることにしました。 X移動のメイトは（Xが20であっても）1または0になります。

#  [-1;1]
def rating(ev, fen):
    val = ev["value"]
    if ev["type"] == "cp":
        #  -300, +300.   .
        val = max(-300, min(300, val))
        return val / 300.0
    #   X :  max .
    if val > 0: return 1.0
    if val < 0: return -1.0
    #   ,     ?
    b = chess.Board(fen)
    return 1.0 if b.turn == chess.WHITE else -1.0

#  [0;1],  0 -  min,  1 -  max   .
def rating_black(ev, fen):
    return -rating(ev, fen) * 0.5 + 0.5
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

今ではすべての情報が適切ではなく、グラフのノード（つまり、位置）を見つける必要がありました。ここでは、黒が負けた位置にあり、それらに到達するための最適な一連の動きがあります。特定の位置に到達する確率を簡単に計算できるように、リブの重さを量る必要がありました。私はこのように推論しました：

• 各位置で、対応するエッジに沿ったパスの数をその位置から行われた移動の総数で割ることにより、特定の移動を行う確率を見積もることができます。
• 各エッジの重みは0から1になります。値が大きいほど、その位置からエッジをトラバースする可能性が高くなります。
• 次に、特定のパスを通過する確率は、通過したすべてのエッジの確率の積になります。

標準のグラフアルゴリズムを使用して問題を解決するには、次のようにエッジの重みを変換する必要がありました。

• それらは確率ではなく距離を表しています（つまり、距離が大きいほど、パスを選択する可能性は低くなります）。
• 2つのノード間の距離は、（確率の積ではなく）通過したエッジの重みの合計でした。

実際、これは説明するよりもはるかに簡単です。式は非常に単純です。

distance(e) = -log(prob(e))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Pythonでは、次のようになります。

def compute_edges_weight(vertex):
    all_count = sum(map(lambda x: x["count"], vertex.out_edges()))
    for edge in vertex.out_edges():
        prob = edge["count"] / all_count
        edge["prob"] = prob
        edge["weight"] = -math.log(prob)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

確率が0から1の間であるため、エッジを選択する確率の対数を取ると負の数になります。確率がゼロの場合を心配する必要はありません（その結果、対数はマイナスになります。無限大）、グラフの各エッジが少なくとも1回トラバースされているため... 確率が低いほど、対数は負になります。つまり、符号を逆にすると、必要なものが得られます。理由は次のとおりです。

• 対数の合計は、引数の積の対数ですlog(a) + log(b) = log(a*b)
  
  
  
  。
• 結果が大きいほど、それを決定する確率は低くなります。

このアイデアを武器に、ダイクストラのアルゴリズムを使用して、開始ノードと他のすべてのノード間の 最短経路を計算でき ます。結果は、各ノードと開始位置への最短パスの間のマッピングであり、ノードにつながる最も可能性の高い一連の移動を表します。



この時点で、アドバンテージの最小値を任意に選択し、確率でパスを並べ替えました。最初のいくつかのパスは、PlayerXよりも有利なデビューから抜け出すための最大のチャンスを表しています。

改善点

私は何を知りましたか？このアルゴリズムによって与えられた位置の中には、次のものがありました（ホワイトの動き）：







ご覧のとおり、黒の最後の動きであるg6が間違いだったため、黒は非常に厄介な位置にあります（Stockfishによると+8.9）。ホワイトは続けて、e5とルークからポーンを取ります。この時点で、黒のゲームは実質的に終了します。彼は騎士、h7のポーン、および司教を救わなければならないからです。アルゴリズムの別の結果はこれでした（ホワイトの動き）：







ここでは、チェックメイトが1つの動きで表示されます（ 子供のチェックメイト）。



問題は、PlayerXが最初のゲームでこれらの間違いを数回だけ犯し、それを二度と繰り返さなかったことです。初期のクイーンアタックは通常、経験の浅いプレイヤーによってのみ行われ、同じレベルのプレイヤーに対してのみ効果があります。初心者のカテゴリーを離れたPlayerXは、より有能な対戦相手がそのように進まないため、長い間これらの間違いを犯していません。 PlayerXはそれに対して防御する方法を知っていたので、私はそのような開口部が機能しないことを知っていました。



もう1つの問題は、移動のシーケンスに関連していました。これは1回だけ発生しましたが、通常の位置から発生しました。各エッジの確率は1.0であったため、最終的な位置の確率は、最後の典型的な位置の確率と同じであることが判明しました（他の可能性が実行されなかった場合）。以下の例では、エッジ7と6（2番目の動きで最も一般的な位置）をたどり、次にエッジの1つを1でたどることができます。さらに、後続のすべての手は1回だけ再生され（この位置は1回の試合でのみ形成されたため）、その結果、各手は1.0の確率になります。







そして、ここに確率があります：







同じ一連の動きが明確に再生される可能性は低いため、このようなスキームは信頼できません。そのような結論のために、これらの位置からゲームが行われる十分なゲームがありません。



有名な引用（ B.ブリュースター？）：「理論的には理論と実践の間に違いはありませんが、実際には違いがあります」この場合は正しいことが判明したので、より成功した仮説を見つけるためにいくつかの改良と独立した研究が必要でしたポジション。



2番目の問題を修正するために、エッジの確率に上限を設定して、1回だけ再生された長い一連の動きが徐々に確率を失うようにしました。

def compute_edges_weight(vertex, prob_ceiling=0.9):
    all_count = sum(map(lambda x: x["count"], vertex.out_edges()))
    for edge in vertex.out_edges():
        #  ...    (default 90%).
        prob = min(edge["count"] / all_count, prob_ceiling)
        edge["prob"] = prob
        edge["weight"] = -math.log(prob)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

最初の問題では、悪い仮定を手動で除外しました。その結果、私は作業するポジションが2、3しか残っていませんでした。



別の変更の理由は、私がホワイトのためにプレーし、どのパスを取るかを自分で決めることができたので、ホワイトの動きの確率がパスを選択する確率に影響を与えたくないということでした。このため、ホワイトの移動のすべての確率を1.0（重みゼロ）に設定すると、次のようなグラフになります。

準備

勉強の過程で、私は次のポジションを選びました：







Lichessによると、これはアレヒンディフェンス（2つのポーン攻撃）です。この位置では、ブラックは1回だけ成功した動き（Nb6）を持っていますが、その後もあまり有利な位置に留まりません（Stockfishによると+0.6）。ただし、この位置から、PlayerXはしばしばNf4を再生します。これは、彼にとって非常に残念なことです（+2.3）。Lichessにスタジオを設置し、いくつかのバリエーション（PlayerXが再生する良い動きと動き）を調べ始めました。



結局、私は可能性の木を手に入れ、それを覚えて理解しようとしました。たとえば、d5のような動きを脅かすもの、Nf4が失敗した理由を見つけ、すべての人に最適な答えを準備する必要がありました。



私はすぐに退屈したので、これを長い間しませんでした、そして実際、私は部分的にしか準備ができていませんでした。

決定的なゲーム

それはすべて、私が未来を見ているかのように起こりました。PlayerXと私はアレヒンの防衛の立場にありました。不快な状況に陥った彼は、5番目の動きで騎士を逃しました。あなたよりもはるかに経験豊富なプレイヤーでさえ、条件を失うことに気付いたときに次々とミスを犯し始めることがわかりました。勝ったときははっきりとプレーするのは簡単ですが、逆の状況で冷静さを保つことはできますか？10番手で、私はすでに+7.1のアドバンテージでリードしていたので、負けるのは難しいですが、それは私が考え出した計画の終わりでもありました。黒が今どのように窮屈になっているか、そして私の作品がどのように王を攻撃することを目指しているかを見てください：







その瞬間から、私はあちこちでミスを犯し始めましたが、同時に私は27を動かすまでいくつかの利点を維持することができました：







残念ながら、時間は非常に限られていたので（10分間の加速ゲームをプレイしました）、すばやく歩かなければなりませんでした。結局、私は32と33の動きで致命的なミスを犯し、もう一度、無敗の対戦相手からチェックメイトを受け取りました。







これが全体の一致です（重大なエラーなどを含む）：





ライブバッチプレビュー：lichess.org/2qKKl2MI

結論

私はこれらすべてから何を学びましたか？振り返ってみると、そのほとんどが明白に見えるいくつかのことがあります。

1. 特定の対戦相手の準備をすることで、オープニングの大きなアドバンテージを得ることができます。
2. 初心者のプレイヤーは、相手の疑わしい動きを利用する機会を逃すことがよくあります。この点で、クーデターが1つしかない位置に敵を追いやることで、簡単にアドバンテージを得ることができます。
3. . , . .
4. , , . .
5. , , .

私が使用したコードはリポジトリにあります。私はそこにデータを含めていないことに注意してください、そしてコード自体はかなりずさんです。それでも、特にコンピュータサイエンスの習得をまだ考えている人にとって、これが役立つことを願っています。見てください-実生活の問題を解決するのに役立つことでかなり可能です、それでそれは単にビットを前後に動かすだけではありません。



それがすべてです、友達。いつか兄を倒せるようになることを願っていますが、今のところは自分の力でこれを成し遂げようとしています。