[Python-checkins] benchmarks: Port PyPy's go benchmark.

brett.cannon python-checkins at python.org
Sat Sep 15 00:12:30 CEST 2012


http://hg.python.org/benchmarks/rev/69e3f1619f32
changeset:   176:69e3f1619f32
user:        Brett Cannon <brett at python.org>
date:        Fri Sep 14 13:41:50 2012 -0400
summary:
  Port PyPy's go benchmark.

files:
  perf.py              |   12 +-
  performance/bm_go.py |  447 +++++++++++++++++++++++++++++++
  2 files changed, 457 insertions(+), 2 deletions(-)


diff --git a/perf.py b/perf.py
--- a/perf.py
+++ b/perf.py
@@ -1653,6 +1653,14 @@
     return SimpleBenchmark(MeasureFannkuch, *args, **kwargs)
 
 
+def MeasureGo(python, options):
+    bm_path = Relative("performance/bm_go.py")
+    return MeasureGeneric(python, options, bm_path, iteration_scaling=1)
+
+def BM_Go(*args, **kwargs):
+    return SimpleBenchmark(MeasureGo, *args, **kwargs)
+
+
 def MeasureMeteorContest(python, options):
     bm_path = Relative("performance/bm_meteor_contest.py")
     return MeasureGeneric(python, options, bm_path, iteration_scaling=1)
@@ -2064,8 +2072,8 @@
                 "logging": ["silent_logging", "simple_logging", "formatted_logging"],
                 # Benchmarks natively 2.x- and 3.x-compatible
                 "2n3": ["calls", "chaos", "fannkuch", "fastpickle",
-                        "fastunpickle", "json_dump_v2", "json_load", "math",
-                        "logging", "meteor_contest", "normal_startup",
+                        "fastunpickle", "go", "json_dump_v2", "json_load",
+                        "math", "logging", "meteor_contest", "normal_startup",
                         "nqueens", "pathlib", "regex", "spectral_norm",
                         "startup_nosite", "richards", "threading",
                         "unpack_sequence"],
