# Python Fights online AI creation game
# Copyright (C) 2009 Maxim Sloyko
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as
# published by the Free Software Foundation, either version 3 of the
# License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Affero General Public License for more details.
#
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import random
import weakref
# Size of the board
# This is the size, excluding borders. I.e. borders
# are not the part of the board!
# Cell coordinates start with 0
# Cell (0,0) is in the upper left corner
BOARD_SIZE = (31, 31)
# Initial length of all the pythons
PYTHON_LENGTH = 10
# How far the python can see on the board
VISIBILITY = 3
# Memory cells content kind
MC_ENEMY_HEAD = 'H'
MC_ENEMY_BODY = 'B'
MC_ENEMY_TAIL = 'T'
MC_OWN_HEAD = 'h'
MC_OWN_BODY = 'b'
MC_OWN_TAIL = 't'
MC_CELL_EMPTY = '0'
# Memory cells traits
MCT_NOT = 'N'
MCT_OR = '|'
# Board cell content type.
CELL_HEAD = 301
CELL_BODY = 302
CELL_TAIL = 303
CELL_HEAD_TAIL = 304 # Special case of python length = 1
CELL_OUT_OF_RANGE = 305 # SPecial off the board cell
# Borders (Also can be in memory cells)
BORDER = '_'
# Move Directions
MOVE_NORTH = 1
MOVE_SOUTH = 2
MOVE_EAST = 3
MOVE_WEST = 4
MC_MAX = 2*VISIBILITY
# Transformations, used in slot matching
def rotate0(x, y):
return (x, y)
def rotate90(x, y):
return (MC_MAX - y, x)
def rotate180(x, y):
return (MC_MAX - x, MC_MAX - y)
def rotate270(x, y):
return (y, MC_MAX - x)
def mirrorX(x, y):
return (MC_MAX - x, y)
def rotate90_mirror(x, y):
return (MC_MAX - y, MC_MAX - x)
def rotate180_mirror(x, y):
return (x, MC_MAX - y)
def rotate270_mirror(x, y):
return (y, x)
rotate0.move = MOVE_NORTH
mirrorX.move = MOVE_NORTH
rotate90.move = MOVE_EAST
rotate90_mirror.move = MOVE_EAST
rotate180.move = MOVE_SOUTH
rotate180_mirror.move = MOVE_SOUTH
rotate270.move = MOVE_WEST
rotate270_mirror.move = MOVE_WEST
class Python(object):
"""
This is the single Fight participant. It has several oredered training slots
and NextMove deduction Engine.
"""
def __init__(self, name = None, data = None):
self._data = data or {}
if name:
self._set_name(name)
self.memslot_list = []
@property
def slot_data(self):
return self._data.get('slot_data')
def add_slot(self, slot):
slot.set_python(self)
self.memslot_list.append(slot)
def replace_slot_list(self, slot_list):
self.clear_slots()
for slot in slot_list:
self.add_slot(slot)
def clear_slots(self):
self.memslot_list = []
def _get_name(self):
return self._data.get('name')
def _set_name(self, name):
self._data['name'] = name
name = property(_get_name, _set_name)
def _get_id(self):
return self._data.get('_id')
def _set_id(self, id):
self._data['_id'] = id
id = property(_get_id, _set_id)
def get_next_move(self, board, allowed_moves = None):
for mslot in self.memslot_list:
res = mslot.match(board, allowed_moves = allowed_moves)
if res is not None:
return res
return None
def __str__(self):
return '<--(%s)-->' % self.name
class MemoryCell(object):
"""
This class represents a single cell in a memory slot.
"""
def __init__(self, python = None, kind = None, trait = None):
self.kind = kind
self.trait = trait
if python is not None:
self.python = weakref.ref(python)
else:
self.python = None
def __eq__(self, other):
if other is None:
return False
return (self.kind == other.kind and self.trait == other.trait)
def __ne__(self, other):
if other is None:
return True
return (self.kind != other.kind or self.trait != other.trait)
def set_python(self, python):
assert(python is not None)
self.python = weakref.ref(python)
def match(self, cell):
assert(self.python is not None)
res = False
if cell is None:
res = (self.kind == MC_CELL_EMPTY)
elif self.kind == BORDER:
res = (self.kind == cell.kind)
elif cell.python is None:
return False
elif self.kind in [MC_OWN_HEAD, MC_OWN_BODY, MC_OWN_TAIL]:
res = (cell.python() == self.python()) and\
{MC_OWN_HEAD: cell.is_head, MC_OWN_BODY: cell.is_body, MC_OWN_TAIL: cell.is_tail}[self.kind]()
elif self.kind in [MC_ENEMY_HEAD, MC_ENEMY_BODY, MC_ENEMY_TAIL]:
res = (cell.python() != self.python()) and\
{MC_ENEMY_HEAD: cell.is_head, MC_ENEMY_BODY: cell.is_body, MC_ENEMY_TAIL: cell.is_tail}[self.kind]()
if self.trait == MCT_NOT:
return (not res)
return res
class MemorySlot(object):
"""
This is the single Python's memory slot with one training position.
"""
def __init__(self, python = None, size = 2*VISIBILITY + 1):
if python is not None:
self.python = weakref.ref(python)
else:
self.python = None
self.cell_map = dict()
self.size = size
def get_cell(self, x, y):
return self.cell_map.get((x, y))
def set_cell(self, x, y, mem_cell):
self.cell_map[(x, y)] = mem_cell
if self.python is not None:
mem_cell.set_python(self.python())
def set_python(self, python):
assert(python is not None)
for mc in self.cell_map.values():
mc.set_python(python)
self.python = weakref.ref(python)
def match(self, board, allowed_moves = None):
"""
Given the board and the tuple of the python's head coordinates, try to
match it against the memory cell.
IF the match is successfull, returns the next move direction.
Otherwise returns None
"""
head_x, head_y = board.py_body[self.python()][0]
trans_list = [
rotate0,
mirrorX,
rotate180,
rotate180_mirror,
rotate90,
rotate90_mirror,
rotate270,
rotate270_mirror
]
cell_top_x, cell_top_y = head_x - VISIBILITY, head_y - VISIBILITY
def match_transform(transform):
# Whether or elements are matched
or_matched = None
# Go through the list of cells, matching them one by one.
for (ix_, iy_), mcell in self.cell_map.items():
if mcell.trait == MCT_OR and or_matched:
continue
(ix, iy) = transform(ix_, iy_)
bx, by = cell_top_x + ix, cell_top_y + iy
cell = board.get_cell(bx, by)
match_res = mcell.match(cell)
if mcell.trait == MCT_OR:
or_matched = bool(or_matched) or match_res
elif not match_res:
return False
if or_matched is not None:
return or_matched
else:
return True
if allowed_moves is not None:
trans_list = filter(lambda t: t.move in allowed_moves, trans_list)
# Try all transforms on the current board position
for tf in trans_list:
if match_transform(tf):
return tf.move
return None
class Cell(object):
"""
This is the single board cell.
"""
def __init__(self, python = None, kind = None):
"""
Create new cell.
python -- the python in this cell.
"""
if python is not None:
self.python = weakref.ref(python)
else:
self.python = None
self.kind = kind
def is_head(self):
return self.kind in [CELL_HEAD, CELL_HEAD_TAIL]
def is_body(self):
return self.kind == CELL_BODY
def is_tail(self):
return self.kind in [CELL_TAIL, CELL_HEAD_TAIL]
class GameBoard(object):
"""
This is the board, on which fights take place.
"""
def __init__(self, python_list, max_moves = 1000):
"""
Initialize the board, placing up to four pythons on it.
"""
assert(len(python_list) <= 4)
self.python_list = list(python_list)
# Pythons move in a random order
random.shuffle(self.python_list)
self.width = BOARD_SIZE[0]
self.height = BOARD_SIZE[1]
self.border = Cell(kind = BORDER)
self.out_of_range = Cell(kind = CELL_OUT_OF_RANGE)
self.max_moves = max_moves
self.move_list = []
# 1. Coordinates of the pythons, head to tail.
# Tuples in the form (x, y)
self.py_body = dict([(py, []) for py in self.python_list])
# This is just another representation of the board
# and is calculated from the previous one. In this representation
# tuples (x, y) are mapped to the python object, which is present in the
# cell with that coordinates. If the cell is empty, then it is just not
# present in this mapping
self.matrix = []
# Initial placement of the pythons on the board
# It assumes that the board width and height is more than 2*PYTHON_LENGTH + 3
# self.python_list is not used here intentionally,
# so that the movement order in respect to placement is random too.
for i, py in enumerate(python_list):
if i == 0:
# first one goes north
X = int(self.width/2)
for y in range(PYTHON_LENGTH, 0, -1):
self.py_body[py].append((X, y))
elif i == 1:
# second one goes south
X = int(self.width/2)
for y in range(self.height - PYTHON_LENGTH, self.height):
self.py_body[py].append((X, y))
elif i == 2:
# Third one goes east
Y = int(self.height/2)
for x in range(self.width - PYTHON_LENGTH, self.width):
self.py_body[py].append((x, Y))
elif i == 3:
# The last one goes west
Y = int(self.height/2)
for x in range(PYTHON_LENGTH, 0, -1):
self.py_body[py].append((x, Y))
self.rebuild_matrix()
def rebuild_matrix(self):
self.matrix = [None for i in range(self.width*self.height)]
for py, body in self.py_body.iteritems():
for body_part in body:
kind = CELL_BODY
if body_part == body[0]:
kind = CELL_HEAD
elif body_part == body[-1]:
kind = CELL_TAIL
if body[0] == body[-1]:
kind = CELL_HEAD_TAIL
x, y = body_part
self.matrix[y*self.width + x] = Cell(py, kind = kind)
def place_python(self, python, body_coords):
self.py_body[python] = body_coords
self.rebuild_matrix()
def get_score(self):
"""
Get *current board*'s score for the pythons.
"""
return dict([(py, len(py_list)) for py, py_list in self.py_body.iteritems()])
def set_cell(self, x, y, cell):
self.matrix[y*self.width + x] = cell
def get_cell(self, x, y):
"""
Return the Cell object, representing the content of the cell with
coordinates x, y. If the cell is empty, returns None
"""
if (0 <= x < self.width) and (0 <= y < self.height):
return self.matrix[y*self.width + x]
elif x == -1 and (0 <= y < self.height):
return self.border
elif y == -1 and (0 <= x < self.width):
return self.border
elif x == self.width and (0 <= y < self.height):
return self.border
elif y == self.height and (0 <= x < self.width):
return self.border
else:
return self.out_of_range
def can_move(self, python, direction = None):
assert(self.py_body.has_key(python)) # Where did you get this snake???
result = []
if len(self.py_body[python]):
head_x, head_y = self.py_body[python][0]
allowed_moves = []
for direct, vector in [(MOVE_NORTH, (0, -1)), (MOVE_SOUTH, (0, 1)), (MOVE_WEST, (-1, 0)), (MOVE_EAST, (1, 0))]:
dcell = self.get_cell(head_x + vector[0], head_y + vector[1])
if dcell is None or dcell.kind == CELL_TAIL:
allowed_moves.append(direct)
# TODO: optimize
if direction is not None:
return direction in allowed_moves
else:
return allowed_moves
else:
# Dead
if direction is not None:
return False
else:
return []
def move_python(self, python, direction):
"""
Perform a single python step into specified direction
This method requires the desired direction to be open for move
and python to be alive.
The caller is responsible for checking this.
"""
assert(direction is not None)
assert(direction in [MOVE_WEST, MOVE_EAST, MOVE_NORTH, MOVE_SOUTH])
move_map = {
MOVE_NORTH: (0, -1),
MOVE_SOUTH: (0, 1),
MOVE_EAST: (1, 0),
MOVE_WEST: (-1, 0),
}
py_coords = self.py_body[python]
new_x, new_y = py_coords[0][0] + move_map[direction][0], py_coords[0][1] + move_map[direction][1]
head_cell = self.get_cell(py_coords[0][0], py_coords[0][1])
move_cell = self.get_cell(new_x, new_y)
# Check if there is someone's tail on the new head's position,
# including this very python's own tail!.
if move_cell is not None:
# There is someone
if move_cell.python() == python:
# Bite his own tail
# This can be only when python's length >= 4
body_cell = self.get_cell(*py_coords[-2])
tail_cell = self.get_cell(*py_coords[-1])
self.set_cell(new_x, new_y, head_cell)
self.set_cell(py_coords[-2][0], py_coords[-2][1], tail_cell)
self.set_cell(py_coords[0][0], py_coords[0][1], body_cell)
self.py_body[python].pop()
self.py_body[python].insert(0, (new_x, new_y))
else:
# Bite someone else's tail
# Here we assume that the move is allowed, so only
# enemy tail can be there
enemy_tail_cell = self.get_cell(new_x, new_y)
self.set_cell(new_x, new_y, head_cell)
if len(py_coords) == 1:
head_cell.kind = CELL_HEAD
tail_cell = Cell(python, kind = CELL_TAIL)
self.set_cell(py_coords[0][0], py_coords[0][1], tail_cell)
else:
body_cell = Cell(python, kind = CELL_BODY)
self.set_cell(py_coords[0][0], py_coords[0][1], body_cell)
if len(self.py_body[move_cell.python()]) == 2:
enemy_hx, enemy_hy = self.py_body[move_cell.python()][0]
cell = self.get_cell(enemy_hx, enemy_hy)
cell.kind = CELL_HEAD_TAIL
elif len(self.py_body[move_cell.python()]) > 2:
self.set_cell(self.py_body[move_cell.python()][-2][0], self.py_body[move_cell.python()][-2][1], enemy_tail_cell)
self.py_body[python].insert(0, (new_x, new_y))
self.py_body[move_cell.python()].pop()
else: # Move to the empty cell
self.set_cell(new_x, new_y, head_cell)
if len(self.py_body[python]) > 2:
body_cell = self.get_cell(*py_coords[-2])
tail_cell = self.get_cell(*py_coords[-1])
self.set_cell(py_coords[0][0], py_coords[0][1], body_cell)
self.set_cell(py_coords[-2][0], py_coords[-2][1], tail_cell)
self.set_cell(py_coords[-1][0], py_coords[-1][1], None)
elif len(self.py_body[python]) == 2:
tail_cell = self.get_cell(*py_coords[-1])
self.set_cell(py_coords[-2][0], py_coords[-2][1], tail_cell)
self.set_cell(py_coords[-1][0], py_coords[-1][1], None)
elif len(self.py_body[python]) == 1:
self.set_cell(py_coords[-1][0], py_coords[-1][1], None)
self.py_body[python].insert(0, (new_x, new_y))
self.py_body[python].pop()
def play(self):
"""
Play the single round.
Returns the sequence of moves made by pythons in the order they
represented in python_list
"""
move_list = list()
# Make turns, until the maximum number of moves exceeded
# or pythons can not move anymore or there is only one python left.
for move_num in range(self.max_moves):
turn_map = self.make_turn()
move_list.extend([turn for (py, turn) in sorted(turn_map.iteritems(), key = lambda (p, m): self.python_list.index(p))])
if not any(turn_map.values()):
# Nobody can move, game over
break
# Count pythons whose length is more that zero
if len([body for body in self.py_body.values() if len(body) > 0]) <= 1:
# Only one guy alive
break
self.move_list = move_list
return move_list
def make_turn(self):
"""
Make a single board's turn.
Returns the mapping of moves, pythons made this turn.
"""
res = dict()
# Number of pythons on the board that can not move
# 1. For every python on the board perform the following steps
for py in self.python_list:
# Check if the python can move anywhere at all
allowed_moves = self.can_move(py)
the_move = None
if len(allowed_moves) > 1:
# If it can, then take the part of the board, that is visible to the python
# pass that part to the python, asking where it wants to move.
the_move = py.get_next_move(self)
# If the python responds with no move (None), or unallowed move,
# choose randomly among moves that can be made.
if the_move not in allowed_moves:
the_move = random.choice(allowed_moves)
elif len(allowed_moves) == 1:
# No need to ask for directions, only one possibility of move
the_move = allowed_moves[0]
if the_move is not None:
self.move_python(py, the_move)
res[py] = the_move
return res
class Game(object):
def __init__(self, python_list, round_num = 20, data = None):
assert(python_list is not None)
assert(len(python_list) > 0)
self._data = data or {}
self.results = dict([(p, 0) for p in python_list])
self.python_list = python_list
self.round_num = round_num
self.round_list = []
def get_score(self):
return self.results
def play(self):
for i in range(self.round_num):
board = GameBoard(self.python_list)
board.play()
self.round_list.append(board)
score_map = board.get_score()
for py, score in score_map.iteritems():
self.results[py] += score
