Come fa un motore di scacchi a decidere quale mossa fare?

Question

Come fa un motore di scacchi a decidere quale mossa fare?

#1 da (4 voti)
#2 da (2 voti)
#3 da (1 voti)

2

Sto scrivendo un semplice motore di scacchi in LISP. In realtà so come il motore decide la mossa, valuta e legge alcuni libri di apertura. Ma non è quello che intendo. Questo è il mio design.

57 58 59 60 61 62 63 64
49 50 51 52 53 54 55 56
41 42 43 44 45 46 47 48
33 34 35 36 37 38 39 40
25 26 27 28 29 30 31 32
17 18 19 20 21 22 23 24
09 10 11 12 13 14 15 16
01 02 03 04 05 06 07 08

Ho esaminato soluzioni più complicate ma sono uscito con quello che ritengo sia il più semplice. Dì che l'alfiere è sul quadrato 23, potrebbe muovere 4 possibili mosse, (a 16 o 14 o 32 o 30), quindi muove -7 o +7 o +9 o -9.

Creo un array

(make-array '(8 8) :initial-contents
'((R B N Q K B N R)
 (P P P P P P P P)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
          (P P P P P P P P))
          (R B N Q K B N R)))

E sposta i pezzi da un indice all'altro. La mia domanda è, non posso semplicemente dire al vescovo di spostare +7 o qualsiasi altra cosa, se è una diagonale aperta. Devo dirlo per spostare +9 * 1 o +9 * 2 ecc. E il tuo vescovo deve decidere a quale andare. Non riesco a scrivere una condizione e un loop per ogni quadrato possibile

lisp common-lisp design-patterns chess

posta Lynob 17.11.2013 - 20:01

fonte

3 risposte

2

Un alfiere può andare al campo numerato +7 o +9, e probabilmente da lì ai campi numerati +14 e +18. Quest'ultima parte puoi controllare con un loop: con quale frequenza puoi fare un +7, quanto spesso un +9?

Ci sono due limiti: altri pezzi (che possono essere catturati, ma devono essere rimossi) e i bordi della tavola. Per l'alfiere, ciò significa che non puoi fare un +7 dalla posizione N * 8 + 1 della tavola, in quanto ciò si avvolgerebbe, non puoi fare un +9 dalla posizione N * 8 della tavola, e non puoi fare alcun + dalla posizione della scheda > = 57. E ovviamente ci sono anche -7 e -9 con vincoli simili.

Altri pezzi hanno altre regole, ma sono praticamente le stesse: non possono attraversare altri pezzi, non possono attraversare i bordi. Alcuni possono eseguire solo un passo alla volta. Per esempio. i cavalieri hanno una mossa di +15, ma non +30, e la mossa di +15 può provenire solo dai campi con il rettangolo 02-08-48-42.

risposta data 18.11.2013 - 12:02

fonte

1

Come sottolineato da @MichaelT, dovresti leggere la minimax ricerca e alpha-beta potatura .

Il problema qui è algoritmico e non ha quasi nulla a che fare con il design. Ad ogni turno hai un certo numero di mosse possibili. Per ciascuna delle tue possibili mosse, il tuo avversario ha un numero di mosse suo proprio. Questo genera l'albero di gioco che devi cercare. In ogni nodo è necessario essere in grado di valutare la posizione della scheda per determinare quale risultato è più vantaggioso per te. L'algoritmo per cercare tali alberi è chiamato minimax search . Il modo per evitare di dover cercare l'intero albero si chiama alpha-beta poting .

risposta data 18.11.2013 - 03:05

fonte

Leggi altre domande sui tag lisp common-lisp design-patterns chess

Differenza tra Linter, Sanitizer e Static Analysis Tools Come considerare concettualmente e implementare le regole dell'interfaccia utente per numerosi controlli e input di dati?

score 4 · Accepted Answer

Immagina di avere una funzione che valuta il tabellone di gioco e restituisce un punteggio, in cui i punteggi positivi più alti significano che stai andando bene e punteggi negativi elevati significano che stai facendo male.

Ora immagina che per ogni posizione possibile in cui un pezzo può muoversi, per ogni pezzo sul tabellone, calcoli quale sarà il punteggio e scegli la mossa che ha come risultato il miglior punteggio. Questo non è troppo difficile da fare e si traduce in un avversario di IA che è grosso modo equivalente a un giocatore di scacchi umano novizio.

Ora; invece di trovare il miglior punteggio dopo aver effettuato una mossa, puoi trovare il punteggio dopo che hai fatto una mossa e anche l'avversario ha fatto una mossa.

Ancora più importante puoi farlo a "n livelli" - ad es. trova il punteggio dopo aver effettuato n mosse e l'avversario ha effettuato n mosse. In questo caso "n = 3" equivale a un giocatore umano decente, e giocatori umani estremamente buoni possono essere equivalenti a circa "n = 7".

I computer sono abbastanza veloci da fare fino a "n = 7" relativamente velocemente; quindi è tutto relativamente facile da implementare.

Se vuoi distruggere completamente e completamente il gioco (rendendo impossibile per un giocatore umano vincere o divertirti giocando); puoi andare oltre questo. In questo caso ci si deve preoccupare delle "potature" che altre persone hanno menzionato per ridurre il tempo di elaborazione e il consumo di memoria. Il mio consiglio è di non disturbare: ci sono già state troppe persone intelligenti / stupide che hanno rovinato gli scacchi "giocatore contro macchina".