Scacchi: alto fattore di ramificazione

Question

Sto provando a sviluppare un semplice motore di scacchi, ma sono alle prese con le sue prestazioni. Ho implementato Negamax con potatura alfa-beta e approfondimento iterativo (senza ulteriori euristiche), ma non sono in grado di ottenere tempi di ricerca ragionevoli oltre il 3-4 ° strato. Ecco un estratto dal registro del mio programma dall'inizio del gioco:

2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28 
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118 
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 
2013-05-11 18:22:06,897 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414 
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 
2013-05-11 18:22:08,005 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880 
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 
2013-05-11 18:22:10,485 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538 
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6 

Essa mostra che ramificazione fattore è di circa 10. Ho letto che con una corretta mossa ordinamento dovrei ottenere qualcosa intorno a 6, quindi ho il sospetto che il mio ordine è sbagliato. Attualmente funziona in questo modo:

1. Il nodo dell'albero di gioco ha un elenco collegato dei suoi figli; inizialmente, cattura e le promozioni sono posti prima di mosse tranquille
2. Durante la ricerca, bambino che aumenta alfa o cause di taglio è posto all'inizio della lista
3. Sulla prossima iterazione di approfondimento fotovoltaico dovrebbe essere cercato prima

È un modo corretto per ordinare i movimenti e il fattore di ramificazione che ottengo è prevedibile? Attualmente sto usando una semplice funzione di valutazione statica che tiene conto solo della differenza materiale della posizione - può essere una ragione per una bassa frequenza di taglio (se si considera anche la mobilità delle cifre, ottengo risultati simili)? Tecniche come la riduzione del movimento nulla o l'euristica killer potrebbero aiutare in modo significativo (non del 10-15%, ma di un ordine di grandezza)? Non mi aspetto che il mio motore sia forte, ma vorrei che il fattore di ramificazione sia circa 6.

Answer 1

Ho sviluppato anche un motore di scacchi in C# e ha un fattore di ramificazione intorno a 2,5. È sicuramente possibile migliorare il tuo motore di molti ordini di grandezza. Oggigiorno la strategia generale consiste nell'utilizzare potature molto aggressive basate su un buon ordine di movimento. Sacrifichi un po 'di correttezza per essere in grado di vedere alcune profonde linee tattiche.

Ecco una panoramica delle tecniche che ho trovato più efficaci.Si noti che alcuni componenti sono complementi e altri sono sostituti, quindi i risultati che fornisco sono linee guida generali. I grandi guadagni alla fine della lista non sono possibili se non hai una base solida.

1. Proprio negamax con alpha-beta pruning: profondità di 4 entro 3 secondi.

2. Aggiungi iterative deepening e null move heuristic: profondità 5. L'approfondimento iterativo non aiuta molto a questo punto, ma è facile da implementare. Lo spostamento nullo consiste nel saltare il tuo turno e vedere se è ancora possibile ottenere un taglio beta con una ricerca poco profonda. Se è possibile, è probabile che sia sicuro per potare l'albero poiché è quasi sempre vantaggioso spostare lo spostamento .

3. Killer heuristic: profondità 6. Questo comporta la memorizzazione di mosse che causa tagli beta e provarli prima se sono legali prossima volta siete alla stessa profondità. Sembra che tu stia facendo qualcosa di simile già.

4. MVV/LVA ordering: profondità 8. In sostanza, si vuole mettere cattura che hanno un sacco di guadagno netto rilevante potenziale nella parte superiore del movimento lista. Quindi se una pedina cattura una regina, dovresti prima cercarla.

