絶賛されたTVシリーズ「TheQueen'sGambit」を今見ているすべての人に捧げます。私たちの新しい翻訳でより多くのチェス用語。
この記事では、サンフィッシュのチェスエンジンをGoに移植することで、チェスエンジンがどのように機能するかを理解しようとし ます。サンフィッシュはそのシンプルさと小さなサイズで有名ですが、それでもまともなチェスゲームをプレイすることができます。一方、Goはシンプルで読みやすいプログラミング言語として知られているので、一緒に素晴らしいペアになることを願っています。
チェスエンジンを作成するには、最初に3つの重要なポイントを決定する必要があります。
- チェスボード（セル、ピース、許可された動き）をどのように表現しますか？
- ボード（勝つ可能性が高い）をどのように評価しますか？
- 最適な動きを見つける方法は？
この投稿のコードスニペットは簡略化されており、最も重要な部分のみが含まれています。完全なエンジンコードは github.com/zserge/carnatusにあります（carnatusはシーバス、Sebastes carnatus種のラテン語名です）。
セルと形状
最適な動きを探している間、何千ものボードのバリエーションがメモリに保存されるため、スペースをあまりとらないボードの便利な表現を見つけることが重要です。
通常、ボードはセルのコレクションです。標準の8x8ボードの周りにパディングを追加して、無効なピースの動きがこの領域に入るようにします。これにより、境界チェックを回避し、コードを大幅に簡素化できます。
線形配列を使用します。チェスピースが移動できる最長の距離は、2平方の騎士の移動です。もちろん、他のスライディングピースは長距離を移動できますが、そのような移動は各正方形が交差するときに順次評価されます。つまり、ピースがそれらを超える前にボードの境界が検出されます。
したがって、ボードの端に沿って2セルのスペースが必要です。12x12ボードを作成することもできますが、ラインアレイとして表現しているため、前の行の右端のインデントスクエアを次のラインの左端のインデントスクエアとして使用できるため、12x10ボードが必要です（×=インデント）。
×××××××××× ×××××××××× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×........× ×××××××××× ××××××××××
この表記では、「a1」は9×10 + 1 = 91のようになり、「a8」は「2×10 + 1」= 21のようになります。
ボード配列の各セルは、チェスピース、空の正方形、またはインデントゾーンを表します。これらの値に数値定数を使用することもできますが、デバッグを容易にするために、人間が読み取れる文字を使用します。大文字と小文字は形状を表し、スペースはインデントゾーンを表し、ドットは空のセルを表します。
| | RNBQKBNR | PPPPPPPP | ........ | ........ | ........ | <- ........ | ........ | ........ | pppppppp | rnbkqbnr | | |
略語のデコード
R — rook —
N — knight —
B — bishop —
Q — queen —
K — king —
N — knight —
B — bishop —
Q — queen —
K — king —
最後に、コードの記述を開始できます。
type Piece byte
func (p Piece) Value() int { ... }
func (p Piece) Ours() bool { ... }
func (p Piece) Flip() Piece { ... }
type Board [120]piece
func (b Board) Flip() Board { ... }
type Square int
func (s Square) Flip() Square { ... }
形状には特定の値があります。これらの値は、ボード上の位置を評価し、誰が勝っているのかを理解するために必要です。通常、ポーン= 100、ナイト= 280、ビショップ= 320、ルーク= 479、クイーン= 929であり、キングは非常に価値があるため、ナイト、ビショップ、ルークのペアと組み合わせて8つのクイーン（ポーンがクイーンになります）を打ち負かします。私たちがこのすべての富を持っているが、私たちが王を失った場合、数えることは私たちが失うことを示します。
各タイプには、対戦相手が移動する前にボードを反転した後、同じ値を返すFlip（）メソッドがあります。シェイプの場合、シェイプシンボルの大文字と小文字が変わります。正方形で、彼は119の正方形を返します（ボードのもう一方の端から数えて）。ボードに関しては、彼は正方形からすべてのピースを逆の順序でコピーし、ケースを変更します。
ストロークジェネレータ
これで、エンジンの構成要素がすでにできたので、ゲームの位置について考えることができます。位置は、通路の正方形、さまよう正方形、キャスティングの可能性など、ゲーム内のピースと追加の状態を備えたボードです。ゲームを単純化したい場合は、ボードタイプを再利用できますが、移動とボード評価用に別の位置タイプを作成します。
動きとは何ですか？これは、2つのセルの組み合わせです。移動前にピースが配置されていたセルと、ピースが移動したセルです。位置は、スコア、各プレーヤーのキャスティングルール、および通過/さまよう正方形を備えたチェスボードです。どちらのタイプにも、対戦相手の動きにフリップ（）メソッドがあります。
type Move struct {
from Square
to Square
}
func (m Move) Flip() Move { ... }
type Position struct {
board Board //
score int // — ,
wc [2]bool //
bc [2]bool //
ep Square // ,
kp Square // ,
}
func (p Position) Flip() Position { ... }
これで、最初の大きなメソッドである許可された移動ジェネレーターを作成できます。黒をプレイするためにボードを裏返し、再び白に移動するので、私たちは白い部分だけを気にします。
すべての有効な動きを生成するには、次のものが必要です。
- 各ピースの各方向へのすべてのワンステップ移動のリストを作成します。
- 白以外の部分を無視して、すべてのセルに対して同じことを行います。
- 各白い部分のすべての可能な方向への動きを指定します。
- 駒の動きの長さが制限されていない場合（ルーク、ビショップ、クイーン）、途中で障害物に遭遇するまで動かし続けます：相手の駒またはボードの端の後ろのくぼみ。
これは、キャプチャとキャスティングを考慮しない単純化されたコードです。完全な実装は Githubにありますが、それほど違いはありません。
方向演算を読みやすくするために、方向定数N / E / S / Wを使用します。
const N, E, S, W = -10, 1, 10, -1
var directions = map[Piece][]Square{
'P': {N, N + N, N + W, N + E},
'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
'B': {N + E, S + E, S + W, N + W},
'R': {N, E, S, W},
'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}
func (pos Position) Moves() (moves []Move) {
for index, p := range pos.board {
if !p.ours() {
continue
}
i := Square(index)
for _, d := range directions[p] {
for j := i + d; ; j = j + d {
q := pos.board[j]
if q == ' ' || (q != '.' && q.ours()) {
break
}
if p == 'P' {
if (d == N || d == N+N) && q != '.' {
break
}
if d == N+N && (i < A1+N || pos.board[i+N] != '.') {
break
}
}
moves = append(moves, Move{from: i, to: j})
if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
break
}
}
}
}
return moves
}
これらはすべて、有効な動きをするために考慮する必要があるチェスのゲームのルールです。次のステップは、ポジションに移動を適用して、新しいゲームポジションを作成することです。途中でのキャプチャ、ポーンプロモーション、キャスティングを考慮しない場合、メソッドは次のようになります。
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = '.'
return np.Flip()
}
彼は単にピースを動かし、それが以前に空だったセルにマークを付け、ボードを裏返します。メソッドの完全な実装は Githubにあり、すべての特別なポーンとキングの動きを正しく処理します。
この段階では、チェス「マン対マン」をプレイして、プロセスを制御し、合法的な動きのみを行うことができます。または、負けるまでランダムに移動するプリミティブなチェスエンジンを作成することもできます。
しかし、私たちが負けていることをどうやって理解するのでしょうか？
ボードの評価
ボード上のポジションごとにポイントが付与されます。両方のプレーヤーが同じ条件で開始するため、最初はスコアはゼロです。移動が完了すると、キャプチャされたピースと、ボード上のピースの位置がどのように変化したかによってスコアが変化します。
最も単純なケースでは、ボード上のピースを数え、それらの値を合計することができます（対戦相手のピースを差し引いたもの）。そのような計算は、王がチェックとチェックメイトと宣言されているかどうかを示します。しかし、これは非常に弱い評価システムです。
はるかに正確で驚くほど単純なアプローチは、形状対二乗比テーブル（ PST）です。-ピーススクエアテーブル）。ピースごとに、チェスボードと同じサイズのテーブルが作成され、対応する値が各正方形に割り当てられます。これらの値は経験的なものなので、Sunfishエンジンから取得しました。
実際、より高度なチェスエンジンは、ピースの価値が変化するため、プレイ中にPSTを更新します（つまり、ポーンはゲームの終わりに向かってより価値が高くなります）。しかし、単純なエンジンがあります。
移動後の位置を評価するには、次のものが必要です。
- 現在の位置の評価を決定し、
- 移動するピースの値を差し引き、
- PTSテーブルに従って新しい図の値を追加します。
- キャプチャされたピースの値があれば追加します。
さらに、キャスティング中のルークの値と、PSTテーブルのパッセージでのプロモーションまたはキャプチャ中のポーンの値を調整する必要があります。しかし、ここではこれを考慮しません：
var pst = map[Piece][120]int{
'P': { ... },
'N': { ... },
'B': { ... },
'R': { ... },
'Q': { ... },
'K': { .... },
}
func (pos Position) value(m Move) int {
i, j := m.from, m.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// PST-
score := pst[p][j] - pst[p][i]
if q != '.' && q != ' ' && !q.ours() {
// PST-
score += pst[q.Flip()][j.Flip()]
}
return score
}
これで、有効なものではなく、可能な限り最良の動きを選択する、もう少し高度なエンジンを作成できます。
しかし、実際のチェスエンジンは、より詳細な分析を行い、両側で可能な動きの分岐を繰り返して、長期的に可能な限り最良の動きを見つけます。
検索アルゴリズム
チェスエンジンで最も一般的な検索アルゴリズムはより単純です。深度優先検索は、ルートから開始して指定された深度制限まで下がり、可能なすべての移動を繰り返してから戻ります。各ストローク位置の値は、ミニマックスアルゴリズム（ミニマックス） cアルファ-ベータプルーニング（ アルファ-ベータプルーニング）を使用して計算され ます。
ミニマックスは、最悪のシナリオで起こりうる損失を最小限に抑えるために使用されるルールです。プレーヤーは、対戦相手のすべての最良の動きを考慮し、対戦相手の最良の戦略が可能な限り多くのポイントをもたらすようにそのような動きを選択します。
単純なミニマックスアルゴリズムはチェスには遅すぎて、良いものを見つけるためにあまりにも多くの動きを繰り返す必要があります。
アルファベータプルーニングは、検討する価値のないノードを削除することにより、ミニマックスアルゴリズムを高速化するために使用されます。アルファベータクリッピングは、次のロジックに基づいています。チェスをプレイしていて、非常に良い動きを発見したと想像してください。A。ボードを見続けて、さらに良い動きを見つけますB。しかし、状況をより深く分析し、選択した場合はそれを理解します。移動Bで、敵は数回の移動であなたにチェックとチェックメイトを宣言します。これで、Bを破棄し、Bの後に他の可能な組み合わせを分析する時間を無駄にしません。
チェスエンジンがどのように機能するかを理解するには、ミニマックスとアルファベータの両方のクリッピングが重要です。 Sunfishエンジンは、改良されたMDF（f）検索アルゴリズムを使用します 。これは、クリッピングと組み合わせたminimaxアルゴリズムの変形でもあります。
私たちのエンジンでは、検索深度を徐々に増やし、MDF（f）アルゴリズムを呼び出して、最適な結果の下限と上限を見つけます。 MDF（f）アルゴリズムは、転置キャッシュを使用したアルファベータクリッピング反復を使用します。
転置キャッシュは、ボード上の各ポジションについて、そのポジションに到達した深さ、カウント、および移動を記憶するキャッシュです。次に、新しい位置を検討するときに、最初に転置テーブルと照合されます。
検索アルゴリズムのコードは数行の再帰検索であるため、ここでは投稿しませんが、チェスエンジンの完全なソースコードはGitHubでいつでも見つけることができ ます。
次は何ですか？
シンプルなチェスエンジンに興味があるなら、Sunfishで遊ぶことを強くお勧めします。ちなみに、SunfishはMicromaxエンジンに基づいており 、著者からのすばらしいドキュメントが付属しています。これは間違いなく読む価値があります。
Goのエンジンでは、UCIプロトコルの小さな実装を追加して、PyChessUIで使用できるようにしました。おそらく、まだ多くのバグがあり、改善の可能性がたくさんありますが、それは興味深い道でした：チェスエンジンを開発するというアイデアから、既製の動作するコンピューターチェスプログラムまで。
はい、彼は弱いですが、彼は本物のチェスゲームをします！
この記事を楽しんでいただけたでしょうか。あなたはで私に従うことができます Github、 Twitter、またはrss経由でサブスクライブし ます。