Ottimizzazioni di scacchi

Question

ok, quindi ho lavorato al mio programma di scacchi per un po 'e sto iniziando a colpire un muro. ho fatto tutte le ottimizzazioni standard (negascout, approfondimento iterativo, mosse killer, euristica storica, ricerca quiescente, valutazione della posizione dei pedoni, alcune estensioni di ricerca) e sono tutte fuori idee!

Sto cercando di renderlo multi-threaded presto, e questo dovrebbe darmi una buona spinta in termini di prestazioni, ma a parte questo ci sono altri trucchi eleganti che voi ragazzi avete incontrato? ho preso in considerazione il passaggio a MDF (f), ma ho sentito che è una seccatura e non ne vale la pena.

Quello che mi interessa di più è un qualche tipo di algoritmo di apprendimento, ma non so se qualcuno lo abbia mai fatto in modo efficace con un programma di scacchi.

Inoltre, il passaggio a una bit board è significativo? attualmente sto usando 0x88.

Answer 1

Supponendo che "storia euristica" implichi una sorta di database delle mosse precedenti, un algoritmo di apprendimento non ti darà molto di più a meno che non giochi un sacco di giochi contro lo stesso giocatore. Probabilmente puoi ottenere di più classificando un giocatore e modificando la selezione delle mosse dal tuo database storico.

Answer 2

È passato molto tempo da quando ho programmato alcun programma di scacchi, ma al momento le schede bit hanno apportato un miglioramento reale. A parte questo, non posso darti molti consigli. Valutate solo la posizione delle pedine? Alcuni (leggeri) bonus per la posizione o la mobilità di alcuni pezzi chiave potrebbero essere in ordine.

io non sono certo il tipo di cosa che si vorrebbe per imparare però ...

Answer 3

so che un miglioramento che è stato parlato ai corsi di AI in università dove avere un enorme database di mosse finali . Quindi avere un database precalcolato per i giochi con solo un piccolo numero di cifre rimanenti. In questo modo, se si preme un posizionamento vicino alla fine della ricerca, si interrompe la ricerca e si ottiene un valore precalcolato che migliora i risultati della ricerca come un ulteriore approfondimento che è possibile eseguire per mosse importanti/critiche senza molto tempo di calcolo. Penso che arrivi anche con un cambio di euristica in uno stato di gioco tardo, ma non sono un giocatore di scacchi quindi non conosco le dinamiche della finitura del gioco.

Answer 4

Per quanto riguarda i suggerimenti, so che è possibile ottenere grandi guadagni nell'ottimizzazione delle routine di generazione del movimento prima di qualsiasi funzione di valutazione. Rendere tale funzione il più stretta possibile può darti il ​​10% o più di miglioramento dei nodi/secondo.

Se ti stai spostando verso bitboard, fai qualche ricerca sugli archivi di rec.games.chess.com per alcuni dei vecchi post di Dr. Robert Hyatts su Crafty (sono sicuro che non pubblichi più). Oppure prendi l'ultima copia da his FTP e inizia a scavare. Sono abbastanza sicuro che sarebbe comunque un cambiamento significativo per te.

Answer 5

• tabella di trasposizione
• apertura a libro
• End Basi gioco da tavolo
• migliorata Statico Scheda di valutazione per Leaf Nodi
• bitboard per Speed ​​Raw

Answer 6

