2

上周我偶然发现了 aichallenge.org，我认为这款“蚂蚁”游戏是学习 Python 和学习 AI 编码的好方法。

游戏是一个 (x,y) 网格，最多可以包含一只蚂蚁。瓷砖可以表示为土地或水，这是不可逾越的。

我的 AI 做得很好，通过广度优先搜索算法派蚂蚁去收集食物，并使用 A* 寻路攻击敌人的山丘。

但是，我尝试实现的探索算法花费了太多时间，大约 700 毫秒。我的 AI 每转只允许 500 毫秒，这意味着它被取消资格。

为了进行探索，我想为每个图块分配一个“ExploreValue”。这个值在游戏开始时从 0 开始，每转一圈增加 1 块隐藏在战争迷雾下。当瓷砖可见时，我希望将探索值重置为 0。每只蚂蚁的视线半径为 10 个方格。

首先，我对每只蚂蚁进行广度优先搜索，将图块标记为“可见”。每只蚂蚁大约需要 10 毫秒。之后，我遍历地图上的每个图块以更新它们的“ExploreValue”。如果它们被标记为可见，则该值将重置为 0，否则将其增加 1。

在必须约为 100x100 的地图上，这需要半秒多的时间。

这是代码，你认为我能做些什么来让它运行得更快？我已经将我的列表转换为集合，因为它们应该更快。

def do_setup 在游戏开始时运行一次，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

这里提到的普通 python 有一些更快的替代品，例如Cython和pypy。

我个人在 AI Challenge 中使用 Cython 来加速我的部分代码。您不必进行太多更改，它可以为您提供显着的速度提升。这里有一个很好的 Cython 介绍。

更新：

如果您在查找哪些图块可见时遇到问题，我建议您查看此入门包。它有一个显示可见图块的 2d numpy 数组。

于 2012-04-04T01:27:49.587 回答