Algoritmo per il gioco di Chomp

Question

Sto scrivendo un programma per il gioco del Chomp. È possibile leggere la descrizione del gioco su Wikipedia , però io descrivo brevemente comunque.

Si gioca su una barra di cioccolato di dimensione n x m, vale a dire la barra è suddivisa in n x m quadrati. Ad ogni turno il giocatore di turno sceglie una piazza e mangia tutto qui sotto e destra della piazza prescelta. Così, per esempio, la seguente è una prima mossa valida:

L'obiettivo è quello di costringere l'avversario a mangiare l'ultimo pezzo di cioccolato (è avvelenato).

Per quanto riguarda la parte AI, ho usato un algoritmo minimax con profondità troncamento. Tuttavia non posso trovare una opportuna funzione di valutazione posizione. Il risultato è che, con la mia funzione di valutazione, è abbastanza facile per un giocatore umano per vincere contro il mio programma.

Qualcuno può:

• suggerire una funzione di valutazione buona posizione o
• fornire qualche riferimento utile o
• suggeriscono un algoritmo alternativo?

Answer 1

Quanto sono grandi i vostri consigli?

Se i pannelli sono abbastanza piccola, allora si può risolvere la partita esattamente con la programmazione dinamica. In Python:

n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))

def moves(board):
    return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]

@memoize
def wins(board):
    if not board: return True
    return any(not wins(move) for move in moves(board))

Le vittorie funzione (board) calcola se la scheda è una posizione vincente. La rappresentazione bordo è un insieme di tuple (x, y) indicano se piece (x, y) è ancora sul tavolo. elenco delle schede la funzione muove Calcola le raggiungibile in una mossa.

La logica dietro la funzione di vittorie funziona in questo modo. Se la scheda è vuota sulla nostra mossa l'altro giocatore deve aver mangiato l'ultimo pezzo, così abbiamo vinto. Se la scheda non è vuota allora possiamo vincere se c'è any mossa che possiamo fare in modo che la posizione risultante è una posizione in perdita (cioè non vincere cioè not wins(move)), perché poi abbiamo ottenuto l'altro giocatore in una posizione in perdita.

Sono necessari la funzione Memoize helper che memorizza nella cache i risultati:

def memoize(f):
    cache = dict()
    def memof(x):
        try: return cache[x]
        except:
            cache[x] = f(x)
            return cache[x]
    return memof

Con il caching abbiamo solo calcoliamo chi è il vincitore per una data posizione, una volta, anche se questa posizione è raggiungibile in diversi modi. Per esempio la posizione di una sola fila di cioccolato può essere ottenuta se i primi mangia giocatore tutte le righe rimanenti nella sua prima mossa, ma può anche essere ottenuta attraverso molte altre serie di movimenti. Sarebbe uno spreco per calcolare chi vince sulla scheda singola riga più e più volte, in modo che in cache il risultato. Questo migliora le prestazioni asintotico da qualcosa come O((n*m)^(n+m)) a O((n+m)!/(n!m!)), un grande miglioramento anche se ancora lento per grandi pannelli.

E qui è una funzione di stampa di debug per comodità:

def show(board):
    for x in range(n):
        print '|' + ''.join('x ' if (x,y) in board else '  ' for y in range(m))

Questo codice è ancora piuttosto lento perché il codice non è ottimizzato in alcun modo (e questo è il Python ...). Se si scrive in C o Java in modo efficiente si può probabilmente migliorare le prestazioni più di 100 volte. Si dovrebbe facilmente essere in grado di gestire 10x10 tavole, e probabilmente si può gestire fino a 15x15 da stiro. Si dovrebbe anche usare una rappresentazione scheda diversa, ad esempio una scheda di bit. Forse si sarebbe nemmeno in grado di accelerarlo 1000x se si fanno uso di più processori.

Ecco una derivazione da Minimax

Si comincerà con minimax:

def minimax(board, depth):
  if depth > maxdepth: return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move, depth-1))
    return alpha

Possiamo rimuovere il controllo di profondità di fare una ricerca completa:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -minimax(move))
    return alpha

Perché il gioco si è conclusa, euristica tornerà o -1 o 1, a seconda di quale giocatore ha vinto. Se rappresentiamo -1 come falso e 1 per vero, allora diventa max(a,b) a or b, e -a diventa not a:

def minimax(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not minimax(move)
    return alpha

Si può vedere questo è equivalente a:

def minimax(board):
  if not board: return True
  return any([not minimax(move) for move in moves(board)])

Se avessimo invece iniziato con minimax con potatura alfa-beta:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -beta, -alpha))
      if alpha >= beta: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

La ricerca inizia con alpha = -1 e beta = 1. Non appena alpha diventa 1, le interruzioni del ciclo. Quindi possiamo supporre che i soggiorni alfa -1 e soggiorni di beta 1 nelle chiamate ricorsive. Quindi il codice è equivalente a questo:

def alphabeta(board, alpha, beta):
  if game_ended(board): return heuristic(board)
  else:
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move, -1, 1))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board, -1, 1)

Quindi possiamo semplicemente rimuovere i parametri, in quanto sono sempre passati come gli stessi valori:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = -1
    for move in moves(board):
      alpha = max(alpha, -alphabeta(move))
      if alpha == 1: break
    return alpha

// start the search:
alphabeta(initial_board)

Possiamo ancora fare il passaggio da -1 e 1 a booleani:

def alphabeta(board):
  if game_ended(board): return heuristic(board)
  else:
    alpha = False
    for move in moves(board):
      alpha = alpha or not alphabeta(move))
      if alpha: break
    return alpha

Così si può vedere questo equivale a utilizzare qualsiasi con un generatore che si ferma l'iterazione non appena ha trovato un valore Vero invece che sempre calcolare l'intera lista dei figli:

def alphabeta(board):
  if not board: return True
  return any(not alphabeta(move) for move in moves(board))

Si noti che qui abbiamo any(not alphabeta(move) for move in moves(board)) invece di any([not minimax(move) for move in moves(board)]). Questo accelera la ricerca di circa un fattore 10 per le schede di dimensioni ragionevoli. Non perché la prima forma è più veloce, ma perché ci permette di saltare tutto il resto del ciclo comprese le chiamate ricorsive, non appena abbiamo trovato un valore che è vero.

Quindi il gioco è fatto, la funzione di vittorie era solo ricerca alphabeta sotto mentite spoglie. Il prossimo trucco che abbiamo utilizzato per la vittoria è a Memoize esso. In gioco programmazione di questo sarebbe chiamato utilizzando "tabelle di recepimento". Così la funzione di vittorie sta facendo AlphAbeta ricerca con le tabelle di recepimento. Naturalmente è più semplice di scrivere questo algoritmo direttamente invece di passare attraverso questa derivazione;)

Answer 2

Non credo che una funzione buona valutazione posizione è possibile qui, perché a differenza di giochi come gli scacchi, non c'è c'è 'progresso' a corto di vincere o perdere. L'articolo di Wikipedia suggerisce una soluzione esaustiva è pratico per i computer moderni, e penso che troverete questo è il caso, dato adeguato Memoizzazione e ottimizzazione.

Un gioco correlato si può trovare di interesse è Nim .