Implementazione dell'algoritmo per generare posizioni di scacchi

Il numero di tutte le possibili posizioni che coinvolgono KBBK e uno scacco matto non è affatto grande: 32 quadrati per l'alfiere quadrato chiaro * 32 per il vescovo quadrato scuro * 62 per il re Bianco (64 - 2 già presi da entrambi i vescovi) * tutte le caselle in cui il re nero è controllato da uno dei vescovi (deve essere sotto controllo, altrimenti non è ancora scacco matto - o non è un "compagno in 0", se preferisci).

Quindi, dato che la generazione di tablebase di endgame è intensiva dal punto di vista computazionale, è possibile trovare facilmente tutte le posizioni in base alla forza bruta. Sarà super veloce. È una piccola parte del lavoro totale che devi fare comunque.

Per tutte le 63488 posizioni che KBB può occupare (e potresti ridurre questo numero perché la scacchiera è simmetrica - 63448/2 (specchiato orizzontalmente) / 2 (speculare verticalmente) = 15862), quindi per ognuno di questi 15.000 le posizioni trovano tutte le caselle in cui il re nero viene controllato da uno dei vescovi.

Ora per ciascuno di questi quadrati vedi se c'è una casella in cui il re nero potrebbe andare per scappare dall'assegno. Se non ce n'è, è una posizione scacco matto. Risciacqua e ripeti.

Già una buona risposta qui, ma cerco di evidenziare il problema da un punto di vista leggermente diverso. Quando si intende implementare un'analisi retrograda completa per KBBK, è necessario generare tutte posizioni KBBK, che sono inferiori a 32 * 32 * 62 * 61 * 2. Il "32" è il numero di quadrati per i vescovi, il "* 2" tiene conto del giocatore che si sposta dopo; e non tutti i 32 * 32 * 62 * 61 posizionamenti teorici dei quattro pezzi sono legali (ovviamente, puoi escludere qualsiasi posizione in cui i re hanno una distanza posizionale < 2).

Per l'analisi, prendi queste posizioni come i vertici di un grafico diretto, ei bordi sono le transizioni legali da una posizione all'altra (in base alle mosse possibili).

Ora, segna le posizioni in cui il bianco si sposta e il re nero potrebbe essere catturato da un alfiere bianco. Tecnicamente, catturare il re non è legale secondo le classiche regole di scacchi, ma lascia supporre per un momento che fosse legale e chiamare queste posizioni "compagno in -1". Le posizioni "mate in 0" sono quindi i vertici nel grafico in cui il nero si muove successivamente, avendo solo "mate in -1", e dove il re nero è già controllato (quando ci sono solo "mate in -1" -successori e il re nero non è controllato, è una situazione remis).

Più in generale, una posizione in cui il nero si sposta dopo è un "compagno in x + 1", quando x è il massimo di tutti y tra i successori nel grafico con una posizione "matto in y", e non ci sono remis situazione. Quando il nero si muove dopo e c'è almeno una posizione remoti tra i successori, anche la posizione corrente è una situazione remis. Una posizione in cui le mosse bianche successive sono "mate in x + 1", quando x è il minimo di tutte le y tra i successori con una posizione di "matto in y" (indipendentemente dalle posizioni di remis). Quando il bianco si sposta dopo, una posizione è solo una posizione remis quando tutti i successori sono anche posizioni remis.

Quindi le posizioni di "compagno in 0" possono essere identificate semplicemente applicando la prima fase dell'analisi retrograda.

Gli "amici a 0" sarebbero le posizioni in cui il re è scacco matto. Konrad ha dato il via alla forza bruta attraverso posizioni a 444 k, ma possiamo fare molto meglio di così.

Il re nero deve essere sul bordo del tabellone, in modo che dia 28 posizioni. Uno dei vescovi deve dargli il controllo; ci sono solo 7 punti che è possibile. L'altro alfiere deve attaccare una delle caselle adiacenti al re, ci sono al massimo 15 posizioni per quello. Infine, il re avversario deve anche attaccare un quadrato adiacente, quindi ci sono fino a 9 punti possibili per esso.

Dopo aver considerato la simmetria orizzontale e verticale (dividi per 4) , otteniamo ~ 6.6k posizioni da cercare.

Diamo un'occhiata al problema in un modo più generale. Probabilmente vorrai avere tavoli per tutte le combinazioni di pezzi. Inoltre, probabilmente hai un motore di scacchi che può generare mosse possibili, eseguire mosse, rilevare check e situazioni di checkmate, valutare posizioni, ecc. Ho, e io uso il seguente algoritmo:

In 4 cicli annidati, genera tutte le posizioni possibili. Salta posizioni illegali. Questo nido viene eseguito molte volte. Nel primo passaggio, rileva tutte le posizioni scacco matto (= il nero non ha mosse ed è sotto controllo). Nei seguenti passaggi, esegui tutte le mosse possibili e vedi se portano a una posizione già coperta. Aggiungi passaggi fino a quando non vengono trovate più soluzioni. I valori della tabella devono essere coerenti con il sistema di valutazione del movimento del tuo motore di scacchi (probabilmente con una formula di conversione). Io uso un byte per ogni voce di tabella.

Le dimensioni della tabella per un end-game in 4 parti sono:

nessuna pedina: 2 * 10 * 64 * 64 * 64 (usando il mirroring orizzontale, verticale e diagonale)

con pedine: 2 * 32 * 64 * 64 * 64 (usando solo il mirroring orizzontale)

In un algoritmo generale, non puoi usare scorciatoie, ma devi usare il metodo della forza bruta. Genero i miei tavoli da 4 pezzi in app. 1 minuto ciascuno su un PC di fascia alta.