Il miglior approccio per scrivere un motore di scacchi? [chiuso]

Giocatore di scacchi valutato 2072 qui. Ho realizzato questo sito web in puro JavaScript per un fine settimana. Non è un motore di scacchi (l'ho progettato per creare divertenti posizioni di apertura come una sorta di motore perverso di Chess960), ma è un punto di partenza. Il codice sorgente è qui .

Ci sono molte complicazioni nel fare una tavola funzionale. Questi includono:

• In primo luogo, capire come rappresentare le mosse legali di base. Devi fare un po 'di matematica con le coordinate iniziali e finali. Ad esempio, con le mosse della torre, una delle coordinate deve essere la stessa prima e dopo. Con le mosse di cavaliere, la somma del valore assoluto delle coordinate cambia deve essere 3, e entrambe le coordinate devono cambiare. Con le mosse del vescovo, la somma delle coordinate rimane la stessa o entrambe aumentano di una stessa quantità. Le pedine sono più difficili perché non devi solo capire se possono muovere due caselle o una (controlla la riga e il colore invece di memorizzare il numero di mosse che hanno fatto), ma devono anche occuparsi dell'intera acquisizione in diagonale, spostare -cosa in avanti.
• Catturare è una sfida a causa di pedine e assegni. Non puoi semplicemente dire che se un pezzo si sposta sul quadrato di un altro pezzo, allora è una cattura. Dopotutto, le pedine non possono spostarsi sul quadrato di un altro pezzo da catturare - hanno il loro modo speciale di catturare.
• Devi trovare un modo efficace per vedere se i pezzi del nemico sono nel modo di muovere un pezzo per decidere se è legale o meno.
• Il controllo è impegnativo da affrontare. Dopo ogni mossa, devi controllare tutti i quadrati a cui i pezzi nemici possono andare e vedere se uno di loro riguarda il tuo re e, in tal caso, è una mossa illegale.
• Castling, en passant, promozione, stallo, estrazioni forzate, ripetizione - nessuno di questi è banale da gestire data la dimensione del problema.

Tutti i motori di scacchi funzionano osservando tutti (possibilmente un sottoinsieme euristicamente determinato) delle mosse legali in una posizione e valutando i numeri per rappresentare i loro valori relativi facendo quelle mosse e facendo ricorsivamente la stessa cosa per le posizioni risultanti. I tuoi problemi gemelli qui sono

• Come conservare questi dati in modo efficiente
• Come procedere con questa ricerca ricorsiva - dopo tutto, non puoi lasciarlo andare per sempre, quindi devi mettere un limite e poi capire come progettare il tuo algoritmo per fare la ricerca più ottimale e approfondita all'interno di quella limite. Ad esempio, vuoi assicurarti che fornisca almeno una valutazione per ogni possibile mossa iniziale, ma potresti anche volere che passi più tempo a valutare mosse più promettenti invece di dare uguale quantità di tempo a ogni mossa.

Tutto questo in cima alla progettazione dell'algoritmo, in primo luogo, su cui sono disponibili molte informazioni.

Per quanto riguarda la lingua da utilizzare (anche se penso che tu abbia già deciso su JavaScript), penso che dipenda più dal tuo obiettivo che da qualsiasi altra cosa. Volevo creare il mio online (e migliorare in JavaScript), quindi JavaScript è stata la mia scelta. Tuttavia, qualsiasi linguaggio di programmazione orientato agli oggetti funzionerà.

Una volta che ti senti a tuo agio con ciò che stai facendo, le seguenti risorse saranno probabilmente molto utili:

• Wiki per la programmazione degli scacchi
• Forum di programmazione degli scacchi
• StockFish su Github

Buona fortuna!

Il problema con il "programma di scacchi" come concetto è che ci sono molti pezzi che possono assorbire molto tempo, e non necessariamente ti interessano al momento. Puoi passare anni a lavorare sulla grafica, o una ricerca alfa-beta o una visualizzazione per sviluppare il motore di ricerca, oppure ... beh, ci sono molti pezzi.

Raccomando di trovare un programma di scacchi open source (ce ne devono essere molti) e di migliorare le parti di esso che ti interessano di più. Si può eventualmente sostituire l'intero programma, una funzione alla volta, o potresti imparare abbastanza ed essere motivato a buttarlo via e progettare il tuo programma da zero. In ogni caso, la chiave è iniziare "luce" e imparare le corde prima di provare ad architettare un intero programma.

Se hai familiarità con le regole degli scacchi, un buon punto di partenza sulle tecniche di base è link Una vasta raccolta di materiali e link che puoi trovare qui: link E terzo: impara dal codice degli altri. Dai un'occhiata alle fonti di Crafty . È il principale motore open source. Molto importante sarà pensare ai casi di test, per vedere se si apportano miglioramenti: inizia ad esempio con alcune semplici posizioni di fine gioco con 3 o 4 cifre.

Come già detto, non c'è nulla di particolarmente difficile nel costruire un motore di scacchi. Forse dovresti concentrarti su come desideri utilizzare e (potenzialmente) distribuire questa applicazione in quanto ciò probabilmente determinerà la tua scelta della lingua.

Se questo è solo un esercizio divertente, potresti volerlo codificare in Javascript e distribuirlo come una pagina web. Se non vuoi mai trasformarlo in un gioco di scacchi esperto, almeno altri saranno in grado di giocare con esso e il suo codice sorgente.

Se vuoi imparare una tecnologia particolare allo stesso tempo, diciamo WPF, allora questo potrebbe essere un buon modo per uccidere due piccioni con una fava. MVVM potrebbe essere eccessivo per questa app, ma lo impareresti almeno.

Se desideri prendere di mira i dispositivi Android, allora Java sarebbe una buona scelta. Allo stesso modo, Objective-C per dispositivi iOS.

Lungo e breve, la scelta della lingua non esiste nel vuoto.

Immagino che tu sappia già del concetto di Min-Max, alberi e potatura, euristica e altre nozioni di base e quello che scrivo qui sono solo alcuni dettagli che potrebbero essere stati sottovalutati.

Io con una compagnia un amico ha scritto il nostro motore di scacchi qualche volta fa. Condivido alcuni problemi e idee che abbiamo avuto e spero che li trovi utili.

Dato che entrambi eravamo programmatori java, il nostro linguaggio ha trasformato il nostro in java e abbiamo iniziato con un approccio orientato agli oggetti. I pezzi erano oggetti, il bordo era oggetto, i file e le file (righe e colonne nella letteratura degli scacchi) erano oggetti. E questo era sbagliato. Il sovraccarico è stato enorme e il programma ha faticato ad andare oltre 2 mosse (4 strati) nell'albero di ricerca.

Quindi con alcune ricerche abbiamo trovato una brillante idea (non la nostra però!): rappresentazione di pezzi e schede come interi lunghi (64 bit). Questo ha senso perché una scacchiera ha 64 quadrati. Il resto è stato operazioni poco saggi (molto vicino a cpu = estremamente veloce). Ad esempio, prendi in considerazione un intero binario a 64 bit in cui quelli presentano i quadrati sul tabellone che il tuo pezzo può attaccare. Ora se si esegue un "AND" logico tra due numeri come questo, un risultato diverso da zero indica che si ha un quadrato con gli attaccanti. Ci sono diversi modi per presentare la scacchiera e pezzi, quindi:

1 - Decide about your Board Presentation

Quindi hai bisogno di aprire il database. L'apertura degli scacchi è in qualche modo risolta e si consiglia vivamente di avere e aprire il libro. In questo caso, hai molto tempo in più nei giochi blitz.

2 - Find yourself an opening book.

Li abbiamo fatti, ma eravamo ancora lontani dall'essere bravi:

3 - A good chess engine should be able to see 6 moves (12 ply) ahead.

Quindi quello che abbiamo fatto allora era utilizzare il tempo morto (se si tratta di un motore umano vs computer).

4 - Use the time when opponent is thinking to create some levels of your tree.

Eppure eravamo molto lontani da 12 strati. Con più studio, scopriamo alcuni trucchi! Ad esempio, è stato suggerito di saltare uno strato dell'albero e iniziare dal prossimo strato (come se non ci fosse nessun avversario). L'idea è che se una mossa è estremamente idiota, allora perché perdere tempo e vedere quali sono le risposte degli avversari a quella mossa. Tuttavia, un buon motore dovrebbe essere in grado di distinguere tra mossa idiota e sacrificio della regina geniale.

5 - Learn the programming tricks for this specific problem (chess).

Io e il mio amico, in questo stato, eravamo ancora cattivi: / Quello che potevamo fare - e in parte lo abbiamo fatto - era di salvare le posizioni calcolate. Se calcoli una posizione, salvala per il futuro! Lo stesso vale per i loop nell'albero di ricerca. Il punto era salvare / recuperare efficientemente:

6 - Save the data you generate...Efficiently!

e infine:

7 - Code with maximum optimization.

Questo problema è estremamente costoso sia in termini di tempo di CPU che di memoria. È molto importante scrivere il tuo codice in modo molto efficiente. Ricorda che stiamo parlando del fattore di derivazione di 35. Significa un "se" inutile da qualche parte nella tua euristica, può essere trasformato in 3.3792205e+18 inutile "se" è da qualche parte nel profondo del tuo albero di ricerca.

La programmazione di scacchi è una sfida molto molto interessante ed è il momento in cui puoi trasformare le tue capacità di programmazione in un test serio. Ci sono alcuni punti in più che posso suggerire, ma sono sicuro che li scoprirai da solo. Ci sono molti altri punti che non conosco ma puoi trovarli su internet!

Buona fortuna e buon divertimento!

P.S. Non conosco molto bene il javascript, ma qualcosa mi sta dicendo la difficoltà del problema, forse, considerando tutto ciò che il C ++ può offrire, sarebbe meglio abbandonare javascript e farlo in C ++.

Come da modifica, sei in grado di definire le mosse "legali".

Ci sono due modi per descrivere le mosse negli scacchi. Notazione descrittiva e Notazione algebrica . Quello che probabilmente vuoi è una funzione che prende il pezzo, la posizione iniziale e la posizione finale come parametri. per esempio. Knight da QN1 a QB2 non è valido, ma Knight da QN1 a Q2 è valido. Pensandoci, la notazione algebrica potrebbe essere più semplice grazie alla possibilità di calcolare facilmente il posizionamento "relativo".

Per assicurarti di scrivere la quantità minima di codice richiesta, inizierei con i test di scrittura per quella funzione prima . Se stai usando la notazione algebrica, probabilmente non hai bisogno di un test per pezzo / inizio / fine. Fai lavorare ogni test e rifatta la duplicazione prima di passare alla successiva "mossa". Il tuo codice diventerà più pulito.

Una volta che hai sufficientemente coperto le mosse legali e illegali per ogni pezzo, inizierei ad aggiungere controlli per altre variabili (come spostare un Re in condizioni di "controllo" e "accoppiamento").

Raccomando qunit per i test unitari e gelsomino per test comportamentali in JavaScript.

In realtà ho scritto un motore di scacchi. Preparati per un piacere e un incubo. Quando i miei amici e io l'abbiamo fatto, era in un concorso di programmazione a tempo e il linguaggio con cui abbiamo deciso di andare era Java. Sento che Java o C sono la tua scelta migliore, ma vedo che hai deciso di andare con Javascript. Non posso davvero bussare perché non mi è familiare.

Il problema principale qui è che ci sono così tanti scenari di movimento / vittoria con ogni pezzo di cui hai bisogno, quindi ti consiglio di scrivere tutte queste possibili situazioni per ogni pezzo prima di iniziare effettivamente la codifica. Saltare dentro senza pianificazione trasformerà questo divertente progetto in un compito ripetitivo. Ma questa è davvero la cosa principale. Prima pianifica solo fuori dal codice e assicurati di ottenere ogni scenario per un pezzo alla volta.

Good Luck

Per la parte del gioco che prende il computer-giocatore, non posso raccomandare abbastanza il libro "Artificial Intelligence: A Modern Approach" (sito web del libro link ). A seconda del tuo background in matematica (la teoria del grafico aiuta) potrebbe essere un po 'di alto livello, ma è scritto semplicemente come questo materiale accademico può essere e contiene una panoramica molto aggiornata (e un po' di profondità) di tecniche per fai in modo che i programmi decidano le cose.

