最初に、チェスエンジンの実装の完全な説明をしたかった（私はそれをセンチュリオンと呼んだ）。 しかし、その後、私は本が記事ではなくこのトピックについて書かれていることに突然気付きました。 記事の形式では、チェスプログラムのすべてのコンポーネントを実装の詳細とともに詳細に説明することは不可能です。 したがって、チェスエンジンの一般的な説明に限定し、そのソースコードとプログラム自体へのリンクを提供することにしました。 Windows用のプログラムは次のようになります。
Windows用プログラム。
フィールド（E2-E4）に動きを入力するか、マウスを使用して歩くことができます-左ボタンはどこから、右ボタンはどこからです。
それでは始めましょう。
まず、チェスプログラムの作成方法に関する特別な文献を探す価値があります。 これらのうち、2005年のコルニロフの著書「チェスとその他の論理的なタスクのプログラミング」を使用しました。 この本だけでは十分ではありませんでした-著者は重要なことに集中せず、単に何かを語りませんでした。 ところで、これは検索ツリーを大幅に削減するものです。 エンジンがビットマップに基づくストロークジェネレーターを使用していないことをすぐに警告します。 このレベルはまだ利用できません。 しかし、私は特にそれらに対処しようとはしませんでした。速度を犠牲にした場合でも、エンジンの動きを処理するための最も透過的な（私にとって）メカニズムを書くことを好みました。
最初に考える必要があるのは、競技場をどのように提示するかです。 各セルを整数として表現するのが非常に便利であることがわかります。整数の個々のビットは、このセルのパラメーターを担当します。 セルにマクロを設定しました
#define CELL long
そして、セル自体はAHIIIIEWB0MFFFとしてビットで表されます。ここで：
W字ホワイト
B型ブラック
Fタイプのフィギュア（0フィギュアNo）
M-フィギュアが歩いたかどうか
Eエッジボード
図を検索するための配列内の図のIインデックス（0〜15）
Hは短いキャスリングでした（旗は王とルークにのみ配置されます）
A-は長いキャスリングでした（旗は王とルークにのみ置かれます）
ビットを使用した便利な表現とは何ですか？ マスクを適用すると、どの種類のセルであるかをすばやく判断できます。 特にこのために、マスクを設定しました：
#define BYTE8(b7,b6,b5,b4,b3,b2,b1,b0) ((CELL)((b7<<7)|(b6<<6)|(b5<<5)|(b4<<4)|(b3<<3)|(b2<<2)|(b1<<1)|(b0<<0))) //---------------------------------------------------------------------------------------------------- // //---------------------------------------------------------------------------------------------------- // #define FIGURE_TYPE_KING 1 // #define FIGURE_TYPE_QUEEN 2 // #define FIGURE_TYPE_ROOK 3 // #define FIGURE_TYPE_BISHOP 4 // #define FIGURE_TYPE_KNIGHT 5 // #define FIGURE_TYPE_PAWN 6 // #define BLACK BYTE8(0,0,1,0,0,0,0,0) #define WHITE BYTE8(0,1,0,0,0,0,0,0) // #define CASTLING_O_O (BYTE8(0,0,0,1,0,0,0,0)<<8) // #define CASTLING_O_O_O (BYTE8(0,1,0,0,0,0,0,0)<<8) // #define INDEX_SHIFT 8 // #define MASK_WHITE WHITE // #define MASK_BLACK BLACK // #define MASK_COLOR (MASK_WHITE|MASK_BLACK) // #define MASK_TYPE BYTE8(0,0,0,0,0,1,1,1) // #define MASK_BORDER BYTE8(1,0,0,0,0,0,0,0) //, #define MASK_IS_MOVED BYTE8(0,0,0,0,1,0,0,0) // #define MASK_INDEX ((BYTE8(0,0,0,0,1,1,1,1))<<INDEX_SHIFT) // #define MASK_CASTLING (BYTE8(0,0,1,1,0,0,0,0)<<8) // #define CELL_EMPTY 0
次に、ボードのサイズを決定します。 8x8は、ボードを超える分析には不便です。 中央にボードがある16x16アレイを指定して、ボードではないすべてのセルに境界フラグを設定する方がはるかに便利です。 この場合、X座標の変更は、X座標を目的のステップだけ変更し、Yをステップ* 16だけ変更することによって発生します。 ボードは次のように設定されています
CELL Board[256];// (16x16).
将来的に8x8フィールドにいくつかのパラメータを設定すると便利です;この目的のために、16x16フィールドから8x8フィールドへの座標変換の配列を作成する価値があります。
ところで、ボード全体をスキャンする必要がないように、ボード上のピースがどこにあるかを覚えておく価値があります。 たとえば、次のように：
#define COORD long COORD FigureWhiteCoord256[16];// ( . 0- ) COORD FigureBlackCoord256[16];// ( . 0- ) COORD *KingWhitePointer;// COORD *KingBlackPointer;//
次に、移動の設定方法を決定します。 これは非常に便利です。
long KingMove[9]={16,-16,1,-1,17,-17,15,-15,0};// long QueenMove[9]={16,-16,1,-1,17,-17,15,-15,0};// long RookMove[5]={16,-16,1,-1,0};// long BishopMove[5]={17,-17,15,-15,0};// long KnightMove[9]={32+1,32-1,16+2,16-2,-(32+1),-(32-1),-(16+2),-(16-2),0};//
ここで、配列では、16x16ボードの空間の座標が図の1ステップに設定されています。 ポーンの動きは単純な動きであるため、ポーンの動きを個別に考慮するのが便利ですが、通路に特定のキャプチャがあります。
そのような配列を使用するには？ さて、たとえば、女王のすべての動きをコンパイルします：
long n; CELL cell=Board[coord256]; FIGURE_COLOR color=cell&MASK_COLOR; FIGURE_COLOR opponent_color=color^(WHITE|BLACK); FIGURE_TYPE type=cell&MASK_TYPE; //-------------------------------------------------- // //-------------------------------------------------- if (type==FIGURE_TYPE_QUEEN) { n=0; while(QueenMove[n]!=0) { COORD c256=coord256+QueenMove[n]; while(Board[c256]==CELL_EMPTY)// { Move_AddMove(coord256,c256,FIGURE_TYPE_QUEEN,MOVE_TYPE_SIMPLY,sMove_Ptr,move,sMove_FirstPtr,sMoveKitPtr);// , c256+=QueenMove[n]; } cell=Board[c256]; if ((cell&MASK_COLOR)==opponent_color)// { Move_AddEatMove(coord256,c256,FIGURE_TYPE_QUEEN,MOVE_TYPE_SIMPLY,sMove_EatPtr,move_eat,sMove_FirstEatPtr,sMoveKitPtr);// } n++; } return; }
ご覧のとおり、すべてがシンプルです。 動きを作成するために、構造を作成しました
// enum MOVE_TYPE { MOVE_TYPE_EMPTY=-1,// MOVE_TYPE_SIMPLY=0,// MOVE_TYPE_CASTLING=1,// MOVE_TYPE_WHITE_PASSED_PAWN_EAT=2,// MOVE_TYPE_BLACK_PASSED_PAWN_EAT=3,// MOVE_TYPE_CONVERSION=4,// }; // struct SMove { // COORD Coord256_1; // COORD Coord256_2; MOVE_TYPE MoveType;// FIGURE_TYPE NewFigureType;// , COORD Coord256_PassedPawn;// ( . 0- ) ENGINE_BOOL IsEat;//- // ( ) long Score; // SMove *sMove_NextPtr; };
動きの配列は次のように設定されていますが
SMove sMove_Level[MAX_PLY+5][200];// SMove sMove_EatLevel[MAX_PLY+5][200];//
ここで、MAX_PLYは最大分析深度（および200は任意のピースの移動の最大数（マージンあり））ですが、次の要素sMove_NextPtrへのポインターを使用すると、移動を簡単に並べ替えることができます（並べ替える必要があります）。 std :: list（またはstlの何か）を使用しませんでした-ここではパフォーマンスが非常に重要です（また、stlと現代のC ++のマスターが逆であるとは言いません）。 ただし、stlでそれを実行し、プログラムの速度を比較できます-私はこれをチェックしませんでした。
さて、一般的に、私たちは動きを終えました。アルゴリズムに移りましょう。
まず、位置推定機能が必要です。 ここでは、可能性は海だけです。 engine_score.cppのエンジンでは、位置の評価に使用するすべてのものが完全に読み取り可能です。 フィールドの特定のセルで図を見つけるためのポイントの配列がそこに表示されます（8x8フィールドの場合-設定がとても簡単です）。
第二に、バウンス償却を伴うアルファベータが必要です。 アルファベータアルゴリズム自体を検討するのは無意味だと思います。このトピックについては多くの記事や本が書かれています。 そして一般的に、それ（またはその修正）は多くのチェスプログラムの基礎です。 チェスプログラムで最も興味深いのは、このアルゴリズムの移動回数を減らす方法です。
第三に、ハッシュテーブルが必要です。 事実、チェスでは検索の位置が頻繁に繰り返されるということです-すでに見たものを再分析する必要があるのはなぜですか？ この位置を特定し、ハッシュテーブルを許可します。 あるアイテムを別のアイテムと区別する「一意の」値を格納します。 これらの「一意の」値は、位置を記述する要素のキーでxor操作を実行するだけの価値があります。 したがって、一意の64ビット数の配列が必要になります（他の次元を使用できます。唯一の問題は、同じ位置値が異なる位置に対応する頻度-ハッシュエラーです）。 私のテーブルは次のように記述されています：
//---------------------------------------------------------------------------------------------------- //- //---------------------------------------------------------------------------------------------------- //- [ ][ ][ 16x16] unsigned __int64 ZobristKey[FIGURE_TYPE_PAWN+1][2][256]=
また、コースを変更するためのキーも必要になります（位置は同じでも、フィギュアの色が異なるため）。 そして、いわゆるゼロムーブの特別なキー（ゼロムーブ自体については後述します）。 私が覚えている限りでは、コルニロフは彼の本の中でこれらの最後の2つの鍵について言及していませんでした。
unsigned __int64 ZobristKeyMove=0x54ca3eb5b5f3cb5b;// unsigned __int64 ZobristKeyNullMove=0x08d9bc25bebf91b1;//
一意性チェックで毎回生成しないように、これらのすべてのキーをプログラムでしっかりと設定します。
次に、どのようなことが起こるかを確認します。最初にボード上のピースのすべてのキーをxor実行して位置を取得する場合
//---------------------------------------------------------------------------------------------------- // - //---------------------------------------------------------------------------------------------------- unsigned __int64 Hash_GetHKey(void) { unsigned __int64 key=0; COORD coord256=4*16+4; for(long y=0;y<8;y++,coord256+=16) { COORD coord256_local=coord256; for(long x=0;x<8;x++,coord256_local++) { CELL cell=Board[coord256_local]; FIGURE_COLOR color=cell&MASK_COLOR; FIGURE_TYPE type=cell&MASK_TYPE; if (type==0) continue; if (color==WHITE) key^=ZobristKey[type][ZOBRIST_WHITE][coord256_local]; if (color==BLACK) key^=ZobristKey[type][ZOBRIST_BLACK][coord256_local]; } } return(key); }
、移動の実行中に、ご覧のとおり、古い場所のシェイプキーの位置xorの現在のハッシュ値と、新しい場所のシェイプキーのxorで十分です。 そのため、キャプチャがあります。 これにより、位置をソートするプロセスでハッシュ値をすばやく計算できます。
第4に、履歴統計などが必要です。 これは何ですか ゲーム中に、いくつかの動きがポジションの評価を改善することに気づくでしょう。 この事実に注目し、移動をソートするときにそれを覚えてから使用する価値があります。 どうやってやるの？ 配列[64] [64]（[フィールド8x8での図の初期位置] [フィールド8x8での図の最終位置]）を開始します。最適な移動の選択の評価の開始時にゼロになります。ポジション評価。
第五に、ある種の動きが必要です。 一番最初の動きは、位置を評価することの最大の利点がある動きでなければなりません。 キャプチャの動きが通常の「サイレント」の動きよりも高いことは明らかです。 キャプチャの動きはMVV / LVAの原則に従ってソートされます（最も価値のある被害者は価値の最も低いストライカーです）。 同時に、すべての異常な動きをキャプチャでプロモートする価値があります（MOVE_TYPE_SIMPLY型ではないすべての動き）。 また、最後に前進した相手の駒のキャプチャを進めることも価値があります（キャプチャがある場合）。 通常の移動は、履歴のヒューリスティックを考慮して、位置によって昇順にソートされます。 このソートはすべて非常に重要です！ それ自体で、ゲームツリーのラウンドを減らすことができますが、さらに、ツリーの下位レベルでは、原則として、ゲームの品質を損なうことなく、ほぼすべての「静かな」動き（および王がチェックされていない場合）を考慮することができます！ Ifritチェスプログラムのコードでこれを見て、もちろん適用しました。 私が理解しているように、これは後期移動削減と呼ばれます。
これを行うには、次の配列を使用します。
static const long FutilityMoveCount[9]={19,19,19,19,19,35,67,131,259};
ここで、数字は、ツリーのレベルに応じて分析される「サイレント」ムーブの数を意味します（配列は逆の順序で与えられます）。 つまり、分析のツリーの最後の9レベルで、レビューは最初に259の動き、次に131、67のように19になります。これにより、プログラムが大幅に高速化されます（コルニロフはこのことについても彼の本で語っていなかったようです）。 もちろん、動きをソートしないと、このクリッピングは機能しません。
第6に、キャプチャとシャーの分析を拡張する必要があります。 これにより、位置評価の精度が向上します。
7番目に、キラーヒューリスティックが必要です。 それは、木の枝を分析するとき、最初に前の枝でクリッピングを引き起こした動きを試みるという事実にあります。 このテクニックはバストも低減します。 このような移動は「サイレント」にしかできないことに注意してください。キャプチャや異常な移動は、このようなチェックには使用できません。
第八に、ゼロムーブなどがあります。 重要なのは、移動をスキップして、どのように悪いことが起こるかを確認できるということです。 同時に、ツリー分析の深さを減らすことができます（削減を行います）-とにかく、予備評価。 主なことは、この非常にゼロの動きのキーで位置ハッシュをマークすることを忘れないことです
9番目に、Futility Prunningもあります。 これは何ですか ツリーの最後の2つのハーフウォークでは、位置の推定値が正確でない場合があります（ゼロ移動ではない場合、移動がチェックでなく、取得であり、移動が分岐分析の延長でない場合）。また、位置推定値の差がいくつかの小さな値よりも大きい場合、この推定値を返すだけで、詳細な分析は行いません。 この手法により、プログラムの速度も向上します。
10番目に、オプションを減らすためにRazoringも発明されました。 これはFutility Prunningとほぼ同じですが、最後の4つの半分の動きを指し、推定値の限界は許容される数字の損失という一定のコストで設定されます。
11番目に、分析でいくつかの動きを拡張する必要があります。 これらには、敵の駒を王に近づける、捕まえる、確認するという動きが含まれます。 個別の分析機能を使用してそれを延長することをお勧めします。この機能では、チェッカーのみを対象に完全な検索を実行する価値があります。 残りの動きについては、キャプチャの動きだけを分析すれば十分です。 これは静的検索と呼ばれます。
12番目に、プリンシパルバリエーション（大きな変化）のようなものがまだあります。 これは、プログラムが現時点で最良と考えるゲームのラインです。 この行は、位置の検索中に常に調整されます。 ソート中のメインラインからの移動は前方に移動する必要があります。
まあ、すべては私のチェスエンジンを使用するセットからのようです。 エンジンはすでに2年前のものであり、同じ方法で触っておらず、何かを完全に忘れてしまう可能性があるため、どこにもめちゃくちゃにならなかったことを願っています。
エンジン自体はアーカイブ （UCIをサポートしているため、Arenaに接続できます）、それで遊ぶためのWindowsプログラム（ホイップアップ）、QNX 6.3のチェスにあります。 ゲームのレベルを正確に評価することはできません（私はチェスプレーヤーではありませんが、奇妙なことに）、それは非常にうまくいくようです。
githubへのリンクを追加しました：
チェス