Gomoku basata su array AI-algoritmo?

StackOverflow https://stackoverflow.com/questions/2753399

Domanda

via del ritorno Way (si pensi 20+ anni) ho incontrato un codice sorgente del gioco Gomoku in una rivista che ho digitato per il mio computer e aveva un sacco di divertimento con.

La partita era difficile vincere contro, ma l'algoritmo di base per l'IA del computer è stato davvero semplice e non tiene conto di un sacco di codice. Mi chiedo se qualcuno conosce questo algoritmo e ha alcuni link ad alcuni di origine o di teoria in proposito.

Le cose che mi ricordo è che fondamentalmente allocata una matrice che copriva tutto il forum. Poi, ogni volta che, o, messo un pezzo, si aggiungerebbe una serie di pesi per tutte le posizioni sul tabellone che il pezzo sarebbe forse l'impatto.

Per esempio (nota che i pesi sono sicuramente sbagliato, come non mi ricordo chi): 

1   1   1
 2  2  2
  3 3 3
   444
1234X4321
  3 3 3
 2  2  2
1   1   1

Poi è semplicemente scansione della matrice per una posizione aperta con il più basso o il valore più alto.

cose che sto confusi su:

  • Forse aveva due array, uno per me e uno per sé e c'era una ponderazione min / max?
  • Ci potrebbe essere stato più per l'algoritmo, ma al suo interno era fondamentalmente un array e numeri ponderati

Fa questo anello una campana con chiunque a tutti? Chiunque ha ottenuto tutto ciò che avrebbe aiutato?

È stato utile?

Soluzione

Leggendo descrizione, e pensare un po 'su di esso, penso che probabilmente funziona con un singolo array, esattamente come hai descritto.

Per raggiungere l'obiettivo di ottenere cinque-in-a-row si deve (a) impedire all'avversario di successo e (b) avere successo se stessi.

Per avere successo te stesso, devi mettere pietre vicino altre pietre hai già sul tabellone, quindi ha senso per aggiungere un punteggio positivo per i campi accanto alle pietre che potrebbero partecipare a una fila. Sia l'esempio lineari ti ha dato, o qualcosa quadratica probabilmente funzionerebbe bene.

Per evitare che il tuo avversario da riuscire, devi mettere le pietre accanto al sue / i suoi pietre. E 'particolarmente buono se si colpisce due piccioni con una sola pietra, in modo da pietre dell'avversario dovrebbe aumentare il valore dei campi circostanti gli stessi vostro modo fare - le più pietre ha già in fila, più alto è il punteggio, e più è probabile che il algoritmo cercherà di tagliare l'avversario.

La cosa più importante qui è la ponderazione dei diversi campi, e se le pietre dell'avversario sono ponderati in modo diverso rispetto la vostra. Purtroppo non posso fare con questo, ma i valori dovrebbero essere ragionevolmente semplice da capire attraverso prove ed errori una volta che il gioco stesso è scritto.

Tuttavia, questo è un approccio molto semplice, e sarebbe stato superato da un algoritmo di ricerca albero. Ricerca Google, c'è una correlata carta sulla ricerca Threat , che a quanto pare funziona bene per Gomoku. La carta è dietro un pay-wall però: /

Altri suggerimenti

Non ho letto l'articolo, ma dalla descrizione la mia ipotesi sarebbe una qualche forma di Minimax algoritmo

Ho visto questo algoritmo hai citato - era abbastanza semplice e veloce (senza backtracking :-)) ed è giocato molto bene :-) devo avere il posto di origine, ma è un sacco di anni fa ... C'erano pesi per le pietre a seconda della quantità di altre pietre erano nelle vicinanze, e pesi di pietre oponent. Questi erano inferiori in modo l'algoritmo preferito la strategia di attacco.

Ma questo è di algoritmo ovviamente molto banale. Strategia vincente è stato già trovato. Vedere questo documento: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens. Go-Moku e minaccia-Space Ricerca . E mi ha aiutato molto quando ero scrittura il mio programma. In questo modo sarete in grado di programma di scrittura che è molto buono per attaccare l'avversario e la ricerca di combinazioni vincenti.

E 'un gioco antico - Ho trovato il codice a Planet Source Code . Ho giocato a questo gioco durante l'università e in 286 giorni ha avuto una versione di base di esso.

Ecco il programma che si sta cercando ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw /gomoku.c

Si tratta di quasi 40 anni

di lavoro su una versione open source per iPhone.

Hit me up, se interessati a far parte!

https://github.com/kigster/kigomoku

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top