Come può essere ottimizzato il seguente algoritmo?

Naviga le tue risposte
1

Attualmente sto lavorando a un gioco di auto-mover per i tic tac toe. Mi sono imbattuto in un algoritmo decente che consente al computer di costruire facilmente e rivendicare punti vittoria. Il problema però è che quando l'avversario è pericolosamente vicino alla vittoria, il computer continua a costruire verso la propria vittoria invece di bloccare gli avversari, è possibile in qualche modo ottimizzare il seguente algoritmo per contrastarlo?

L'algoritmo funziona come segue:

  1. Inizializza un array intero 3x3

  2. Esegue il ciclo su tutte le possibili combinazioni sulla scheda (0 | 0, 1 | 1, 0 | 2 ... e.tc).

    1. Se la combinazione è una vittoria immediata, fermati e restituisci questa posizione.

    2. Altrimenti avvia un ciclo (che esegue il loop di 1000, 10000 o 100000 volte, a seconda della difficoltà)

      1. Continua a muoverti da entrambe le parti in modo casuale fino a raggiungere la vittoria. Se la vittoria è dal computer, incrementa il contatore dei punti.
  3. Seleziona la posizione della scheda con il punteggio più alto

Questo algoritmo funziona bene e può costruire verso la vittoria (esempio: 

·|x|o    ·|x|o    ·|x|o
·|·|·    x|·|o    x|x|o
·|·|·    ·|·|·    ·|·|o

Tuttavia quando si trova di fronte a una scacchiera come questa 

·|x|o
o|x|·
·|·|·

La mossa ottimale dovrebbe essere quella di spezzare la catena di x, ma il computer si costruisce verso l'innalzamento della propria catena, ovvero spostandosi a 1 | 2 (la scacchiera è 3x3, gli indici partono da zero. Quindi quella sarebbe la terza colonna della seconda riga) .

C'è un modo per ottimizzare questo algoritmo in modo tale che questa debolezza scompaia?

    
posta Aayush Agrawal 28.04.2014 - 08:09
fonte

4 risposte

2

Certo, c'è un modo. Il tuo problema è che la tua definizione di "I win" è troppo ristretta. Come hai sottolineato, una riga di tre è solo una vittoria per te se il tuo avversario non ne ha già uno - quindi la tua metrica deve tracciare le potenziali righe raggiunte da te e il tuo avversario ed evitare stati in cui ricevono una riga completata per prima.

    
risposta data 28.04.2014 - 08:15
fonte
1

Tic-Tac-Toe è un gioco risolto e abbastanza "facile" per programma di programma o espandere (è stato anche fatto in libri ). La pre-programmazione dell'intero gioco è l'approccio ottimale.

Se lavoravi con un gioco più grande (come un gioco 20,20,5 (questi appartengono tutti a una serie di giochi noti come m, n, k giochi - Tic-Tac-Toe può essere descritto come 3,3,3)) quindi conta min-max alberi e ottimizzazioni su di loro entrare in gioco. Per Tic-Tac-Toe, questo è eccessivo.

Lavorare con solo 3,3,3; se il gioco è rappresentato con 0 come cella vuota, +1 come X e -1 come O, la scheda ha alcune proprietà interessanti: 

·|x|o        0 | +1 | -1
o|x|·  -->  -1 | +1 |  0
·|·|·        0 |  0 |  0

Per ogni riga, colonna e diagonale, prendi il valore assoluto della somma degli elementi: 

             0
            /
 0 | +1 | -1 = 0
-1 | +1 |  0 = 0
 0 |  0 |  0 = 0
 =    =    =\ 
 1    2    1 1

Ovunque ci sia un 2, vuoi giocare in quel punto rimanente. Se ci sono due o più punti che possono essere giocati, scegli quello che ha il segno corrispondente al tuo. In questo modo, sei sempre garantito di giocare per vincere o bloccare se possibile.

Questo può essere usato come base per altre euristiche. Gli spot con valore 0 sono piuttosto poco interessanti in quanto sono bloccati ( x | o | . ) o non contestati ( . | . | . ). Il numero di linee contestate che passano attraverso una determinata cella probabilmente lo renderebbe un gioco migliore.

    
risposta data 29.05.2014 - 05:05
fonte
0
  1. guarda se puoi vincere 1 mossa: gioca questa mossa
  2. guarda se puoi impedirgli la vittoria all'ultimo movimento: gioca questa mossa
  3. guarda se puoi vincere 2 mosse: gioca prima di queste 2 mosse (che potrebbero variare in base alla difficoltà o quali impediscono l'altra di vincere)
  4. guarda se puoi impedirgli di vincere a 2 mosse: gioca prima di queste 2 mosse (...)
  5. gioca ovunque
risposta data 28.04.2014 - 08:31
fonte
0

Non sono sicuro di cosa intendi con

Else initiate a loop (That loops either 1000, 10000 or 100000 times, depending on difficulty)

Sembra che tu stia lavorando con un algoritmo genetico rudimentale; in questo caso, hai bisogno di una migliore funzione fitness . In particolare, per ogni possibile risultato del gioco (le tue "tutte le combinazioni"),

  • se l'avversario può vincere con una mossa

dovrebbe avere una priorità più alta di

  • puoi vincere con una mossa

Quando dici

Continually move from both sides randomly till victory is achieved. If victory is by the computer, increment the score counter.

Questo a caso è il tuo problema. Cerca di evitare che ciò accada.

    
risposta data 28.04.2014 - 12:15
fonte

Leggi altre domande sui tag

Design semplice per funzione Singleton in java per Kernel [chiuso] Il problema della gestione delle dipendenze