Potatura Alpha Beta in Dama (test case per dimostrare l'efficienza) - algoritmo, testcase, potatura alfa-beta

Ho sviluppato una pedina parallelizzata (inglesebozze) del gioco usando la potatura alfa beta per trovare la mossa ottimale che può essere fatta dalla macchina. Vorrei sapere se l'aumento della profondità / livello dell'albero del gioco e la sua ricerca utilizzando l'algoritmo di potatura alfa beta necessariamente evolve nel miglior modo possibile?

Sto correndo su una macchina di basso livello e non lo sonoin grado di sommare una profondità superiore a 9. Ho controllato il mio programma usando i seguenti casi di test, ma sto ottenendo la stessa mossa possibile considerando la profondità da 1 a 9 come segue.

case 1
+B+B+B+B
B+B+B+B+
+B+B+B+B
O+O+O+O+
+O+O+O+O
A+A+A+A+
+A+A+A+A
A+A+A+A+           output: (5, 0) => (4, 1)

case 2
+B+B+B+B
O+O+B+B+
+O+O+B+B
O+B+O+O+
+O+O+O+O
A+A+A+O+
+O+O+O+O
O+O+O+O+           output: (5, 2) => (4, 3)

case 3
+O+O+O+O
O+O+O+O+
+B+O+O+O
O+O+O+O+
+B+B+O+O
O+A+A+O+
+O+O+O+O
O+O+A+A+           output: (5, 2) => (3, 4)

case 4
+k+O+O+O
O+B+O+O+
+O+O+O+B
O+O+O+B+
+O+O+B+O
O+O+O+O+
+O+O+O+O
A+A+A+A+           output: (0, 1) => (2, 3)

case 5
+B+B+B+B
O+O+O+O+
+O+O+O+O
O+O+O+O+
+B+B+K+O
O+A+O+O+
+O+O+O+O
A+A+O+A+           output: (5, 2) => (3, 0)

case 6
+k+O+O+O
B+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+
+O+O+O+O
O+O+O+O+           output: (0, 1) => (1, 2)

dove sono le interpretazioni,

O- Empty dark square
+- Empty white square
A- Machine"s pawn
B- Opponent"s pawn
k- Machine"s king
K- Opponent"s king

Ho calcolato il valore euristico per ilil nodo foglia dell'albero del gioco come il numero di pezzi della Macchina rimasti nel tabellone sottratti dal numero di pezzi del giocatore avversario, poiché i re hanno un'abilità più potente dei pedoni, l'euristico conta ogni re come due pedine normali, usando quale ricerca alfa beta è applicato.

Immagino che il mio programma funzioni bene, ma l'euristicoi valori calcolati per i nodi foglia dell'albero di gioco alla fine non sono cambiati in quanto aumento la profondità fino a 9 (potrebbe cambiare se aumento ancora di più la profondità). Può chiunque fornirmi alcuni casi di test con cui posso provare l'efficienza all'interno della profondità 9?

risposte:

la tua domanda è abbastanza aperta ma qui un paio di suggerimenti.

1. Il valore euristico calcolato per i nodi foglianon dipende dalla profondità di ricerca, perché sono nodi foglia. Quindi il tuo commento "i valori calcolati per i nodi foglia non cambiano" non ha molto senso, forse vuoi dire che il valore per il nodo radice non è cambiato.

2. Normalmente l'aumento della profondità di ricerca porta a mosse migliori. Se ottieni la stessa mossa "migliore" per tutte le profondità di ricerca 1..9, allora c'è un bug da qualche parte.

3. La funzione di valutazione è la più importantepezzo di una soluzione di ricerca alfa-beta. Avete bisogno di una funzione di valutazione migliore di quella che conta il materiale in modo semplicistico, specialmente se non potete permettervi una ricerca approfondita.

4. Di solito le persone non usano la semplice alfa-beta, ma cose come la ricerca delle variazioni principali, l'approfondimento iterativo, l'euristica con spostamento nulla e così via per aumentare l'efficienza pratica dell'algoritmo.

5. Costruisci i tuoi casi di test in cui sai cosala mossa migliore è effettivamente, e verifica che il tuo algoritmo possa trovarlo. Ad esempio, situazioni di fine gioco in cui sai che un giocatore può vincere in tre mosse.