コンピュータのチェス プログラムでチェス盤を表すには、どのようなデータ構造を使用しますか?
質問する
23947 次
14 に答える
15
本格的なチェス エンジンの場合、ビットボードを使用すると、メモリ内のチェス盤を効率的に表すことができます。ビットボードは、特にビットボードが単一の CPU レジスタ内に収まる 64 ビット アーキテクチャでは、どの配列ベースの表現よりも高速です。
ビットボード
ビットボードの基本的な考え方は、すべてのチェスの駒の種類を 64 ビットで表現することです。C++/C# では になりますulong/UInt64。したがってUInt64、チェス盤を表す 12 個の変数を維持します。駒の種類ごとに 2 つ (黒 1 つと白 1 つ)、つまり、ポーン、ルーク、ナイト、ビショップ、クイーン、キングです。a のすべてのビットは、UInt64チェス盤の正方形に対応します。通常、最下位ビットは a1 平方、次の b1、次に c1 というように、行優先方式で続きます。チェス盤上の駒の位置に対応するビットは 1 に設定され、その他はすべて 0 に設定されます。たとえば、a2 と h1 に 2 つの白いルークがある場合、白いルークのビットボードは次のようになります。
0000000000000000000000000000000000000000000000000000000110000000
たとえば、上記の例でルークを a2 から g2 に移動したい場合、次のビットボードで XOR を実行するだけで済みます。
0000000000000000000000000000000000000000000000000100000100000000
ビットボードには、移動の生成に関してパフォーマンス上の利点があります。ビットボード表現から自然に生まれる他のパフォーマンス上の利点もあります。たとえば、検索アルゴリズムを並列化するときに大きな利点となるロックレス ハッシュ テーブルを使用できます。
参考文献
チェス エンジン開発の究極のリソースはChess Programming Wikiです。私は最近、C# でビットボードを実装するこのチェス エンジンを作成しました。さらに優れたオープン ソースのチェス エンジンはStockFishで、これもビットボードを実装していますが、C++ で記述されています。
于 2013-08-27T20:50:52.017 に答える
13
最初に、チェス盤を表すために8 * 8 整数配列を使用します。
この表記法を使用してプログラミングを開始できます。ピースのポイント値を指定します。例えば：
**White**
9 = white queen
5 = white rook
3 = bishop
3 = knight
1 = pawn
**black**
-9 = white queen
-5 = white rook
-3 = bishop
-3 = knight
-1 = pawn
White King: very large positive number
Black King: very large negative number
など (上記のポイントは、各チェスの駒の取引力の概算であることに注意してください)
アプリケーションの基本的なバックボーンを開発し、使用されるアルゴリズムの動作を明確に理解したら、ビット ボードを使用してパフォーマンスを改善してみてください。
ビット ボードでは、8 つの 8 ビット ワードを使用してボードを表します。この表現には、チェスの駒ごとにボードが必要です。あるビットボードではルークの位置を保存し、別のビットボードではナイトの位置を保存します...など
ビット ボードを使用したピースの操作は非常に簡単かつ高速であるため、ビット ボードを使用すると、アプリケーションのパフォーマンスを大幅に向上させることができます。
ご指摘の通り、
今日のほとんどのチェス プログラム、特に 64 ビット CPU で実行されるものは、ビットマップ アプローチを使用してチェス盤を表し、動きを生成します。x88 は、64 ビット CPU を搭載していないマシン用の代替ボード モデルです。
于 2008-09-02T16:08:42.887 に答える
9
簡単な方法は、8x8 整数配列を使用することです。空の正方形には 0 を使用し、ピースに値を割り当てます。
1 white pawns
2 white knights
3 white bishops
4 white rooks
5 white queens
6 white king
Black pieces use negative values
-1 black pawn
-2 black knight
etc
8| -4 -2 -3 -5 -6 -3 -2 -4
7| -1 -1 -1 -1 -1 -1 -1 -1
6| 0 0 0 0 0 0 0 0
5| 0 0 0 0 0 0 0 0
4| 0 0 0 0 0 0 0 0
3| 0 0 0 0 0 0 0 0
2| 1 1 1 1 1 1 1 1
1| 4 2 3 5 6 3 2 4
-------------------------
1 2 3 4 5 6 7 8
ピース移動は、配列インデックスを使用して計算できます。たとえば、白いポーンは、行インデックスを 1 ずつ増やすか、ポーンの最初の移動の場合は 2 ずつ増やして移動します。したがって、[2][1] の白いポーンは [3][1] または [4][1] に移動できます。
ただし、このチェス盤の単純な 8x8 配列表現には、いくつかの問題があります。最も顕著なのは、ルーク、ビショップ、クイーンなどの「スライドする」駒を動かしている場合、常にインデックスをチェックして、駒がボードから外れていないかどうかを確認する必要があることです。
今日のほとんどのチェス プログラム、特に 64 ビット CPU で実行されるものは、ビットマップ アプローチを使用してチェス盤を表し、動きを生成します。x88 は、64 ビット CPU を搭載していないマシン用の代替ボード モデルです。
于 2008-09-02T16:04:17.780 に答える
6
120 バイトの配列。
これはセンチネル スクエアで囲まれた 8x8 のチェス盤です (たとえば、255 は駒がこのスクエアに移動できないことを示します)。騎士が飛び越えられないように、歩哨の深さは 2 です。
右に移動するには 1 を足します。左に移動するには -1 を足します。上 10、下 -10、上および右斜め 11 など。正方形 A1 はインデックス 21 です。H1 はインデックス 29 です。H8 はインデックス 99 です。
すべてがシンプルになるように設計されています。しかし、ビットボードほど高速になることはありません。
于 2009-07-26T22:58:56.677 に答える
4
もちろん、チェス盤を表すにはさまざまな方法があり、最適な方法は、何が最も重要かによって異なります。
主な選択肢は、速度とコードの明瞭さの 2 つです。
速度が優先される場合は、ボード上のピースの各セットに 64 ビットのデータ型を使用する必要があります (例: 白のポーン、黒のクイーン、アンパッサンのポーン)。その後、移動を生成し、移動の正当性をテストするときに、ネイティブのビット操作を利用できます。
コードの明確さが優先される場合は、ビットシャッフルを忘れて、他の人がすでに提案したようにうまく抽象化されたデータ型を使用してください。この方法を使用すると、パフォーマンスの上限に達するのが早まる可能性があることを覚えておいてください。
まず、Crafty (C) とSharpChess (C#) のコードを見てください。
于 2008-09-02T16:16:46.923 に答える
4
これが役立つかどうかはわかりませんが、Deep Blue は単一の 6 ビット数値を使用して、ボード上の特定の位置を表していました。これにより、64 ビットのビットボードを使用していた競合他社と比較して、オンチップのフットプリントを節約できました。
ターゲット ハードウェアに既に 64 ビット レジスタがある可能性があるため、これは関係ないかもしれません。
于 2008-09-02T16:29:58.687 に答える
4
チェス エンジンを作成するとき、最初は [8][8] アプローチを使用しましたが、最近、64 個のアイテム配列を使用してチェス盤を表すようにコードを変更しました。少なくとも私の場合、この実装は約 1/3 効率的であることがわかりました。
[8][8] アプローチを行う際に考慮したいことの 1 つは、位置を記述することです。たとえば、チェスの駒の有効な動きを記述したい場合、そのためには 2 バイトが必要になります。[64] item 配列を使用すると、1 バイトで実行できます。
[64] アイテム ボード上の位置から [8][8] ボードに変換するには、次の計算を使用するだけです。
行= (バイト)(インデックス / 8)
列 = (バイト)(インデックス % 8)
パフォーマンスに敏感な再帰的な移動検索中にそれを行う必要がないことがわかりましたが。
チェス エンジンの構築の詳細については、プロセスをゼロから説明している私のブログ ( www.chessbin.com)を参照してください。
アダム・ベレント
于 2009-04-15T01:13:54.780 に答える
3
標準の8x8 ボードに代わるものは、10x12メールボックスです (メールボックスのように見えるため、そう呼ばれています)。これは、移動の生成を支援するために、その「境界」の周りにセンチネルを含む 1 次元配列です。次のようになります。
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, "a8", "b8", "c8", "d8", "e8", "f8", "g8", "h8", -1,
-1, "a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7", -1,
-1, "a6", "b6", "c6", "d6", "e6", "f6", "g6", "h6", -1,
-1, "a5", "b5", "c5", "d5", "e5", "f5", "g5", "h5", -1,
-1, "a4", "b4", "c4", "d4", "e4", "f4", "g4", "h4", -1,
-1, "a3", "b3", "c3", "d3", "e3", "f3", "g3", "h3", -1,
-1, "a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2", -1,
-1, "a1", "b1", "c1", "d1", "e1", "f1", "g1", "h1", -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1
この配列を次のように生成できます (JavaScript で):
function generateEmptyBoard() {
var row = [];
for(var i = 0; i < 120; i++) {
row.push((i < 20 || i > 100 || !(i % 10) || i % 10 == 9)
? -1
: i2an(i));
}
return row;
}
// converts an index in the mailbox into its corresponding value in algebraic notation
function i2an(i) {
return "abcdefgh"[(i % 10) - 1] + (10 - Math.floor(i / 10));
}
もちろん、実際の実装では、ボード ラベルがある場所に実際のピース オブジェクトを配置します。ただし、負のもの（または同等のもの）を保持します。これらの場所は、その特別な値をチェックすることでいつボードから外れたかを簡単に知ることができるため、移動生成の苦痛を大幅に軽減します。
まず、ナイト (スライドしない駒) の正当な動きを生成する方法を見てみましょう。
function knightMoves(square, board) {
var i = an2i(square);
var moves = [];
[8, 12, 19, 21].forEach(function(offset) {
[i + offset, i - offset].forEach(function(pos) {
// make sure we're on the board
if (board[pos] != -1) {
// in a real implementation you'd also check whether
// the squares you encounter are occupied
moves.push(board[pos]);
}
});
});
return moves;
}
// converts a position in algebraic notation into its location in the mailbox
function an2i(square) {
return "abcdefgh".indexOf(square[0]) + 1 + (10 - square[1]) * 10;
}
有効な騎士の動きはピースの開始点から一定の距離にあることがわかっているため、それらの場所が有効であること (つまり、センチネル スクエアではないこと) を確認するだけで済みます。
スライドピースはそれほど難しくありません。ビショップを見てみましょう：
function bishopMoves(square, board) {
var oSlide = function(direction) {
return slide(square, direction, board);
}
return [].concat(oSlide(11), oSlide(-11), oSlide(9), oSlide(-9));
}
function slide(square, direction, board) {
var moves = [];
for(var pos = direction + an2i(square); board[pos] != -1; pos += direction) {
// in a real implementation you'd also check whether
// the squares you encounter are occupied
moves.push(board[pos]);
}
return moves;
}
ここではいくつかの例を示します。
knightMoves("h1", generateEmptyBoard()) => ["f2", "g3"]
bishopMoves("a4", generateEmptyBoard()) => ["b3", "c2", "d1", "b5", "c6", "d7", "e8"]
slide関数は一般的な実装であることに注意してください。他のスライディング ピースの正当な動きをかなり簡単にモデル化できるはずです。
于 2013-12-20T18:15:44.637 に答える
2
ビットボードを使用すると、チェス盤の状態を効率的に表すことができます。基本的な考え方は、ボード上の各正方形を表すために 64 ビット ビットセットを使用することです。通常、最初のビットは A1 (左下の正方形) を表し、64 番目のビットは H8 (対角線上の正方形) を表します。各プレイヤー (黒、白) の各タイプのピース (ポーン、キングなど) は、独自のビット ボードを取得し、これらの 12 のボードすべてがゲームの状態を構成します。詳細については、このウィキペディアの記事を参照してください。
于 2009-02-07T20:18:50.147 に答える
1
多次元配列を使用して、配列内の各要素がボード上の正方形へのグリッド参照になるようにします。
したがって
board = arrary(A = array (1,2,3,4,5,5,6,7,8),
B = array (12,3,.... etc...
etc...
)
次に、board[A][1]はボード スクエア A1 です。
実際には、文字ではなく数字を使用して、ピースの移動が許可されている場所の数学ロジックをシンプルに保ちます。
于 2008-09-02T16:09:31.340 に答える
0
int[8][8]
0=no piece
1=king
2=queen
3=rook
4=knight
5=bishop
6=pawn
白には正の整数を使用し、黒には負の整数を使用します
于 2008-09-02T16:05:21.600 に答える
0
これは非常に古い投稿であり、チェスのプログラミングをグーグルで調べているときに何度か出くわしたことは知っていますが、チェス盤などの 1D 配列でチェス盤をモデル化することは完全に実行可能であることを言及しなければならないと感じています[64]。
これがチェス盤表現への最も単純なアプローチだと思いますが、もちろん基本的なアプローチです。
1D チェス盤配列構造は、2D 配列 (インデックスにアクセスして操作するためにネストされた for ループが必要) よりも効率的ですか?
チェス盤[120]などのオフボードの正方形を表すために、64 を超える正方形の 1D 配列を使用することもできます。(アレイ センチネルとボード プレイ スクエアが正しく初期化された状態で)。
最後に、この記事を完全なものにするために、0x88 ボード アレイの表現について言及する必要があると思います。これは、ボード外の正方形も考慮したチェス盤を表す非常に一般的な方法です。
于 2014-02-23T09:37:46.067 に答える
0
チェス盤をモデル化するのではなく、駒の位置をモデル化するだけです。そうすれば、チェス盤の境界を持つことができます。
Piece.x= x position of piece
Piece.y= y position of piece
于 2009-02-07T20:21:25.023 に答える
-4
配列はおそらく問題ないでしょう。ボードを「トラバース」するためのより便利な手段が必要な場合は、データ構造の実装の詳細を抽象化するメソッドを簡単に構築できます。
于 2008-09-02T16:05:14.330 に答える