attenzione, ottenendo di ricerca gioco giusto in un ambiente filettato può essere un dolore reale (I've tried it). Può essere fatto, ma da qualche ricerca bibliografica ho fatto un po 'di tempo fa, è estremamente difficile ottenere alcun aumento di velocità.

Answer 7

Nell'ultimo anno di sviluppo del mio motore di scacchi (www.chessbin.com), la maggior parte del tempo è stato dedicato all'ottimizzazione del mio codice per consentire una ricerca di spostamento migliore e più veloce. In quel periodo ho imparato alcuni trucchi che vorrei condividere con voi.

di misurazione delle prestazioni

In sostanza è possibile migliorare le prestazioni in due modi:

• Valutare i nodi più veloce
• ricerca minor numero di nodi a venire con la stessa risposta

Il tuo primo problema nell'ottimizzazione del codice sarà la misurazione. Come sai che hai davvero fatto la differenza? Per aiutarti con questo problema, dovrai assicurarti di poter registrare alcune statistiche durante la tua ricerca. Quelle che catturo nel mio motore di scacchi sono:

• Il tempo impiegato per la ricerca è completo.
• Numero di nodi cercato

Questo vi permetterà di punto di riferimento e verificare le modifiche. Il modo migliore per affrontare i test è creare diversi salvataggi dalla posizione di apertura, dal gioco centrale e dal gioco finale. Registrare l'ora e il numero di nodi ricercati in bianco e nero. Dopo aver apportato qualche modifica, di solito eseguo dei test rispetto ai suddetti giochi di salvataggio per vedere se ho apportato miglioramenti alle due matrici precedenti: numero di nodi ricercati o velocità.

Per complicare ulteriormente le cose, dopo aver apportato un cambio di codice è possibile eseguire il motore 3 volte e ottenere ogni volta 3 risultati diversi. Diciamo che il tuo motore di scacchi ha trovato la migliore mossa in 9, 10 e 11 secondi. Quello è uno spread di circa il 20%. Quindi hai migliorato il tuo motore del 10% -20% o è stato solo un carico variabile sul tuo pc. Come lo sai? Per combattere questo ho aggiunto metodi che permetteranno al mio motore di giocare contro se stesso, farà mosse sia per il bianco che per il nero. In questo modo puoi testare non solo la varianza del tempo su una mossa, ma anche una serie di 50 mosse nel corso del gioco. Se l'ultima volta che il gioco ha impiegato 10 minuti e ora ne occorrono 9, probabilmente hai migliorato il tuo motore del 10%. Eseguire nuovamente il test dovrebbe confermare questo.

Prestazioni Trovare Utili

Ora che sappiamo come misurare miglioramenti delle prestazioni consente di discutere come identificare potenziali miglioramenti delle prestazioni.

Se si è in un ambiente .NET, il profiler .NET sarà tuo amico. Se si dispone di una versione di Visual Studio for Developers, viene fornita gratuitamente, tuttavia esistono altri strumenti di terze parti che è possibile utilizzare. Questo strumento mi ha permesso di risparmiare ore di lavoro in quanto ti dirà dove il tuo motore trascorre la maggior parte del suo tempo e ti consente di concentrarti sui punti problematici. Se non hai uno strumento profiler potresti dover in qualche modo registrare i timestamp mentre il tuo motore passa attraverso diversi passaggi. Non lo suggerisco. In questo caso un buon profiler vale il suo peso in oro. Red Gate ANTS Profiler è costoso ma il migliore che abbia mai provato. Se non puoi permetterti uno, almeno lo usi per la loro prova di 14 giorni.

vostro profiler sarà burbero identificare le cose per voi, ma qui ci sono alcune piccole lezioni che ho imparato a lavorare con C#:

• Rendere tutto privato
• Tutto ciò che non è possibile effettuare privata, rendono sigillato
• Possibile eseguire molti metodi statici come .
• Non rendere i tuoi metodi chiacchieroni, un metodo lungo è meglio di 4 più piccoli .
• La scacchiera memorizzata come array [8] [8] è più lenta di un array di [64]
• Sostituisci int con byte laddove possibile.
• È possibile tornare dai propri metodi già a partire da .
• Le pile sono migliori degli elenchi
• Gli array sono migliori delle pile e degli elenchi .
• Se è possibile definire la dimensione dell'elenco prima di popolarlo.
• Casting, boxing, un-boxing è il male.

ulteriori guadagni di prestazione:

trovo generazione mossa e l'ordinazione è estremamente importante. Comunque qui è il problema come lo vedo io. Se valuti il ​​punteggio di ogni mossa prima di ordinare ed eseguire Alpha Beta, sarai in grado di ottimizzare il tuo ordine di movimento in modo tale da ottenere riduzioni estremamente veloci di Alpha Beta. Questo perché sarai in grado di provare per prima cosa la migliore mossa. Tuttavia, il tempo impiegato per valutare ogni mossa sarà sprecato. Ad esempio potresti aver valutato il punteggio su 20 mosse, ordinare le tue mosse, provare i primi 2 e ricevere un cut-off sul numero di mossa 2. In teoria il tempo che hai speso per le altre 18 mosse è stato sprecato.

D'altra parte se si effettua una valutazione più leggera e molto più veloce dire solo acquisizioni, il tuo ordinamento non sarà così buono e dovrai cercare più nodi (fino al 60% in più). D'altra parte non dovresti fare una valutazione pesante su ogni mossa possibile. Nel complesso, questo approccio è in genere più veloce.

Trovare questo perfetto equilibrio tra avere abbastanza informazioni per un buon tipo e non fare un lavoro extra su mosse che non userete, vi permetterà di trovare enormi guadagni nell'algoritmo di ricerca. Inoltre, se si sceglie l'approccio di ordinamento più povero, si vorrà prima eseguire una ricerca meno profonda, dire a ply 3, ordinare la propria mossa prima di andare nella ricerca più profonda (questo è spesso chiamato approfondimento iterativo). Ciò migliorerà in modo significativo il tuo ordinamento e ti consentirà di cercare molte meno mosse.

Answer 8

Rispondere a una vecchia domanda.

Supponendo che abbiate già una tabella di trasposizione funzionante.

Riduzione del movimento in ritardo. Ciò ha dato al mio programma circa 100 punti elo ed è molto semplice da implementare.

Nella mia esperienza, a meno che l'implementazione non sia molto inefficiente, la rappresentazione della scheda effettiva (0x88, bitboard, ecc.) Non è così importante.

Sebbene sia possibile criptare il motore degli scacchi con prestazioni scadenti, un generatore di movimento rapido non è in grado di rendere un programma valido.

I trucchi di ricerca utilizzati e la funzione di valutazione sono i fattori che determinano la forza complessiva.

E le parti più importanti, di gran lunga, della valutazione sono Materiale, Pedoni passate, Sicurezza re e Struttura dei pedoni.

Le parti più importanti della ricerca sono: Null Move Poting, Check Extension e Late Move reduction.

Il tuo programma può percorrere una lunga strada, con queste semplici tecniche!

Answer 9

È una domanda piuttosto vecchia, stavo solo cercando domande sugli scacchi e ho trovato questo senza risposta. Beh, potrebbe non essere di alcun aiuto per te ora, ma potrebbe rivelarsi utile ad altri utenti.

Non ho visto nessuna potatura, tabelle di trasposizione ... le stai usando? Ti darebbero una grande spinta ...

Una cosa che mi ha dato una grande spinta è stata la riduzione al minimo della ramificazione condizionale ... Un sacco di cose può essere precalcolata. Cerca tali opportunità.

I PC più moderni hanno più core, quindi sarebbe una buona idea renderlo multithreading. Non è necessario necessariamente utilizzare MDF (f) per quello.

Non suggerisco di spostare il codice su bitboard. È semplicemente troppo lavoro. Anche se i bitboard potrebbero dare una spinta alle macchine a 64 bit.

Infine, e soprattutto la letteratura di scacchi domina le ottimizzazioni che possiamo usare. l'ottimizzazione è troppo lavoro. Guarda i motori di scacchi open source, in particolare furbo e frutta/toga. La frutta era inizialmente open source.

Answer 10

Profilo e benchmark. Le ottimizzazioni teoriche sono grandiose, ma a meno che tu non stia misurando l'impatto sulle prestazioni di ogni cambiamento che fai, non saprai se il tuo lavoro sta migliorando o peggiorando la velocità del codice finale.

Cerca di limitare la penalità a te stesso per provare diversi algoritmi. Semplifica il test delle varie implementazioni di algoritmi l'uno contro l'altro. Ad esempio, semplificare la creazione di una versione PVS del codice e di una versione NegaScout.

Trova i punti caldi. Refactor. Riscrivi in ​​assembly se necessario. Ripetere.

Answer 11

Buon ordine di movimento!

Una vecchia domanda, ma le stesse tecniche si applicano ora come per 5 anni fa. Non stiamo tutti scrivendo i nostri motori di scacchi, ho il mio "Norwegian Gambit" che spero finirà per competere con altri motori Java sul CCRL. Io, come molti altri, uso lo stoccafisso per le idee dato che è così ben scritto e aperto. Il loro framework di test Fishtest e la sua community danno anche un sacco di buoni consigli. Vale la pena confrontare i punteggi di valutazione con quello che lo stoccafisso ottiene dal momento che la valutazione è probabilmente la più grande incognita nella programmazione degli scacchi e Stoccafisso è andato via da molte eval tradizionali che sono diventate leggende metropolitane (come il doppio bonus bishop). La differenza più grande però è stata quando ho implementato le stesse tecniche che hai menzionato, Negascout, TT, LMR, ho iniziato a usare lo stoccafisso per il confronto e ho notato come per la stessa profondità lo stoccafisso avesse mosse molto meno cercate di me (a causa dell'ordine di spostamento).

essenziali Spostare ordinazione

L'unica cosa che si dimentica facilmente è buona mossa-ordinazione. Affinché il cutoff Alpha Beta sia efficiente, è essenziale innanzitutto ottenere le mosse migliori. D'altra parte può anche richiedere molto tempo, quindi è essenziale farlo solo se necessario.

1. tabella di trasposizione
2. Ordina promozioni e buoni cattura per il loro guadagno
3. Killer muove
4. Moves che si traducono in controllo sull'avversario
5. euristiche di storia
6. si muove silenzioso - Ordina per valore PSQT

L'ordinamento deve essere eseguito secondo necessità, in genere i t è sufficiente per ordinare le acquisizioni e, successivamente, è possibile eseguire il più costoso ordinamento di controlli e PSQT solo se necessario.

Chi Java/C# vs C/C++/Assemblea

tecniche di programmazione sono gli stessi per Java come nella risposta eccellente da Adam Berent che ha usato C#. Oltre alla sua lista, vorrei menzionare l'eliminazione degli array Object, piuttosto usare molti array di primitivi, ma contrariamente al suo suggerimento di usare i byte, trovo che con java a 64 bit c'è poco da salvare usando byte e int invece di 64 bit. Ho anche intrapreso la strada della riscrittura in C/C++/Assembly e non ho alcun guadagno in termini di prestazioni. Ho usato codice assembly per istruzioni bitscan come LZCNT e POPCNT, ma in seguito ho scoperto che Java 8 utilizza anche quelli invece dei metodi sull'oggetto Long. Con mia sorpresa, Java è più veloce, la macchina virtuale Java 8 sembra fare un ottimizzazione del lavoro migliore di quanto possa fare un compilatore C.

Answer 12

risposta tardi, ma questo può aiutare qualcuno:

Tenuto conto di tutte le ottimizzazioni che hai citato, 1450 ELO è molto bassa. La mia ipotesi è che qualcosa sia molto sbagliato con il tuo codice. hai fatto:

1. ha scritto un perft routine e stato eseguito attraverso una serie di posizioni? Tutti i test dovrebbero passare, quindi sai che il tuo generatore di mosse è privo di bug. Se non hai questo, non ha senso parlare di ELO.

2. Ha scritto una routine mirrorBoard e ha eseguito il codice di valutazione attraverso una serie di posizioni? Il risultato dovrebbe essere lo stesso per le posizioni normali e speculari, altrimenti hai un bug nel tuo account.

3. Hai una tabella hash (nota anche come tabella di trasposizione)? In caso contrario, questo è un must. Aiuterà a cercare e ordinare le mosse, dando una brutale differenza di velocità.

4. Come si implementa l'ordine di spostamento? Questo link torna al punto 3.

5. Hai implementato il protocollo UCI? La tua funzione move parsing funziona correttamente?Ho avuto un problema come questo nel mio motore:

   /* Parses a uci move string and return a Board object */ 
       Board parseUCIMoves(String moves)// e2e4 c7c5 g1f3 ...{ 
        //... 
        if (someMove.equals("e1g1") || someMove.equals("e1c1")) 
         //apply proper castle 
       //... 
   } 
   

A volte il motore si è schiantato durante la riproduzione di un fiammifero, e ho pensato che fosse colpa GUI, dal momento che tutti i test perft erano ok. Mi ci è voluta una settimana per trovare l'errore per fortuna. Quindi, prova .

Per (1) è possibile cercare ogni posizione in profondità 6. Uso un file con ~ 1000 posizioni. Vedi qui https://chessprogramming.wikispaces.com/Perft

Per (2) è sufficiente un file con milioni di posizioni (solo la stringa FEN).

Dato tutto quanto sopra e una funzione di valutazione molto semplice (materiale, tabelle quadrate, pedine passate, sicurezza re) dovrebbe giocare a + -2000 ELO.