Das Aktualisieren eines Wertes für jede Zelle in einem Raster pro Zug kostet zu viel Zeit. (Ameisen, AIChallenge.org)

Question

Ich bin letzte Woche über aichallenge.org gestolpert und ich dachte dieses "Ameisen" Spiel war ein guter Weg um Python zu lernen und KI zu programmieren.

Das Spiel ist ein (x, y) -Gitter, das bis zu einer Ameise enthalten kann. Fliesen können als Land oder Wasser bezeichnet werden, was unpassierbar ist.

Meine KI macht einen guten Job und schickt Ameisen, um Nahrung durch einen Suchalgorithmus der Breite zu sammeln und feindliche Hügel mit A * Wegfindung anzugreifen.

Der Algorithmus, den ich für die Exploration implementieren möchte, benötigt jedoch viel zu viel Zeit, etwa 700 ms. Meine KI darf nur 500 ms pro Runde haben, was bedeutet, dass sie disqualifiziert wird.

Um die Exploration durchzuführen, möchte ich jeder Kachel einen "ExploreValue" zuweisen. Dieser Wert beginnt bei 0 zu Beginn des Spiels und erhöht sich um 1, wenn das Spielfeld im Kriegsnebel versteckt ist. Wenn eine Kachel sichtbar ist, möchte ich, dass der Erkundungswert auf 0 zurückgesetzt wird. Jede Ameisen hat einen Sichtradius von 10 Quadraten.

Zuerst führe ich eine Breitensuche von jeder Ameise durch, um Kacheln als "sichtbar" zu markieren. Dies dauert etwa 10 ms pro Ant. Danach iteriere ich durch jede Kachel auf der Karte, um ihren "ExploreValue" zu aktualisieren. Wenn sie als sichtbar markiert sind, wird der Wert auf 0 zurückgesetzt, andernfalls wird er um eins erhöht.

Dies dauert mehr als eine halbe Sekunde auf Karten, die etwa 100x100 sein müssen.

Hier ist der Code, was denkst du könnte ich tun, um diesen Lauf schneller zu machen? Ich habe meine Listen bereits in Sets umgewandelt, da sie schneller sein sollen.

def do_setup wird einmal zu Beginn des Spiels ausgeführt, def do_turn wird jede Runde im Spiel ausgeführt.

def do_setup(self, ants): 
    self.tile_visible = set() 

    self.explorevalue = {} 
    for row in range(ants.rows): 
    for col in range(ants.cols): 
     self.explorevalue[(row, col)]=0 


def do_turn(self, ants): 
    self.tile_visible = [] # empty visible list 

#Define visible tiles set: 
    ants_tiles_scan_distance=10 

    for ant in ants.my_ants(): #start bfs of length ants_tiles_can_distance 
     tiles_dist = {} #dict visited tiles 
     tiles_from = {} #dict previous tiles 
     from_nodes=[] 
     from_nodes.append(ant) 
     to_nodes=[] 
     close_friends_count[ant]=0 

     steps=1 
     while (steps<=ants_tiles_scan_distance and len(from_nodes)>=1): 
      for from_node in from_nodes: 
       for new_loc in ants.tiles_voisins[(from_node)]: 

        if (new_loc not in tiles_dist): 
         tiles_dist[new_loc]=steps 
         to_nodes.append(new_loc) 

         if new_loc not in self.tile_visible: 
          self.tile_visible.append(new_loc) 

      from_nodes=to_nodes 
      to_nodes=[] 
      steps=steps+1 


#Update ExploreValues : 
    for tile in self.explorevalue.keys() : 
     if (tile in self.tile_visible): 
      self.explorevalue[tile]=0 
     else: 
      self.explorevalue[tile]=self.explorevalue[tile]+1 

Answer 1

Es gibt ein paar schnellere Alternativen zu normalen Python erwähnt here, wie Cython und pypy.

Ich persönlich habe Cython für die AI-Challenge verwendet, um Teile meines Codes zu beschleunigen. Sie müssen nicht viel ändern und es gibt Ihnen dramatische Geschwindigkeitssteigerungen. Es gibt ein gutes Intro zu Cython here.

Update:

Wenn Sie Probleme bei der Suche sind, die Fliesen sichtbar sind, würde ich in this starter pack suchen empfehlen. Es hat ein 2d numpy Array, das die sichtbaren Kacheln anzeigt.