2

先週、aichallenge.org を偶然見つけて、この "Ants" ゲームは、Python と AI のコーディングの両方を学ぶのに良い方法だと思いました。

ゲームは (x,y) グリッドで、最大 1 つのアリを含むことができます。タイルは土地または水として表すことができ、通行できません。

私の AI はうまく機能しており、幅優先探索アルゴリズムによってアリを送り込んで食物を収集し、A* パスファインディングを使用して敵の丘を攻撃しています。

ただし、探索のために実装しようとしているアルゴリズムは、時間がかかりすぎて、約 700 ミリ秒かかります。私の AI は 1 ターンあたり 500 ミリ秒しか許可されていません。つまり、失格です。

探索を実行するには、各タイルに「ExploreValue」を割り当てたいと考えています。この値は、ゲーム開始時に 0 から始まり、タイルが戦争の霧の下に隠れているターンごとに 1 ずつ増加します。タイルが表示されているときは、探索値を 0 にリセットしたいと考えています。各アリの視界半径は 10 マスです。

まず、各アリから幅優先検索を実行して、タイルに「可視」のタグを付けます。これには 1 アリあたり約 10 ミリ秒かかります。その後、マップ上のすべてのタイルを繰り返し処理して、"ExploreValue" を更新します。それらが可視としてタグ付けされている場合、値は 0 にリセットされ、それ以外の場合は 1 増加します。

これは、約 100x100 でなければならないマップでは 0.5 秒以上かかります。

これがコードです。これをより速く実行するにはどうすればよいと思いますか? リストはより高速であるはずなので、すでにリストをセットに変換しました。

def do_setup はゲームの開始時に 1 回実行され、def do_turn はゲームのターンごとに実行されます。

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
4

1 に答える 1

2

Cythonやpypyなど、ここで言及されている通常の python のより高速な代替手段がいくつかあります。

私は個人的に AI Challenge で Cython を使用して、コードの一部を高速化しました。多くを変更する必要はなく、劇的な速度向上が得られます。ここに Cython の紹介があります。

アップデート：

表示されているタイルを見つけるのに問題がある場合は、このスターター パックを調べることをお勧めします。目に見えるタイルを示す 2 次元の numpy 配列があります。

于 2012-04-04T01:27:49.587 に答える