Quelles collections de pièces sont légales?

Dec 14 2020

Appelez une collection de pièces d'échecs (blanches et noires) légales si elles se produisent dans la position d'une partie d'échecs légale. Par exemple, KQRRBBNNPPPPPPPPkqrrbbnnppppppppest la collection au début du jeu. Il semble que n'importe quel sous-ensemble de ceci (contenant toujours les deux rois) soit également possible. Mais parfois, vous pouvez avoir beaucoup de promotions, par exemple, Kkqqqqqqqqc'est possible si le noir promeut les huit pions en reines alors que toutes les autres pièces sont capturées.

Quelles collections de pièces sont légales?

Cette réponse sur MathOverflow conjecture / déclare sans preuve que les collections légales sont celles qui peuvent être obtenues à partir de la collection de départ en utilisant les deux opérations suivantes:

  1. Supprimez toute pièce (non-roi) et promouvez au plus un pion blanc et au plus un pion noir.

  2. Supprimez un pion et promouvez au plus un pion de la même couleur et au plus deux pions de la couleur opposée.

Cette caractérisation est-elle correcte?

Réponses

6 Laska Jan 20 2021 at 02:04

Oui, la qualification est correcte et il y a 58 084 310 collections légales au total.

Pour avancer, nous avons besoin du bon niveau de discours, évitant une perte de précision tout en évitant de plonger dans des trivialités.

Nécessité et suffisance des mouvements de suppression

Deux types d'opérations ont été suggérés comme nécessaires et suffisants pour atteindre toutes les collections légales:

(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.

Premièrement, les deux critères sont nécessaires. Pour débloquer un fichier, une capture doit avoir lieu. Capturer un officier permettra aux deux pions d'un fichier de se promouvoir. Un pion capturant un pion à partir d'un fichier voisin est plus efficace, car il permet à trois pions de se promouvoir.

La condition est également suffisante, comme on peut le voir en divisant la carte en 4 paires de fichiers. Nous devons faire des suppositions que les rois peuvent se tenir à l'écart de l'action. Voir plus loin pour un exemple qui explore la validité de cette hypothèse.

"Offre et la demande"

Peut-être vaut-il la peine de passer à la question de savoir quelles collections sont réalisables de cette manière:

  1. Comptez le nombre "d'officiers non partants" visibles pour chaque camp (reines au-delà du premier; autres officiers au-delà du second de ce type): N_w & N_b
  2. Comptez le nombre de "pions awol" de chaque côté: (les pions transformés en NSO ne sont pas comptés): A_w & A_b
  3. Comptez le nombre "d'officiers manquants" pour chaque camp (reine manquante, ou autres officiers moins que le second de ce type): M_w & M_b

Ensuite, les élégantes inégalités «offre et demande» suivantes sont des critères nécessaires et suffisants pour une collecte légale:

M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b

Regroupant les termes par White & Black, le côté gauche est «l'offre», le côté droit est la «demande». L'offre est toujours non négative, donc si la demande est nulle ou inférieure, elle est toujours satisfaite. De même, une offre de 8+ répondra à toute demande qui peut survenir.

Voici un exemple. Pouvons-nous avoir 18 reines sur le plateau? Oui!

N_w = N_b = 8
(because 8 promoted pawns on each side)

A_w = A_b = 0
(every missing pawn was promoted)

M_w = M_b = 6
(all Rs, Bs & Ns were captured)

M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2

C'est donc légal. De même pour l'offre blanche pour la demande noire. Même si nous avions encore les chevaliers sur le plateau, donc M_b = M_w = 4, l'inégalité serait 4> = 4, donc toujours légale.

Mis à part le compagnon / l'impasse

Certains se demandent si une telle position peut être atteinte sans compagnon ni impasse, ce qui est une question légitime. La réponse est oui. C'est comme demander à prouver que 450 g de cornflakes rentrent tous dans une boîte. C'est une question d'expérience commune que l'on peut simplement secouer le paquet et que les cornflakes s'installent. Il n'y a pas trop de cornflakes dans la boîte. Bien que ce soit évidemment illégal, il est possible d'organiser les rois et jusqu'à 34 (!) Reines blanches sur le plateau sans compagnon ni impasse. À cette densité, cela devient un peu serré, mais cette expérience de pensée montre que lorsque nous avons affaire à seulement 18 reines, où de plus les reines amies peuvent se protéger contre les ennemis, il y a beaucoup de mou, et pas besoin de s'inquiéter des partenaires forcés. ou des impasses. Même avec 18 reines, l'échiquier est une boîte de cornflakes très vide :-)