Ti indicherà cose come dichiarare un obiettivo (es. scacco matto o null), valutando quanto vicino un particolare stato (il layout della plancia) è a quell'obiettivo, come generare i diversi stati seguenti possibili a partire dall'attuale uno, e come attraversare quello che è un immenso spazio problematico.

Una cosa che potrebbe aiutare a progettare un algoritmo di intelligenza artificiale è capire come decidere quale mossa giocare, come se avessi tutto il tempo del mondo, partendo da una situazione molto vicina a una partita vinta. Lo ottimizzi in modo che trovi una soluzione in un ragionevole lasso di tempo (ore), quindi trovi i modi per scegliere un percorso vincente anche se non hai ancora esplorato tutti i risultati, in modo da poter effettivamente interrompere il "pensiero" per un giro vale il tempo.

Solo a quel punto dovrei cercare di ottimizzare la rappresentazione di rendere i calcoli individuali più veloci, come usare interi lunghi come suggerito. Non importa quanto sia veloce in modo da poter fare un confronto unico, se il modo in cui attraversi il problema lo spazio non ha una buona euristica, ci vorranno secoli per farlo.

Puoi andare davvero come vuoi, ma questi sono i miei pensieri sull'argomento:

Userò Java in quanto ti consente di essere di altissimo livello e di avere librerie di interfacce utente (AWT, Swing) a tua disposizione. È possibile utilizzare un approccio orientato agli oggetti per modellare la scacchiera e pezzi. Altri oggetti potrebbero sostituire la cronologia delle mosse e il punteggio. Anche i giocatori potrebbero essere oggetti, quindi in futuro potresti estendere la tua classe Player per fornire un riproduttore artificiale intelligente per computer.

