Vorbestellung Exploration von Tictactoe Suchraum nicht alle Zustände

Question

Ich versuche, q-Learning für Tictactoe zu implementieren. Einer der Schritte dabei besteht darin, alle möglichen Zustände der Tictactoeboard zu einer Zustandswerttabelle aufzulisten. Ich habe eine Prozedur geschrieben, um alle möglichen Zustände ausgehend von der leeren Tafel rekursiv zu generieren. Um dies zu tun, führe ich implizit die Vorbestellung des Suchraumbaums durch. Aber am Ende von allem, ich bekomme nur 707 eindeutige Staaten, während der allgemeine Konsens ist, dass die Anzahl der rechtlichen Staaten rund 5000 ist.

Hinweis: Ich beziehe mich auf die Anzahl der Rechtsstaaten. Ich bin mir bewusst, dass die Anzahl der Staaten näher bei 19.000 liegt, wenn einer der Spieler nach dem Abschluss eines Spiels weiterspielen darf (was ich unter einem illegalen Staat verstehe).

Code:

def generate_state_value_table(self, state, turn): 

    winner = int(is_game_over(state)) #check if, for the current turn and state, game has finished and if so who won 
    #print "\nWinner is ", winner 
    #print "\nBoard at turn: ", turn 
    #print_board(state) 
    self.add_state(state, winner/2 + 0.5) #add the current state with the appropriate value to the state table 
    open_cells = open_spots(state) #find the index (from 0 to total no. of cells) of all the empty cells in the board 

    #check if there are any empty cells in the board 
    if len(open_cells) > 0: 
     for cell in open_cells: 
      #pdb.set_trace() 
      row, col = cell/len(state), cell % len(state) 
      new_state = deepcopy(state) #make a copy of the current state 

      #check which player's turn it is 
      if turn % 2 == 0: 
       new_state[row][col] = 1 
      else: 
       new_state[row][col] = -1   

      #using a try block because recursive depth may be exceeded 
      try: 
       #check if the new state has not been generated somewhere else in the search tree 
       if not self.check_duplicates(new_state): 
        self.generate_state_value_table(new_state, turn+1) 
       else: 
        return 
      except: 
       #print "Recursive depth exceeded" 
       exit() 

    else: 
     return 

Sie im vollständigen Code aussehen kann here wenn Sie möchten.

EDIT: Ich räumte den Code ein wenig sowohl in den Link und hier mit mehr Kommentare, um die Dinge klarer zu machen. Ich hoffe, das hilft.

Answer 1

So habe ich endlich das Problem gelöst und ich stelle diese Antwort für jeden, der ein ähnliches Problem hat. Der Fehler war in der Art, wie ich doppelte Zustände behandelte. Wenn der neue generierte Status zuvor irgendwo anders im Suchbaum generiert wurde, sollte er nicht zur Statustabelle hinzugefügt werden, aber der Fehler, den ich gemacht habe, bestand darin, die Vorbestellung bei der Suche nach einem doppelten Zustand zu unterbrechen ein. setzen

einfach: Entfernen der else-Klausel aus dem Code unten gab mir die Zahl der Staaten als 6046:

#check if the new state has not been generated somewhere else in the search tree 
if not self.check_duplicates(new_state): 
    self.generate_state_value_table(new_state, turn+1) 
else: 
    return 

Außerdem hielt ich den Suchbaum Zweig zu erkunden, wenn ich einen Zustand angetroffen, wo es eine klare war Gewinner. Konkret, habe ich den folgenden Code nach self.add_state(state, winner/2 + 0.5):

#check if the winner returned is one of the players and go back to the previous state if so 
if winner != 0: 
    return 

Dies gab mir die Zahl der Staaten als 5762, das ist das, was ich suchte.