We're working on a project and we are completely stuck.
Basically, we are coding a virtual Quoridor player module.
However, our player module thinks that it's starting one square in front of it's home!
Why could this be?
from interface import *
import engine
import random
import time
import copy
class StackNode(object):
"""A building block for stacks.
Each object contains a value and a link to another node.
"""
__slots__ = ( "value", "next" )
def __init__(self,value,next):
"""Set the values of a newly created StackNode"""
self.value = value
self.next = next
class EmptyStackNode(object):
"""A special stack node used to mark the end of the links.
Also, a stack's top containing an instance of this class
implies an empty stack.
"""
__slots__ = ()
class Stack(object):
"""A linear collection accessed in Last-In-First-Out order."""
__slots__ = ( "top" )
def __init__(self):
"""Initialize an empty stack by setting its top to
refer to an EmptyStackNode.
"""
self.top = EmptyStackNode()
def push(self,value):
"""Insert an element onto the top of the stack."""
self.top = StackNode(value,self.top)
def pop(self):
"""Remove the top (newest) element from the stack.
Nothing is returned.
"""
# Precondition: stack is not empty
self.top = self.top.next
def topItem(self):
"""Access and return the top (newest) element in the stack.
The stack does not change.
"""
# Precondition: stack is not empty
return self.top.value
def isEmpty(self):
"""Is the stack empty?"""
return isinstance( self.top, EmptyStackNode )
#Queue and related classes and methods. Implemented by Peter Sevich.
class QueueNode(object):
"""A building block for queues.
Each object contains a value and a link to another node.
"""
__slots__ = ( "value", "next" )
def __init__(self,value,next):
"""Set the values of a newly created QueueNode."""
self.value = value
self.next = next
class EmptyQueueNode(object):
"""A special queue node used to mark the end of the links.
Also, a queue's front and back containing instances of this
class implies an empty queue.
"""
__slots__ = ()
class Queue(object):
"""A linear collection accessed in First-In-First-Out order"""
__slots__ = ( "front", "back" )
def __init__(self):
"""Initialize an empty queue by setting both the front and
back to refer to EmptyQueueNodes.
"""
self.front = EmptyQueueNode() # The front node in the queue
self.back = EmptyQueueNode() # The back node in the queue
def enqueue(self, value):
"""Insert an element onto the back of the queue."""
newnode = QueueNode(value,EmptyQueueNode())
if self.isEmpty():
self.front = newnode
# Front is only updated on enqueue when the queue was empty.
else: # There is a last node; append to it.
self.back.next = newnode
self.back = newnode
def dequeue(self):
"""Remove the front element from the queue."""
# Precondition: queue is not empty
self.front = self.front.next
if self.isEmpty():
self.back = EmptyQueueNode()
# Back is only updated on dequeue if the queue ends up empty.
def frontItem(self):
"""Access and return the first element in the queue.
The queue does not change.
"""
# Precondition: queue is not empty.
return self.front.value
def isEmpty(self):
"""Is the queue empty?"""
return isinstance(self.front, EmptyQueueNode)
class wall(object):
__slots__ = ("cords")
def __init__(self):
self.cords = time.time()
class tile(object):
'''
Left, right, up and down are directions West East North and South (respectively).
'cords' variable is a tuple where the first value represents row, the second column.
'neighbors' is all tiles not seperated by a wall
'''
__slots__ = ("left", "up", "right", "down", "cords", "neighbors", "previous")
def __init__(self, cords):
self.cords = cords
def connect(self, cords, board):
'''Run after initialization of the board to connect all neighboring tiles and
put walls around the outside of the board.
'''
if(self.cords[1]!= 0):
self.left = board.tiles[cords[0]][cords[1]-1]
else:
self.left = wall()
if(self.cords[0]!= board.dims-1):
self.down = board.tiles[cords[0]+1][cords[1]]
else:
self.down = wall()
if(self.cords[1]!= board.dims-1):
self.right = board.tiles[cords[0]][cords[1]+1]
else:
self.right = wall()
if(self.cords[0]!=0):
self.up = board.tiles[cords[0]-1][cords[1]]
else:
self.up = wall()
def find_neighbors(self):
'''Called after adding walls to find the neighbors of every tile not separated by a wall.'''
neighbors = []
if isinstance(self.left, tile):
neighbors.append(self.left)
if isinstance(self.right, tile):
neighbors.append(self.right)
if isinstance(self.up, tile):
neighbors.append(self.up)
if isinstance(self.down, tile):
neighbors.append(self.down)
self.neighbors = neighbors
def __str__(self):
return(str(self.cords))
class board(object):
__slots__ = ("tiles", "dims")
''' 'tiles' is a two dimensional array of all tile objects on the board
dims is equal to the value of BOARD_DIM imported from interface.'''
def __init__(self, BOARD_DIM):
self.dims = BOARD_DIM
self.tiles = [ [ None ] * self.dims for i in range(self.dims) ]
for i in range(self.dims):
for j in range(self.dims):
self.tiles[i][j] = tile([i,j])
for i in range(self.dims):
for j in range(self.dims):
self.tiles[i][j].connect([i,j], self)
def addwalls(self, gameFile):
'''Adds a wall by setting all the directions of the tiles touching the wall to wall instead of another tile.
Preconditions: input file has 2 sets of coordinates R1, C1, R2, C2 per line and that these coordinates
represent walls with a length equal to two'''
file = open(gameFile)
for line in file:
wStart = [int(line.split()[0]),int(line.split()[1])]
wEnd = [int(line.split()[2]), int(line.split()[3])]
if wStart[1] == wEnd[1]:
self.tiles[wStart[0]][wStart[1]].left = wall()
self.tiles[wEnd[0]-1][wEnd[1]].left = wall()
self.tiles[wStart[0]][wStart[1]-1].right = wall()
self.tiles[wEnd[0]-1][wEnd[1]-1].right = wall()
if(wStart[0] == wEnd[0]):
self.tiles[wStart[0]][wStart[1]].up = wall()
self.tiles[wEnd[0]][wEnd[1]-1].up = wall()
self.tiles[wStart[0]-1][wStart[1]].down = wall()
self.tiles[wEnd[0]-1][wEnd[1]-1].down = wall()
def printboard(board, BOARD_DIM):
'''Prints one tile of the board per line in the form "start up right left down"
where i is the row j is the column.'''
for i in range(BOARD_DIM):
for j in range(BOARD_DIM):
print("start:" + str(self.tiles[i][j].cords) + " up:" + str(self.tiles[i][j].up.cords) + " right:" +\
str(self.tiles[i][j].right.cords) + " down:" + str(self.tiles[i][j].down.cords) + " left:" + str(self.tiles[i][j].left.cords))
class player(object):
#Updated by Thomas W. Yoo and Andrew Jaffe
__slots__ = ("board", "playerId", "numPlayers","PlayerLocation", "PlayerDestinations", "PlayerHomes", "wallsRemaining", "locations" )
def __init__(self, board, ID, numPlayers, PlayerLocation, PlayerHomes, wallsRemaining):
self.board = board
self.playerId = ID
self.numPlayers = numPlayers
self.PlayerHomes = PlayerHomes
self.PlayerLocation = self.board.tiles[PlayerHomes[ID][0]][PlayerHomes[ID][1]]
if numPlayers == 1 or numPlayers == 2 :
self.wallsRemaining = wallsRemaining[0]
else:
self.wallsRemaining = wallsRemaining[1]
self.PlayerDestinations = []
self.locations = []
for i in range(numPlayers):
self.locations.append(self.board.tiles[self.PlayerHomes[i][0]][self.PlayerHomes[i][1]])
for i in range(numPlayers):
self.PlayerDestinations.append('temp')
self.PlayerDestinations[i] = set()
for j in range(self.board.dims):
if i == 0:
self.PlayerDestinations[i].add(self.board.tiles[0][j])
if i == 1:
self.PlayerDestinations[i].add(self.board.tiles[self.board.dims -1 ][j])
if i == 2:
self.PlayerDestinations[i].add(self.board.tiles[j][self.board.dims - 1])
if i == 3:
self.PlayerDestinations[i].add(self.board.tiles[j][0])
def init(gameFile, playerId, numPlayers, playerHomes, wallsRemaining):
"""
For all parts the engine calls this method so the player can initialize their data.
gameFile - a string which is the file containing the initial board state.
playerId - the numeric Id of the player (0-4).
numPlayers - the number of players (2 or 4).
playerHomes - a list of coordinates for each players starting cell (PO-P4).
wallsRemaining - the number of walls remaining (same for all players at start).
"""
# log any message string to standard output and the current log file
engine.log_msg("player.init called for player " + str(playerId) + " File=" + gameFile +
', playerId=' + str(playerId) + ', numPlayers=' + str(numPlayers) + ', playerHomes=' +
str(playerHomes) + ', wallsRemaining=' + str(wallsRemaining))
gameboard = board(BOARD_DIM)
gameboard.addwalls(gameFile)
for i in range(BOARD_DIM):
for j in range(BOARD_DIM):
gameboard.tiles[i][j].find_neighbors()
playerData = player(gameboard, playerId, numPlayers, playerHomes, playerHomes, wallsRemaining)
# initialize your data structure here, and then return it. It will be
# passed back to you as 'playerData' in the shortest_path function.
return playerData
def shortest_path(playerData, playerID):
#Updated by Andrew Jaffe and Peter Sevich
"""Returns a list of coordinates representing the shortest path on the
board between the start and finish coordinates.
playerData - The player's data
source - the start coordinate
dest - the end coordinate
"""
board = playerData.board
path = []
# Implement your shortest path algorithm here. If no path is found
# return an empty list.
start = playerData.locations[playerID]
finish = playerData.PlayerDestinations[playerID]
"""start and finish are nodes. Print a path from start to finish."""
visited = set()
stk = Queue()
visited.add(start)
start.previous = None
stk.enqueue(start)
while not stk.isEmpty():
node = stk.frontItem()
stk.dequeue()
if node in finish:
break
for neighbor in node.neighbors:
if neighbor not in visited:
neighbor.previous = node
visited.add(neighbor)
stk.enqueue(neighbor)
if node in visited:
backPath = Stack()
while node != start:
backPath.push(node)
node = node.previous
backPath.push(start)
while not backPath.isEmpty():
path.append(backPath.topItem())
backPath.pop()
if(path[-1] not in finish):
return []
else:
return path
def is_valid_wall(player, start, end):
'''conditions Start and end are neighbors of eachother
start and end are tile objects
wall will be placed above (if horiontal) or left (if vertical) of the tiles
function returns False if wall is not valid
functino returns True if wall is valid'''
if(start.cords[0] == end.cords[0]):#wall is horizontal
if(isinstance(start.up, wall) or isinstance(end.up, wall)):
return False #wall overlaps an already overlaping wall
if(isinstance(start.right, wall) and\
isinstance(player.board.tiles[start.cords[0] - 1][start.cords[1]].right, wall)):
return False #Horizontal wall through a vertical wall
if(start.cords[1] == end.cords[1]):#wall is vertical
if(isinstance(start.left, wall) or isinstance(end.left, wall)):
return False #Vertical wall overlaps
if(isinstance(start.down, wall) and\
isinstance(player.board.tiles[start.cords[0]][start.cords[1] - 1].down, wall)):
return False #Vertical wall crosses a horizontal wall
return True
def place_wall(player, start, end):
'''conditions: start and end are tile objects that are touching
the location of the wall must have already been validated'''
if(start.cords[0] == end.cords[0]):#row equal wall is horizontal
start.up = wall()
start.find_neighbors()
player.board.tiles[start.cords[0]][start.cords[1]-1].down = wall()
player.board.tiles[start.cords[0]][start.cords[1]-1].find_neighbors()
end.up = wall()
end.find_neighbors()
player.board.tiles[end.cords[0]][end.cords[1]-1].down = wall()
player.board.tiles[end.cords[0]][end.cords[1]-1].find_neighbors()
elif(start.cords[1] == end.cords[1]):#column equal wall is vertical
start.left = wall()
start.find_neighbors()
player.board.tiles[start.cords[0]-1][start.cords[1]].right = wall()
player.board.tiles[start.cords[0]-1][start.cords[1]].find_neighbors()
end.left = wall()
end.find_neighbors()
player.board.tiles[end.cords[0]-1][end.cords[1]].right = wall()
player.board.tiles[end.cords[0]-1][end.cords[1]].find_neighbors()
return player
def find_walls(player, start, end):
'''start and end are tiles in player.board.tiles, and are touching
find_walls returns a list of all walls that go between the two'''
walls = []
if(start.cords[0] == end.cords[0]):#row equal path is horizontal #vertical wall
if(start.cords[1] < 8):
walls.append(start, player.board.tiles[start.cords[0]][start.cords[1]+1])#one tile below start
if(start.cords[1] == 8):
walls.append(player.board.tiles[start.cords[0]][start.cords[1]-1], start)
## if(start.cords[1] == 0):
## walls.append(start, player.board.tiles[start.cords[0]][start.cords[1]+1])#oen tile above start
if(start.cords[1] == end.cords[1]):#path is vertical horizontal wall
if(start.cords[0] < 8):
walls.append((start, player.board.tiles[start.cords[0]+1][start.cords[1]]))
if(start.cords[1] == 8):
walls.append((player.board.tiles[start.cords[0]-1][start.cords[1]], start))
## if(start.cords[0] == 0):
## walls.append(start, player.board.tiles[start.cords[0] +1][start.cordss[1]])
for wallnum in range(len(walls)):
if is_valid_wall(player, walls[wallnum][0], walls[wallnum][1]) == False:
walls.pop(wallnum)
return walls
def last_move(playerData, playerMove):
#Written and implemented by Thomas W. Yoo
if playerMove.move == False:
place_wall(playerData,playerData.board.tiles[playerMove.start[0]][playerMove.start[1]],playerData.board.tiles[playerMove.end[0]][playerMove.end[1] - 1])
elif playerMove.move == True:
playerData.locations[playerMove.playerId] = playerData.board.tiles[playerMove.end[0]][playerMove.end[1]]
return playerData
def test_wall(player, start, end, playerids):
'''takes in a valid wall location and a list of players
adds the wall to a test board config and re-evaluates
and returns the shortest paths'''
test = copy.deepcopy(player)
test = place_wall(test, start, end)
player_paths = []
for Id in playerids:
player_paths.append(shortest_path(test, Id))
return player_paths
def find_best_wall(player,target):
print("best wall was called")
'''currently only writen for 2 player mode
tkes in player data
returns a movetype data structure with the placement of the best wall
or if it is better to wait with moving player.playerId forward one on his path'''
player1 = player.playerId #our player
player2 = target #opponent
player1_path = shortest_path(player, player1)
player2_path = shortest_path(player, player2)
player1_paths = []
player2_paths = []
#for player_loc in range(len(player2_path)):
for position in range(len(player2_path) - 1):
walls = find_walls(player, player2_path[position], player2_path[position+1])
for wall in walls:
player_paths = test_wall(player, wall[0], wall[1], (0,1))
if( not(len(player_paths[0]) > len(player1_path))):
player2_paths.append((player_paths[1], wall))
for x in range(len(player2_paths)):
tempmax = len(player2_paths[x])
maxim = 0
if tempmax > maxim:
maxim = tempmax
best_path = player2_paths[x]
wall_spot = best_path[1]
when_to_place = best_path[0][-1]
if( player.locations[player2] == when_to_place):
start = (best_path[1][0].cords[0], best_path[1][0].cords[1])
end = (best_path[1][1].cords[0], best_path[1][1].cords[1])
if end[0] == start [0]:
end[1] += 1
else:
end[0] += 1
print("best wall returned start = " + str(start) + " end = " + str(end))
return PlayerMove(player.playerId, False, start, end)
elif( player.locations[player2] != when_to_place):
start = (player1_path[0].cords[0], player1_path[0].cords[1])
end = (player1_path[1].cords[1], player1_path[1].cords[1])
print("best wall returned start = " + str(start) + " end = " + str(end))
return PlayerMove(player.playerId, True, start, end)
def move(player):
for i in range(player.numPlayers):
player_path = shortest_path(player,player.playerId)
myshort = shortest_path(player,player.playerId)
tempshort = shortest_path(player,i)
currentShortest = tempshort
if len(tempshort) < len(myshort) or len(tempshort) < len(currentShortest):
targetPlayer = i #Target to fuck over
currentShortest = tempshort #Length of above's path
movedata = find_best_wall(player,targetPlayer)
player.PlayerLocation = player.board.tiles[movedata.end[0]][movedata.end[1]]
player.locations[player.playerId] = player.PlayerLocation
else:
start = (player_path[0].cords[0], player_path[0].cords[1])
end = (player_path[1].cords[0], player_path[1].cords[1])
if player.board.tiles[end[0]][end[1]] in player.locations:
if player.board.tiles[end[0]][end[1]] == player.PlayerLocation or( (len(path)>2) and player.board.tiles[path[2][0]][path[2][1]] in player.locations):
end = start
else:
end = (path[2][0],path[2][1])
movedata = PlayerMove(player.playerId, True, start, end)
player.PlayerLocation = player.board.tiles[end[0]][end[1]]
player.locations[player.playerId] = player.PlayerLocation
return player, movedata