diff --git a/performance/bm_go.py b/performance/bm_go.py
new file mode 100644
--- /dev/null
+++ b/performance/bm_go.py
@@ -0,0 +1,447 @@
+import random, math, sys, time
+
+SIZE = 9
+GAMES = 200
+KOMI = 7.5
+EMPTY, WHITE, BLACK = 0, 1, 2
+SHOW = {EMPTY: '.', WHITE: 'o', BLACK: 'x'}
+PASS = -1
+MAXMOVES = SIZE*SIZE*3
+TIMESTAMP = 0
+MOVES = 0
+
+def to_pos(x,y):
+    return y * SIZE + x
+
+def to_xy(pos):
+    y, x = divmod(pos, SIZE)
+    return x, y
+
+class Square:
+    def __init__(self, board, pos):
+        self.board = board
+        self.pos = pos
+        self.timestamp = TIMESTAMP
+        self.removestamp = TIMESTAMP
+        self.zobrist_strings = [random.randrange(9223372036854775807)
+                                for i in range(3)]
+
+    def set_neighbours(self): 
+        x, y = self.pos % SIZE, self.pos // SIZE;
+        self.neighbours = []
+        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
+            newx, newy = x + dx, y + dy
+            if 0 <= newx < SIZE and 0 <= newy < SIZE:
+                self.neighbours.append(self.board.squares[to_pos(newx, newy)])
+
+    def move(self, color):
+        global TIMESTAMP, MOVES
+        TIMESTAMP += 1
+        MOVES += 1
+        self.board.zobrist.update(self, color)
+        self.color = color
+        self.reference = self
+        self.ledges = 0
+        self.used = True
+        for neighbour in self.neighbours:
+            neighcolor = neighbour.color
+            if neighcolor == EMPTY: 
+                self.ledges += 1
+            else:
+                neighbour_ref = neighbour.find(update=True)
+                if neighcolor == color:
+                    if neighbour_ref.reference.pos != self.pos:
+                        self.ledges += neighbour_ref.ledges 
+                        neighbour_ref.reference = self
+                    self.ledges -= 1
+                else:
+                    neighbour_ref.ledges -= 1
+                    if neighbour_ref.ledges == 0:
+                        neighbour.remove(neighbour_ref)
+        self.board.zobrist.add()
+
+    def remove(self, reference, update=True):
+        self.board.zobrist.update(self, EMPTY)
+        self.removestamp = TIMESTAMP
+        if update:
+            self.color = EMPTY
+            self.board.emptyset.add(self.pos)
+#            if color == BLACK:
+#                self.board.black_dead += 1
+#            else:
+#                self.board.white_dead += 1
+        for neighbour in self.neighbours:
+            if neighbour.color != EMPTY and neighbour.removestamp != TIMESTAMP:
+                neighbour_ref = neighbour.find(update)
+                if neighbour_ref.pos == reference.pos:
+                    neighbour.remove(reference, update)
+                else:
+                    if update:
+                        neighbour_ref.ledges += 1
+
+    def find(self, update=False): 
+       reference = self.reference
+       if reference.pos != self.pos:
+           reference = reference.find(update)
+           if update:
+               self.reference = reference
+       return reference
+    
+    def __repr__(self):
+        return repr(to_xy(self.pos))
+
+class EmptySet:
+    def __init__(self, board):
+        self.board = board
+        self.empties = list(range(SIZE*SIZE))
+        self.empty_pos = list(range(SIZE*SIZE))
+
+    def random_choice(self):
+        choices = len(self.empties)
+        while choices:  
+            i = int(random.random()*choices)
+            pos = self.empties[i]
+            if self.board.useful(pos):
+                return pos
+            choices -= 1
+            self.set(i, self.empties[choices])
+            self.set(choices, pos)
+        return PASS
+
+    def add(self, pos):
+        self.empty_pos[pos] = len(self.empties)
+        self.empties.append(pos)
+
+    def remove(self, pos):
+        self.set(self.empty_pos[pos], self.empties[len(self.empties)-1])
+        self.empties.pop()
+
+    def set(self, i, pos): 
+        self.empties[i] = pos
+        self.empty_pos[pos] = i
+
+class ZobristHash:
+    def __init__(self, board):
+        self.board = board
+        self.hash_set = set()
+        self.hash = 0
+        for square in self.board.squares:
+            self.hash ^= square.zobrist_strings[EMPTY]
+        self.hash_set.clear()
+        self.hash_set.add(self.hash)
+
+    def update(self, square, color):
+        self.hash ^= square.zobrist_strings[square.color]
+        self.hash ^= square.zobrist_strings[color]
+
+    def add(self):
+        self.hash_set.add(self.hash)
+    
+    def dupe(self):
+        return self.hash in self.hash_set
+
+class Board:
+    def __init__(self):
+        self.squares = [Square(self, pos) for pos in range(SIZE*SIZE)]
+        for square in self.squares:
+            square.set_neighbours()
+        self.reset()
+
+    def reset(self):
+        for square in self.squares:
+            square.color = EMPTY
+            square.used = False
+        self.emptyset = EmptySet(self)
+        self.zobrist = ZobristHash(self)
+        self.color = BLACK
+        self.finished = False
+        self.lastmove = -2
+        self.history = []
+        self.white_dead = 0
+        self.black_dead = 0
+
+    def move(self, pos):
+        square = self.squares[pos]
+        if pos != PASS:
+            square.move(self.color)
+            self.emptyset.remove(square.pos)
+        elif self.lastmove == PASS:
+            self.finished = True
+        if self.color == BLACK: self.color = WHITE
+        else: self.color = BLACK
+        self.lastmove = pos
+        self.history.append(pos)
+
+    def random_move(self):
+        return self.emptyset.random_choice()
+
+    def useful_fast(self, square):
+        if not square.used:
+            for neighbour in square.neighbours:
+                if neighbour.color == EMPTY:
+                    return True
+        return False
+
+    def useful(self, pos): 
+        global TIMESTAMP
+        TIMESTAMP += 1
+        square = self.squares[pos]
+        if self.useful_fast(square):
+            return True
+        old_hash = self.zobrist.hash
+        self.zobrist.update(square, self.color)
+        empties = opps = weak_opps = neighs = weak_neighs = 0
+        for neighbour in square.neighbours:
+            neighcolor = neighbour.color
+            if neighcolor == EMPTY:
+                empties += 1
+                continue
+            neighbour_ref = neighbour.find()
+            if neighbour_ref.timestamp != TIMESTAMP:
+                if neighcolor == self.color:  
+                    neighs += 1
+                else: 
+                    opps += 1
+                neighbour_ref.timestamp = TIMESTAMP
+                neighbour_ref.temp_ledges = neighbour_ref.ledges
+            neighbour_ref.temp_ledges -= 1
+            if neighbour_ref.temp_ledges == 0:
+                if neighcolor == self.color:  
+                    weak_neighs += 1
+                else:
+                    weak_opps += 1
+                    neighbour_ref.remove(neighbour_ref, update=False)
+        dupe = self.zobrist.dupe()
+        self.zobrist.hash = old_hash
+        strong_neighs = neighs-weak_neighs
+        strong_opps = opps-weak_opps
+        return not dupe and \
+               (empties or weak_opps or (strong_neighs and (strong_opps or weak_neighs)))
+
+    def useful_moves(self):
+        return [pos for pos in self.emptyset.empties if self.useful(pos)]
+
+    def replay(self, history):
+        for pos in history:
+            self.move(pos)
+
+    def score(self, color):
+        if color == WHITE:
+            count = KOMI + self.black_dead
+        else:
+            count = self.white_dead
+        for square in self.squares:
+            squarecolor = square.color
+            if squarecolor == color:
+                count += 1
+            elif squarecolor == EMPTY:
+                surround = 0
+                for neighbour in square.neighbours:
+                    if neighbour.color == color:
+                        surround += 1
+                if surround == len(square.neighbours): 
+                    count += 1
+        return count
+
+    def check(self):
+       for square in self.squares:
+           if square.color == EMPTY:
+               continue
+
+           members1 = set([square])
+           changed = True
+           while changed:
+               changed = False
+               for member in members1.copy():
+                   for neighbour in member.neighbours:
+                       if neighbour.color == square.color and neighbour not in members1:
+                           changed = True
+                           members1.add(neighbour)
+           ledges1 = 0
+           for member in members1:
+               for neighbour in member.neighbours:
+                   if neighbour.color == EMPTY:
+                       ledges1 += 1
+
+           root = square.find()
+
+           #print 'members1', square, root, members1
+           #print 'ledges1', square, ledges1
+
+           members2 = set()
+           for square2 in self.squares:
+               if square2.color != EMPTY and square2.find() == root:
+                   members2.add(square2)
+
+           ledges2 = root.ledges
+           #print 'members2', square, root, members1
+           #print 'ledges2', square, ledges2
+
+           assert members1 == members2
+           assert ledges1 == ledges2, ('ledges differ at %r: %d %d' % (square, ledges1, ledges2))
+
+           empties1 = set(self.emptyset.empties)
+
+           empties2 = set()
+           for square in self.squares:
+               if square.color == EMPTY:
+                   empties2.add(square.pos)
+
+    def __repr__(self):
+        result = []
+        for y in range(SIZE):
+            start = to_pos(0, y)
+            result.append(''.join([SHOW[square.color]+' ' for square in self.squares[start:start+SIZE]]))
+        return '\n'.join(result)
+
+class UCTNode:
+    def __init__(self):
+        self.bestchild = None
+        self.pos = -1
+        self.wins = 0
+        self.losses = 0
+        self.pos_child = [None for x in range(SIZE*SIZE)]
+        self.parent = None
+
+    def play(self, board):
+        """ uct tree search """
+        color = board.color
+        node = self
+        path = [node]
+        while True:
+            pos = node.select(board)
+            if pos == PASS:
+                break
+            board.move(pos)
+            child = node.pos_child[pos]
+            if not child:
+                child = node.pos_child[pos] = UCTNode()
+                child.unexplored = board.useful_moves()
+                child.pos = pos
+                child.parent = node
+                path.append(child)
+                break
+            path.append(child)
+            node = child
+        self.random_playout(board)
+        self.update_path(board, color, path)
+
+    def select(self, board):
+        """ select move; unexplored children first, then according to uct value """
+        if self.unexplored:
+            i = random.randrange(len(self.unexplored))
+            pos = self.unexplored[i]
+            self.unexplored[i] = self.unexplored[len(self.unexplored)-1]
+            self.unexplored.pop()
+            return pos
+        elif self.bestchild:
+            return self.bestchild.pos
+        else:
+            return PASS
+
+    def random_playout(self, board):
+        """ random play until both players pass """
+        for x in range(MAXMOVES): # XXX while not self.finished?
+            if board.finished:
+                break
+            board.move(board.random_move())
+
+    def update_path(self, board, color, path):
+        """ update win/loss count along path """
+        wins = board.score(BLACK) >= board.score(WHITE)
+        for node in path:
+            if color == BLACK: color = WHITE
+            else: color = BLACK
+            if wins == (color == BLACK):
+                node.wins += 1
+            else:
+                node.losses += 1
+            if node.parent:
+                node.parent.bestchild = node.parent.best_child()
+
+    def score(self):
+        winrate = self.wins/float(self.wins+self.losses)
+        parentvisits = self.parent.wins+self.parent.losses
+        if not parentvisits:
+            return winrate
+        nodevisits = self.wins+self.losses
+        return winrate + math.sqrt((math.log(parentvisits))/(5*nodevisits))
+
+    def best_child(self):
+        maxscore = -1
+        maxchild = None
+        for child in self.pos_child:
+            if child and child.score() > maxscore:
+                maxchild = child
+                maxscore = child.score()
+        return maxchild
+
+    def best_visited(self):
+        maxvisits = -1
+        maxchild = None
+        for child in self.pos_child:
+#            if child:
+#                print to_xy(child.pos), child.wins, child.losses, child.score()
+            if child and (child.wins+child.losses) > maxvisits:
+                maxvisits, maxchild = (child.wins+child.losses), child
+        return maxchild
+
+def user_move(board):
+    while True:
+        text = raw_input('?').strip()
+        if text == 'p':
+            return PASS
+        if text == 'q':
+            raise EOFError
+        try:
+            x, y = [int(i) for i in text.split()]
+        except ValueError:
+            continue
+        if not (0 <= x < SIZE and 0 <= y < SIZE):
+            continue
+        pos = to_pos(x, y)
+        if board.useful(pos): 
+            return pos
+
+def computer_move(board):
+    global MOVES
+    pos = board.random_move()
+    if pos == PASS:
+        return PASS
+    tree = UCTNode()
+    tree.unexplored = board.useful_moves()
+    nboard = Board()
+    for game in range(GAMES):
+        node = tree
+        nboard.reset()
+        nboard.replay(board.history)
+        node.play(nboard)
+#    print 'moves', MOVES
+    return tree.best_visited().pos
+
+def versus_cpu():
+    random.seed(1)
+    board = Board()
+    pos = computer_move(board)
+
+def main(n):
+    times = []
+    for i in range(5):
+        versus_cpu() # warmup
+    for i in range(n):
+        t1 = time.time()
+        versus_cpu()
+        t2 = time.time()
+        times.append(t2 - t1)
+    return times
+
+if __name__ == "__main__":
+    import util, optparse
+    parser = optparse.OptionParser(
+        usage="%prog [options]",
+        description="Test the performance of the Go benchmark")
+    util.add_standard_options_to(parser)
+    options, args = parser.parse_args()
+
+    util.run_benchmark(options, options.num_runs, main)
+

-- 
Repository URL: http://hg.python.org/benchmarks


More information about the Python-checkins mailing list