Twist su tic tac toe

Question

Sto scrivendo un programma di tictactoe ma il suo non è il tuo tictactoe tradizionale

Prima di tutto il bordo è 4x4 e il modo per vincere è quello di ottenere 3 di un tipo e 1 dei tuoi avversari in una riga, una colonna o una diagonale. Così il seguente sarebbe una vittoria per "O" via prima colonna:

O|_|X|_ 
O|X|_|_ 
O| |_|_ 
X|_|_|_ 

Sto cercando di implementare un algoritmo minimax al fine di dare al programma una modalità "duro" che non può essere battuto.

Il mio problema è che non posso sperare di creare un albero con tutti i possibili stati di gioco, e quindi devo inventare qualche tipo di funzione che valuti gli stati del gioco che posso generare.

Suppongo che la mia domanda sia, come posso ottenere una tale funzione?

Answer 1

Questo gioco è decisamente abbastanza piccolo per la forza bruta.

È possibile enumerare tutti gli stati. Ci sono 16 caselle, con 3 valori possibili per ogni quadrato (X, O o vuoto).

3^16 = 43046721, circa 43 milioni.

Ciò significa che una tabella con un byte per descrivere la vincita di ciascuno stato sarebbe solo di 43 megabyte.

Avrei creato una funzione che associava ciascuno stato a un indice compreso tra uno e 43 milioni (hai solo bisogno degli stati, non degli eventuali ordini di gioco), in pratica lo rappresenta come un numero in base-3 e ti consente per creare lo stato da un indice.

Selezionare 4 valori di winnability che ciascuno stato potrebbe prendere - winnable per O, winnable per X, non vinabile e sconosciuto.

Assegnare un buffer di lunghezza 43046721 per memorizzare la vincita di ogni stato di gioco.

Iterate attraverso tutti i numeri indice, contrassegnando gli stati vincenti. Quindi passa attraverso e completa iterativamente la vincita di ciascuno degli altri stati, se noti (controlla tutti gli stati successivi, in base a chi è il turno). Ciò richiederà al massimo 16 iterazioni sul set di indici, quindi non vedo alcun motivo per cui la forza bruta non funzionerebbe qui.

Ci sono ottimizzazioni, come approfittare della simmetria, approfittando del fatto che tutti gli stati con n pezzi giù sono seguiti da stati con n + 1 pezzi, ecc., Ma non credo che ne abbiate bisogno all'inizio.

Answer 2

Una funzione euristica per il gioco è quella che valuta un determinato stato del gioco. Qui - lo stato è fondamentalmente composto da due parti: (1) Il consiglio stesso. (2) Di chi è il turno.

Alcuni possibile funzione euristica:

1. numero massimo di X (o O, secondo il giocatore valutato) in linea/colonna/diagonale
2. Numero di "Quasi vincente" sistema limita (con un movimento mancanti) - può essere efficace per massimizzare il numero di possibilità di vincita

Presumo che si possa pensare a più euristiche.
È possibile combinare le vostre diverse euristiche in una funzione euristica "grande" come segue:

a_1 * h_1(state) + a_2 * h_2(state) + ... + a_n * h_n(state) 

La parte difficile sarà quello di imparare i punteggi per a_1, ..., a_n - questo può essere fatto in diversi modi - uno di questi è monte carlo learning - che in pratica significa: creare vari agenti con vari valori a_1,..,a_n, organizzare un torneo tra loro e quando il torneo è terminato - aggiustare i pesi in base ai vincitori - e ripetere il processo mentre hai ancora tempo (è un anytime algorithm).
Una volta terminato, usa i pesi appresi per il tuo agente finale.

P.S. Il numero di giochi possibili è ~ 16! (è necessario determinare l'ordine dei quadrati scelti - sceglie come terminerà il resto del gioco) - chiediti se è "piccolo" abbastanza da essere sviluppato entro i tuoi limiti - o è troppo e una soluzione euristica è davvero necessaria .