Comptage des collections

Concentrons-nous d'abord uniquement sur les unités blanches. Combien y a-t-il de collections légales blanches? 8,694. Voici une preuve rapide.

Soit k le nombre de promotions visibles à la tour, au chevalier ou à l'évêque (c'est-à-dire les officiers au-delà de l'effectif initial de 2 pour n'importe lequel de ces types). (Pour des raisons de symétrie, les reines sont traitées dans quelques paragraphes à la place.)

Soit v (k) le nombre de combinaisons différentes de R, N, B qui y parviennent.

v(0) = 27:
because there may be 0-2 remaining of each of R,N,B. 

For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:

v(1) = again 27:
3 ways to pick one of R,N,B to be 3; 
& 0-2 possible for each of the other two types.

v(2) = 36:
27 ways to have 4,0-2,0-2; 
& 9 ways to have 3,3,0-2.

Ensuite, les autres pions de 8 k peuvent toujours être Ps, ou transformés en Q, ou capturés.

Soit q le nombre de promotions de reines visibles (c'est-à-dire que les reines au-delà du complément original de 1).

Soit u_k (q) le nombre de manières combinatoires différentes que nous pouvons atteindre (en termes de pions survivants, de reines et de pions capturés)

u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.

For q>0, u_k(q) = (9-k-q)

s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.

Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1

So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694

Toutes ces collections blanches sont en effet réalisables, par exemple s'il ne reste que le roi nu, mais en fait dans bien d'autres situations aussi: les inégalités offre / demande ne sont pas très exigeantes.

L'exercice suivant consiste à compter pour chaque combinaison de N_w, M_w, A_w le nombre de collections blanches existantes.

J'ai calculé le tableau suivant des nombres de collections, triés en fonction du nombre total de pièces sur le plateau, comme indiqué dans ce tableau:

Pour chaque nombre d'unités de 2 à 32, cela montre

  • v_0: le nombre de candidats de base sans se soucier de l'offre-demande,
  • v_1: le nombre qui a un seul échec face à l'offre-demande,
  • v_2: le nombre qui a un double échec face à l'offre-demande.

Pour éviter un double comptage, le nombre de positions légales est calculé comme suit: v_1 - 2 * v_2 + v_3. Mes calculs correspondent exactement aux résultats antérieurs de Kryukov .

Notez qu'il n'y a pas d'échec jusqu'à ce que l'on atteigne 25 unités. En effet, avec 8 captures, toutes les collections de promotion des candidats peuvent être réalisées.

Une question ouverte "crédit supplémentaire" (travail en cours)

Les amateurs de rétro font la distinction entre la couleur des carrés sur lesquels se trouvent les évêques, car c'est un invariant. Cela a un impact majeur et visible sur la légalité potentielle, fait partie de la classification essentielle des bases de table d'échecs, et constitue également une préoccupation esthétique dans la composition. Le terme correspondant est alors «officiers non standard» (reines ou évêques «teintés» au-delà du premier; tours ou chevaliers au-delà du second). Le décompte des officiers disparus est basé sur les 5 mêmes types. La détermination des inégalités supplémentaires nécessaires et suffisantes pour caractériser les collections légales est désormais beaucoup plus compliquée.

La meilleure approche peut être d'appliquer d'abord les inégalités adaptées offre / demande. Puis pouvez-vous demander combien de captures de pions supplémentaires sont nécessaires pour «pousser» certains évêques à la bonne teinte?

Une capture de pion d'un officier / pion se traduira par un lot de respectivement 2/3 pions tous promus sur les mêmes carrés de teinte, mais il semble que pour chacun de ces lots, nous sommes libres de choisir la teinte indépendamment.