更新：私はこのトピックがとても好きで、プログラミングパズル、チェスの位置、ハフマンコーディングを書きました。これを読んだ場合、完全なゲーム状態を保存する唯一の方法は、動きの完全なリストを保存することであると判断しました。理由を読んでください。そのため、ピースのレイアウトには、問題の少し簡略化されたバージョンを使用します。
問題
この画像は、チェスの開始位置を示しています。チェスは8x8のボードで発生し、各プレーヤーは、次の図に示すように、8つのポーン、2つのルーク、2つのナイト、2つのビショップ、1つのクイーン、1つのキングで構成される16個の同一のセットから始まります。
位置は通常、列の文字とそれに続く行の番号として記録されるため、ホワイトのクイーンはd1にあります。移動は、ほとんどの場合、代数表記で保存されます。これは明確であり、通常、必要な最小限の情報のみを指定します。この開口部を検討してください：
- e4 e5
- Nf3 Nc6
- …</li>
これは次のように解釈されます。
- 白は王のポーンをe2からe4に移動します（e4、つまり「e4」に到達できる唯一の駒です）。
- 黒は王のポーンをe7からe5に移動します。
- 白は騎士（N）をf3に移動します。
- 黒は騎士をc6に移動させます。
- …</li>
ボードは次のようになります。
プログラマーにとって重要な能力は、問題を正確かつ明確に特定できることです。
では、何が欠けているか、あいまいですか？結局のところ、たくさんあります。
ボード状態とゲーム状態
最初に決定する必要があるのは、ゲームの状態を保存するのか、ボード上のピースの位置を保存するのかです。ピースの位置を単純にエンコードすることは1つのことですが、問題は「その後のすべての法的措置」を意味します。この問題は、この時点までの動きを知ることについても何も述べていません。これから説明するように、これは実際には問題です。
キャスリング
ゲームは次のように進行しました。
- e4 e5
- Nf3 Nc6
- Bb5 a6
- Ba4 Bc5
ボードは次のようになります。
白にはキャスリングのオプションがあります。このための要件の一部は、キングと関連するルークが移動することはできないということです。そのため、キングまたは各サイドのルークのいずれかが移動したかどうかを保存する必要があります。明らかに、開始位置にない場合は移動しています。そうでない場合は、指定する必要があります。
この問題に対処するために使用できるいくつかの戦略があります。
まず、追加の6ビットの情報（ルークとキングごとに1つ）を保存して、そのピースが移動したかどうかを示すことができます。適切なピースが入っている場合は、これらの6つの正方形の1つにビットを格納するだけで、これを合理化できます。または、動かない各ピースを別のピースタイプとして扱うこともできます。そのため、各サイドに6つのピースタイプ（ポーン、ルーク、ナイト、ビショップ、クイーン、キング）の代わりに、8つ（動かないルークと動かないキングを追加）があります。
アンパッサン
チェスのもう1つの独特で、しばしば無視されるルールは、アンパッサンです。
ゲームが進行しました。
- e4 e5
- Nf3 Nc6
- Bb5 a6
- Ba4 Bc5
- OO b5
- Bb3 b4
- c4
b4の黒のポーンには、b4のポーンをc3に移動して、c4の白のポーンを取得するオプションがあります。これは最初の機会にのみ発生します。つまり、ブラックがオプションを渡した場合、次の動きをとることができなくなります。したがって、これを保存する必要があります。
前の動きを知っていれば、アンパッサンが可能であれば間違いなく答えることができます。または、4番目のランクの各ポーンが2回前進して、そこに移動したかどうかを保存することもできます。または、ボード上の可能な各アンパッサンの位置を見て、それが可能かどうかを示すフラグを立てることもできます。
昇進
ホワイトの動きです。ホワイトがh7からh8にポーンを移動すると、他のピースに昇格できます（ただしキングは昇格できません）。99％の確率で女王に昇格しますが、昇格しない場合もあります。通常、そうでない場合は勝つと膠着状態になる可能性があるためです。これは次のように書かれています：
- h8 = Q
これは私たちの問題において重要です。なぜなら、それは、両側に固定された数のピースがあることを期待できないことを意味するからです。8つのポーンすべてが昇格した場合、片側が9つのクイーン、10のルーク、10のビショップ、または10のナイトになる可能性は完全にあります（ただし、信じられないほどありそうにありません）。
膠着状態
あなたが最善の戦術を勝ち取ることができない立場にあるときは、膠着状態を試みることです。最も可能性の高い変種は、合法的な移動を行うことができない場合です（通常、キングをチェックしたときに移動が発生するため）。この場合、引き分けを請求できます。これは簡単に対応できます。
2番目の変形は、 3回の繰り返しによるものです。同じボードポジションがゲームで3回発生した場合（または次の手で3回発生する場合）、ドローを要求できます。位置は特定の順序で発生する必要はありません（つまり、同じ一連の移動を3回繰り返す必要はありません）。これは、以前のすべてのボード位置を覚えておく必要があるため、問題を非常に複雑にします。これが問題の要件である場合、問題に対する唯一の可能な解決策は、以前のすべての動きを保存することです。
最後に、50手ルールがあります。ポーンが移動しておらず、前の50回の連続した移動で駒が取られていない場合、プレーヤーは引き分けを要求できます。そのため、ポーンが移動された、または駒が取られてからの移動数を保存する必要があります（2つのうち最新のもの。これには必要です。 6ビット（0-63）。
誰の番ですか？
もちろん、それが誰の番かを知る必要もあります。これはほんの少しの情報です。
2つの問題
膠着状態の場合のため、ゲームの状態を保存するための唯一の実行可能または賢明な方法は、この位置につながったすべての動きを保存することです。その1つの問題に取り組みます。ボードの状態の問題はこれに単純化されます。キャスリング、アンパッサン、膠着状態を無視してボード上のすべてのピースの現在の位置を保存し、その順番はです。
ピースのレイアウトは、各正方形の内容を保存するか、各ピースの位置を保存するかの2つの方法のいずれかで広く処理できます。
シンプルな内容
6つのピースタイプ（ポーン、ルーク、ナイト、ビショップ、クイーン、キング）があります。各ピースは白または黒にすることができるので、正方形には12個の可能なピースの1つを含めることができます。または、空にすることで13個の可能性があります。13は4ビット（0〜15）で格納できるため、最も簡単な解決策は、各正方形に4ビットを掛けて64平方または256ビットの情報を格納することです。
この方法の利点は、操作が非常に簡単で高速であることです。これは、ストレージ要件を増やすことなく、さらに3つの可能性を追加することで拡張することもできます。最後のターンで2スペース移動したポーン、移動していないキング、移動していないルークです。前述の問題の。
しかし、私たちはもっとうまくやることができます。
ベース13エンコーディング
ボードの位置を非常に大きな数と考えると役立つことがよくあります。これは、コンピュータサイエンスでよく行われます。たとえば、停止問題はコンピュータプログラムを（正しく）多数として扱います。
最初のソリューションでは、位置を64桁の16進数として扱いますが、示されているように、この情報には冗長性があり（「桁」あたり3つの未使用の可能性があるため）、数値スペースを64進数の13桁に減らすことができます。もちろん、これはベース16ほど効率的に行うことはできませんが、ストレージ要件を節約できます（そして、ストレージスペースを最小限に抑えることが私たちの目標です）。
基数10では、数値234は2 x 10 2 + 3 x 10 1 + 4 x100に相当します。
基数16では、数値0xA50は10 x 16 2 + 5 x 16 1 + 0 x 16 0 = 2640（10進数）に相当します。
したがって、位置をp 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0としてエンコードできます。ここで、 piは正方形iの内容を表します。
2256は約1.16e77に相当します。13 64は約1.96e71に相当し、237ビットのストレージスペースが必要です。わずか7.5％の節約には、操作コストが大幅に増加します。
可変ベースエンコーディング
法務委員会では、特定の部分が特定の正方形に表示されない場合があります。たとえば、ポーンは1番目または8番目のランクでは発生しないため、これらの正方形の可能性は11に減少します。これにより、可能なボードは11 16 x 13 48 = 1.35e70（約）に減少し、233ビットのストレージスペースが必要になります。
実際には、このような値を10進数（または2進数）との間でエンコードおよびデコードするのは少し複雑ですが、確実に実行でき、読者の練習問題として残されています。
可変幅アルファベット
前の2つの方法は、どちらも固定幅のアルファベットエンコーディングとして説明できます。アルファベットの11、13、または16の各メンバーは、別の値に置き換えられます。各「文字」は同じ幅ですが、各文字の可能性が同じではないことを考慮すると、効率を向上させることができます。
モールス信号（上の写真）を考えてみましょう。メッセージ内の文字は、ダッシュとドットのシーケンスとしてエンコードされます。それらのダッシュとドットは、それらを区切るためにそれらの間に一時停止を入れて（通常）無線で転送されます。
文字E（英語で最も一般的な文字）が単一のドットであり、可能な限り短いシーケンスであるのに対し、Z（最も頻度が低い）は2つのダッシュと2つのビープ音であることに注意してください。
このようなスキームは、予想されるメッセージのサイズを大幅に削減できますが、ランダムな文字シーケンスのサイズを増やすという犠牲を伴います。
モールス信号には別の機能が組み込まれていることに注意してください。ダッシュは3ドットの長さであるため、ダッシュの使用を最小限に抑えるために、上記のコードはこれを念頭に置いて作成されています。1と0（ビルディングブロック）にはこの問題がないため、複製する必要のある機能ではありません。
最後に、モールス信号には2種類の休符があります。短い休符（ドットの長さ）は、ドットとダッシュを区別するために使用されます。より長いギャップ（ダッシュの長さ）は、文字を区切るために使用されます。
では、これは私たちの問題にどのように当てはまりますか？
ハフマン符号化
ハフマン符号化と呼ばれる可変長符号を処理するためのアルゴリズムがあります。ハフマンコーディングは、可変長コード置換を作成します。通常、シンボルの予想される頻度を使用して、より一般的なシンボルに短い値を割り当てます。
上記のツリーでは、文字Eは000（または左-左-左）としてエンコードされ、Sは1011です。このエンコード方式が明確であることは明らかです。
これはモールス信号との重要な違いです。モールス信号には文字区切り文字があるため、あいまいな置換を行うことができます（たとえば、4つのドットはHまたは2 Isになります）が、1と0しかないため、代わりに明確な置換を選択します。
以下は簡単な実装です。
private static class Node {
private final Node left;
private final Node right;
private final String label;
private final int weight;
private Node(String label, int weight) {
this.left = null;
this.right = null;
this.label = label;
this.weight = weight;
}
public Node(Node left, Node right) {
this.left = left;
this.right = right;
label = "";
weight = left.weight + right.weight;
}
public boolean isLeaf() { return left == null && right == null; }
public Node getLeft() { return left; }
public Node getRight() { return right; }
public String getLabel() { return label; }
public int getWeight() { return weight; }
}
静的データの場合：
private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;
static {
List<string> list = new ArrayList<string>();
list.add("White");
list.add("Black");
COLOURS = Collections.unmodifiableList(list);
Map<string, integer> map = new HashMap<string, integer>();
for (String colour : COLOURS) {
map.put(colour + " " + "King", 1);
map.put(colour + " " + "Queen";, 1);
map.put(colour + " " + "Rook", 2);
map.put(colour + " " + "Knight", 2);
map.put(colour + " " + "Bishop";, 2);
map.put(colour + " " + "Pawn", 8);
}
map.put("Empty", 32);
WEIGHTS = Collections.unmodifiableMap(map);
}
と：
private static class WeightComparator implements Comparator<node> {
@Override
public int compare(Node o1, Node o2) {
if (o1.getWeight() == o2.getWeight()) {
return 0;
} else {
return o1.getWeight() < o2.getWeight() ? -1 : 1;
}
}
}
private static class PathComparator implements Comparator<string> {
@Override
public int compare(String o1, String o2) {
if (o1 == null) {
return o2 == null ? 0 : -1;
} else if (o2 == null) {
return 1;
} else {
int length1 = o1.length();
int length2 = o2.length();
if (length1 == length2) {
return o1.compareTo(o2);
} else {
return length1 < length2 ? -1 : 1;
}
}
}
}
public static void main(String args[]) {
PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
new WeightComparator());
for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
queue.add(new Node(entry.getKey(), entry.getValue()));
}
while (queue.size() > 1) {
Node first = queue.poll();
Node second = queue.poll();
queue.add(new Node(first, second));
}
Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
addLeaves(nodes, queue.peek(), "");
for (Map.Entry<string, node> entry : nodes.entrySet()) {
System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
}
}
public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
if (node != null) {
addLeaves(nodes, node.getLeft(), prefix + "0");
addLeaves(nodes, node.getRight(), prefix + "1");
if (node.isLeaf()) {
nodes.put(prefix, node);
}
}
}
考えられる出力の1つは次のとおりです。
White Black
Empty 0
Pawn 110 100
Rook 11111 11110
Knight 10110 10101
Bishop 10100 11100
Queen 111010 111011
King 101110 101111
開始位置の場合、これは32 x 1 + 16 x 3 + 12 x 5 + 4 x 6=164ビットに相当します。
状態の違い
別の可能なアプローチは、最初のアプローチをハフマンコーディングと組み合わせることです。これは、（ランダムに生成されたものではなく）最も期待されるチェスボードが、少なくとも部分的には開始位置に似ている可能性が高いという仮定に基づいています。
つまり、256ビットの現在のボード位置と256ビットの開始位置をXORしてから、それをエンコードします（ハフマンコーディング、またはランレングスエンコードの何らかの方法を使用）。明らかに、これは最初は非常に効率的です（64 0はおそらく64ビットに対応します）が、ゲームが進むにつれて必要なストレージが増えます。
ピースの位置
前述のように、この問題を攻撃する別の方法は、代わりにプレーヤーが持っている各ピースの位置を保存することです。これは、ほとんどの正方形が空になるエンドゲームの位置で特にうまく機能します（ただし、ハフマンコーディングのアプローチでは、空の正方形はとにかく1ビットしか使用しません）。
それぞれの側に王と0-15の他の部分があります。プロモーションのため、これらのピースの正確な構成は十分に異なる可能性があるため、開始位置に基づく数が最大であると想定することはできません。
これを分割する論理的な方法は、2つの側面（白と黒）で構成される位置を保存することです。各サイドには：
- キング：場所は6ビット。
- ポーンあり：1（はい）、0（いいえ）;
- はいの場合、ポーンの数：3ビット（0-7 + 1 = 1-8）;
- はいの場合、各ポーンの位置は次のようにエンコードされます。45ビット（以下を参照）。
- 非ポーンの数：4ビット（0-15）;
- 各ピースの場合：タイプ（クイーン、ルーク、ナイト、ビショップの場合は2ビット）と場所（6ビット）
ポーンの位置に関しては、ポーンは48個の可能な正方形にのみ配置できます（他の正方形のように64個ではありません）。そのため、ポーンごとに6ビットを使用する場合に使用する余分な16個の値を無駄にしない方がよいでしょう。したがって、ポーンが8つある場合、 28,179,280,429,056に相当する488の可能性があります。その数の値をエンコードするには、45ビットが必要です。
これは、片側105ビット、つまり合計210ビットです。ただし、開始位置はこの方法の最悪のケースであり、ピースを削除すると大幅に改善されます。
ポーンをすべて同じ正方形に配置することはできないため、可能性は48 8未満であることに注意してください。最初の可能性は48、2番目の可能性は47というように続きます。48 x47x…x41= 1.52e13=44ビットストレージ。
これをさらに改善するには、他のピース（反対側を含む）が占める正方形を削除して、最初に白の非ポーン、次に黒の非ポーン、次に白のポーン、最後に黒のポーンを配置します。開始位置では、これによりストレージ要件が白の場合は44ビット、黒の場合は42ビットに削減されます。
組み合わせたアプローチ
もう1つの可能な最適化は、これらのアプローチのそれぞれに長所と短所があることです。たとえば、最適な4つを選択し、最初の2ビットでスキームセレクターをエンコードし、その後にスキーム固有のストレージをエンコードすることができます。
オーバーヘッドが非常に小さいため、これが最善のアプローチになります。
ゲームの状態
ポジションではなくゲームを保存するという問題に戻ります。3回繰り返されるため、この時点までに発生した移動のリストを保存する必要があります。
注釈
決定しなければならないことの1つは、単に動きのリストを保存するのか、それともゲームに注釈を付けるのかということです。チェスゲームには、多くの場合、次のように注釈が付けられます。
- Bb5 !! Nc4？
ホワイトの動きは2つの感嘆符で見事にマークされていますが、ブラックの動きは間違いと見なされています。チェスの句読点を参照してください。
さらに、動きが説明されているときにフリーテキストを保存する必要がある場合もあります。
注釈がないように、移動は十分であると想定しています。
代数表記
ここに移動のテキスト（「e4」、「Bxb5」など）を保存するだけで済みます。終了バイトを含めると、移動ごとに約6バイト（48ビット）が表示されます（最悪の場合）。それは特に効率的ではありません。
次に試すことは、開始位置（6ビット）と終了位置（6ビット）を格納して、移動ごとに12ビットにすることです。それはかなり良いです。
あるいは、予測可能で決定論的な方法で現在の位置からのすべての法的措置を決定し、選択した状態を示すことができます。次に、これは上記の可変ベースエンコーディングに戻ります。白と黒には、最初の動きでそれぞれ20の可能な動きがあり、2番目の動きでさらに多くの動きがあります。
結論
この質問に対する絶対的な正しい答えはありません。上記がほんの数例である多くの可能なアプローチがあります。
この問題や同様の問題について私が気に入っているのは、使用パターンを検討したり、要件を正確に決定したり、コーナーケースについて考えたりするなど、プログラマーにとって重要な能力が必要なことです。
ChessPositionTrainerからスクリーンショットとして取得されたチェスの位置。