5. Bitboard representation: profondità 10. Questo non migliora il fattore di diramazione , ma questo è ciò che ho fatto quando ho raggiunto questo punto. Eliminare gli array , utilizzare invece UInt64 s e utilizzare make/unmake anziché copy-make. Non è necessario utilizzare i bitboard magici se lo trovi difficile; ci sono metodi più semplici che sono ancora molto veloci. I bitboard migliorano notevolmente le prestazioni e semplificano la scrittura dei componenti di valutazione. Sono passato da perft (6) impiegando minuti per impiegare 3 secondi. (A proposito, scrivendo una funzione perft è un ottimo modo per garantire mossa generazione correttezza)

6. Transposition table: profondità 13. Questo offre grandi guadagni, ma è anche molto difficile da ottenere. Sii assolutamente certo che l'hashing della tua posizione sia corretto prima di implementare la tabella. La maggior parte del vantaggio deriva dallo l'incredibile mossa che ordina il tavolo. Memorizza sempre il miglior mossa nel tavolo e ogni volta che ottieni una posizione corrispondente, prova prima il .

7. Late move reductions: profondità 16. Questo gonfia notevolmente la profondità di ricerca ma il guadagno di forza è più artificiale rispetto ad altre tecniche. Fondamentalmente il tuo ordine di spostamento è così buono ora che devi solo cercare completamente i primi movimenti di in un nodo, e puoi semplicemente controllare gli altri con ricerche superficiali.

8. Futility pruning: profondità 17. I nodi foglia sono tagliati saltando mosse che hanno una bassa probabilità di migliorare il valore del nodo quando guardando potenziale guadagno materiale. Se il guadagno potenziale netto del movimento + valutazione statica della posizione è inferiore al valore corrente della posizione, saltare la valutazione per lo spostamento.

Ci sono vari altri componenti che aiutano anche, ma la maggior parte sono minori e altri sono proprietari.: D Tuttavia, non si tratta solo di profondità di ricerca elevate e di fattori di ramificazione bassi. Cose come quiescence search peggiorano la profondità di ricerca ma sono praticamente una necessità per qualsiasi motore. Senza di esso il tuo motore subirà grandi errori tattici. Si consiglia inoltre di prendere in considerazione check extensions e single reply extensions. Suggerirei anche di introdurre almeno piece-square tables nella funzione di valutazione. È un modo molto semplice per migliorare notevolmente la conoscenza posizionale del tuo programma; probabilmente vedrai il tuo motore riprodurre aperture più comuni. La programmazione di scacchi è un hobby divertente e spero che il volume delle informazioni non scoraggi!

Answer 2

L'euristica multipla è possibile utilizzare per ridurre il fattore di ramificazione.

In primo luogo, è necessario utilizzare uno transposition table (TT) per memorizzare i risultati delle posizioni, la profondità e il miglior spostamento. Prima di cercare una mossa, per prima cosa controlla se è già stata cercata a una profondità> = alla profondità che stai pianificando di cercare. Se lo è, puoi semplicemente utilizzare il risultato dalla tabella. Se non lo è, puoi ancora utilizzare la mossa nella tabella come prima mossa per la ricerca.

Se non c'è una corrispondenza nel TT per una posizione (all'interno della ricerca), è possibile utilizzare Iterative Deepening (ID). Anziché eseguire una ricerca a una profondità di N, eseguire prima una ricerca fino a una profondità di N-2. Questo sarà veramente veloce e ti darà una mossa per cercare prima a profondità N.

C'è anche Null Move Pruning. In combinazione con Alpha-Beta (Negamax è una variazione su Alpha-Beta), si riduce notevolmente il fattore di ramificazione. L'idea è prima di cercare una posizione, si prova una mossa nulla (non in riproduzione) e si fa una ricerca ridotta (N-2 o N-3). La ricerca di riduzione sarà molto veloce. Se il risultato della ricerca di spostamento nullo è ancora superiore alla beta, significa che la posizione è così grave che non è necessario cercarla più (non sempre vera, ma è la maggior parte delle volte).

Naturalmente ci sono molti altri euristici che è possibile utilizzare per migliorare il tuo move ordering che migliorerà il tuo fattore di ramificazione.