Potresti dare un'occhiata a model-view-controller (MVC in questo caso è un ottimo approccio per legare gli oggetti del modello (modello di dominio) all'interfaccia utente (vista) e consentire all'utente di manipolare il modello (tramite il controller).

Potresti anche voler applicare lo sviluppo basato sui test , che non solo assicura che tutti i metodi si comportino come ti aspetti, ma ti costringe anche a scrivere codice testabile e modulare.

Le regole degli scacchi in sé sono abbastanza semplici. Devi solo essere in grado di creare una matrice (array bidimensionale) per la tavola e trovare un modo per codificare i concetti dei pezzi, le regole di movimento per ogni pezzo, la convalida che una mossa è legale e le condizioni che segnalano la fine del gioco. Niente di particolarmente difficile in tutto ciò. Dovresti usare qualsiasi lingua tu abbia più familiarità.

Ora, se vuoi creare un'IA che gioca a scacchi, assumerà il ruolo di uno dei giocatori, è lì che le cose si complicano. Ma ancora una volta, la scelta della lingua non è il problema più grande qui; capire i principi di intelligenza artificiale coinvolti è. Questo sarà un fattore molto più importante.

(detto questo, questo tipo di processo decisionale può essere estremamente intenso dal punto di vista computazionale e probabilmente si vorrà usare qualcosa che si compila in codice nativo piuttosto che in un linguaggio di scripting. E il C ++ è una scelta pessima, non perché non è adatto a questo problema, ma semplicemente perché è un linguaggio molto brutto in generale, e provare a implementare cose complesse in esso è un buon modo per codificare tutti i tipi di mal di testa per te stesso.)