agents/celsius/celsius.py

   1 #!/usr/bin/python -u
   2
   3 #NOTE: The -u option is required for unbuffered stdin/stdout.
   4 #       If stdin/stdout are buffered, the manager program will not recieve any messages and assume that the agent has timed out.
   5
   6
   7 import sys
   8 import random
   9
  10 ranks = ['B','1','2','3','4','5','6','7','8','9','s','F', '?', '!', '+']
  11
  12 """
  13 The scaretable lists how `scary' pieces are to each other; pieces will move
  14 in the least scary direction.
  15 """
  16
  17 #                B   1  2  3  4  5  6  7  8  9  s  F  ?  !  +
  18 scaretable = [[  0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #B
  19               [  0,  0,-8,-8,-7,-6,-5,-4,-3,-2, 5,-9, 0,-7, 0], #1
  20               [  0,  4, 0,-7,-6,-5,-4,-3,-2,-1,-2,-9,-3,-6, 0], #2
  21               [  0,  4, 2, 0,-6,-5,-4,-3,-2,-1,-2,-9,-2,-5, 0], #3
  22               [  0,  3, 2, 2, 0,-5,-4,-3,-2,-1,-2,-9,-1,-3, 0], #4
  23               [  0,  3, 2, 2, 2, 0,-4,-3,-2,-1,-2,-9, 0,-2, 0], #5
  24               [  0,  3, 2, 2, 2, 2, 0,-3,-2,-1,-2,-9, 1,-1, 0], #6
  25               [  0,  3, 2, 2, 2, 2, 2, 0,-2,-1,-2,-9,-1, 0, 0], #7
  26               [-40,  3, 2, 2, 2, 2, 2, 2, 0,-2,-2,-9,-1, 1, 0], #8
  27               [  0,  3, 2, 2, 2, 2, 2, 2, 2, 0,-2,-9,-2, 2, 0], #9
  28               [  0, -5, 3, 3, 3, 3, 3, 3, 3, 3,-1,-9, 5, 3, 0], #s
  29               [  0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #F
  30               [  0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #?
  31               [  0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #!
  32               [  0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] #+
  33
  34 """
  35 The override table allows moves to be forced or prevented, thus ensuring
  36 that sacrifices are not made.
  37 """
  38 #               B  1  2  3  4  5  6  7  8  9  s  F  ?  !  +
  39 overrides  = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #B
  40               [ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0, 1], #1
  41               [ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1], #2
  42               [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1], #3
  43               [ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1], #4
  44               [ 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1], #5
  45               [ 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,-1, 0, 0, 1], #6
  46               [ 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,-1, 0, 0, 1], #7
  47               [-1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,-1, 0, 0, 1], #8
  48               [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,-1, 0, 0, 1], #9
  49               [ 1,-1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1, 0, 0, 1], #s
  50               [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #F
  51               [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #?
  52               [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], #!
  53               [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] #+
  54
  55
  56 def is_integer(s):
  57         """ Using exceptions for this feels... wrong..."""
  58         try:
  59                 int(s)
  60                 return True
  61         except ValueError:
  62                 return False
  63
  64 def move(x, y, direction, multiplier):
  65         """ Moves point (x,y) in direction, returns a pair """
  66         if direction == "UP":
  67                 return (x,y-multiplier)
  68         elif direction == "DOWN":
  69                 return (x,y+multiplier)
  70         elif direction == "LEFT":
  71                 return (x-multiplier, y)
  72         elif direction == "RIGHT":
  73                 return (x+multiplier, y)
  74         return (x,y)
  75
  76
  77
  78 def oppositeColour(colour):
  79         """ Returns the opposite colour to that given """
  80         if colour == "RED":
  81                 return "BLUE"
  82         elif colour == "BLUE":
  83                 return "RED"
  84         else:
  85                 return "NONE"
  86
  87 class Piece:
  88         """ Class representing a piece
  89                 Pieces have colour, rank and co-ordinates
  90         """
  91         def __init__(self, colour, rank, x, y):
  92                 self.colour = colour
  93                 self.rank = rank
  94                 self.x = x
  95                 self.y = y
  96                 self.lastMoved = -1
  97                 self.beenRevealed = False
  98                 self.positions = [(x, y)]
  99
 100
 101
 102                 self.heatmap = []
 103                 self.turnCount = 0
 104
 105         def mobile(self):
 106                 return self.rank != 'F' and self.rank != 'B' and self.rank != '?' and self.rank != '+'
 107
 108         def valuedRank(self):
 109                 if ranks.count(self.rank) > 0:
 110                         return len(ranks) - 2 - ranks.index(self.rank)
 111                 else:
 112                         return 0
 113
 114         def scariness(self, other):
 115                 scare = scaretable[ranks.index(self.rank)][ranks.index(other.rank)]
 116                 if scare > 0:
 117                         scare = scare * 1
 118                 return scare
 119
 120         def getOverride(self, other):
 121                 return overrides[ranks.index(self.rank)][ranks.index(other.rank)]
 122
 123         def getHeatmap(self, x,y,w,h):
 124                 if (x < 0) or (x >= w) or (y < 0) or (y >= h):
 125                         return 10
 126                 else:
 127                         return self.heatmap[x][y]
 128
 129         def validSquare(self, x, y, width, height, board):
 130                 if x < 0:
 131                         return False
 132                 if y < 0:
 133                         return False
 134                 if x >= width:
 135                         return False
 136                 if y >= height:
 137                         return False
 138                 if board[x][y] != None and board[x][y].colour == self.colour:
 139                         return False
 140                 if board[x][y] != None and board[x][y].rank == '#':
 141                         return False
 142                 return True
 143
 144         def generateHeatmap(self, width, height, board):
 145                 self.heatmap = []
 146                 newmap = []
 147                 for x in range(0,width):
 148                         self.heatmap.append([])
 149                         newmap.append([])
 150                         for y in range(0,height):
 151                                 self.heatmap[x].append(0)
 152                                 newmap[x].append(0)
 153                                 if board[x][y] == None:
 154                                         self.heatmap[x][y] = 0
 155                                         continue
 156                                 if board[x][y].colour == self.colour:
 157                                         if board[x][y].rank == 'F':
 158                                                 self.heatmap[x][y] = -5 # + self.valuedRank()           # Defend our flag
 159                                 else:
 160                                         self.heatmap[x][y] = self.scariness(board[x][y])
 161
 162                 # Make pieces prefer to stay where they are
 163                 #self.heatmap[self.x][self.y] = -0.5
 164
 165                 for i in range(0,min(30,len(self.positions))):
 166                         p = self.positions[len(self.positions)-1-i]
 167                         if board[p[0]][p[1]] != None:
 168                                 self.heatmap[p[0]][p[1]] += 0.2 * ((50 - i)/50)
 169
 170
 171
 172                 for n in range(0,8):
 173                         for x in range(0,width):
 174                                 for y in range(0,height):
 175                                         if self.heatmap[x][y] != 0:
 176                                                 newmap[x][y] = self.heatmap[x][y]
 177                                                 continue
 178                                         newmap[x][y] = 0 #self.heatmap[x][y] * 0.2
 179                                         if self.validSquare(x-1,y,width,height,board):
 180                                                 newmap[x][y] += self.heatmap[x-1][y] * 0.2
 181                                         else:
 182                                                 newmap[x][y] += 0 #self.heatmap[x][y] * 0.1
 183                                         if self.validSquare(x+1,y,width,height,board):
 184                                                 newmap[x][y] += self.heatmap[x+1][y] * 0.2
 185                                         else:
 186                                                 newmap[x][y] += 0 #self.heatmap[x][y] * 0.1
 187                                         if self.validSquare(x,y-1,width,height,board):
 188                                                 newmap[x][y] += self.heatmap[x][y-1] * 0.2
 189                                         else:
 190                                                 newmap[x][y] += 0 #self.heatmap[x][y] * 0.1
 191                                         if self.validSquare(x,y+1,width,height,board):
 192                                                 newmap[x][y] += self.heatmap[x][y+1] * 0.2
 193                                         else:
 194                                                 newmap[x][y] += 0 #self.heatmap[x][y] * 0.1
 195                         self.heatmap = newmap
 196
 197         def debugPrintHeat(self,w,h):
 198                 """ For debug purposes only. Prints the board to stderr.
 199                         Does not indicate difference between allied and enemy pieces
 200                         Unknown (enemy) pieces are shown as '?'
 201                 """
 202                 sys.stderr.write("Pos: " + str(self.x) + ", " + str(self.y) + " -- rank: " + str(self.rank) + "\n")
 203                 for y in range(0, h):
 204                         for x in range(0, w):
 205                                 if (self.heatmap[x][y] - self.heatmap[self.x][self.y] > 0.0):
 206                                         sys.stderr.write("O")
 207                                 elif (self.heatmap[x][y] - self.heatmap[self.x][self.y] == 0.0):
 208                                         sys.stderr.write("X")
 209                                 elif (self.heatmap[x][y] - self.heatmap[self.x][self.y] < 0.0):
 210                                         sys.stderr.write(".")
 211                                 else:
 212                                         sys.stderr.write(" ")
 213                         sys.stderr.write("\n")
 214                 sys.stderr.write("\n")
 215
 216
 217
 218
 219 def valuedRank(rank):
 220         if ranks.count(rank) > 0:
 221                 return len(ranks) - 2 - ranks.index(rank)
 222         else:
 223                 return 0
 224
 225
 226
 227 class SulixAI:
 228         """
 229                 BasicAI class to play a game of stratego
 230                 Implements the protocol correctly. Stores the state of the board in self.board
 231                 Only makes random moves.
 232                 Override method "MakeMove" for more complex moves
 233         """
 234         def __init__(self):
 235                 """ Constructs the BasicAI agent, and starts it playing the game """
 236                 #sys.stderr.write("BasicAI __init__ here...\n");
 237                 self.turn = 0
 238                 self.board = []
 239                 self.units = []
 240                 self.enemyUnits = []
 241
 242                 self.total_turns = 0
 243
 244                 self.totalAllies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1}
 245                 self.totalEnemies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1}
 246                 self.hiddenEnemies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1}
 247                 self.hiddenAllies = {'B':6,'1':1,'2':1,'3':2,'4':3,'5':4,'6':4,'7':4,'8':5,'9':8,'s':1,'F':1}
 248                 self.lastMoved = None
 249
 250
 251
 252         def Setup(self):
 253                 """ Implements Setup part of protocol. Always uses the same setup. Override to create custom setups """
 254                 #sys.stderr.write("BasicAI Setup here...\n");
 255                 setup = sys.stdin.readline().split(' ')
 256                 if len(setup) != 4:
 257                         sys.stderr.write("BasicAI setup fails, expected 4 tokens, got " + str(len(setup)) + " "+str(setup) + "\n")
 258                 self.colour = setup[0]
 259                 self.opponentName = setup[1]
 260                 self.width = int(setup[2])
 261                 self.height = int(setup[3])
 262                 for x in range(0, self.width):
 263                         self.board.append([])
 264                         for y in range(0, self.height):
 265                                 self.board[x].append(None)
 266                 if self.colour == "RED":
 267                         print "FB8sB979B8\nBB99555583\n6724898974\nB314676699"
 268                 elif self.colour == "BLUE":
 269                         print "B314676699\n6724898974\nBB99555583\nFB8sB979B8"
 270                 return True
 271
 272         def MoveCycle(self):
 273                 #sys.stderr.write("BasicAI MakeMove here...\n");
 274                 if self.InterpretResult() == False or self.ReadBoard() == False or self.MakeMove() == False:
 275                         return False
 276                 self.turn += 1
 277                 return self.InterpretResult()
 278
 279         def MakeMove(self):
 280                 """ Randomly moves any moveable piece, or prints "NO_MOVE" if there are none """
 281                 #TODO: Over-ride this function in base classes with more complex move behaviour
 282
 283                 #sys.stderr.write("Sulix's AI makes a move...\n")
 284                 #self.debugPrintBoard()
 285
 286                 if len(self.units) <= 0:
 287                         return False
 288
 289                 index = random.randint(0, len(self.units)-1)
 290                 startIndex = index
 291
 292                 directions = ("UP", "DOWN", "LEFT", "RIGHT")
 293                 bestdir = 0
 294                 bestScare = 999
 295                 bestpiece = None
 296                 while True:
 297                         piece = self.units[index]
 298
 299                         if piece != None and piece.mobile():
 300                                 dirIndex = random.randint(0, len(directions)-1)
 301                                 startDirIndex = dirIndex
 302                                 piece.generateHeatmap(self.width, self.height, self.board)
 303                                 currentScary = piece.getHeatmap(piece.x, piece.y, self.width, self.height) * 0 + piece.turnCount*0 #Perhaps just look for the best move
 304                                 piece.turnCount = piece.turnCount + 1
 305                                 while True:
 306                                         #sys.stderr.write("Trying index " + str(dirIndex) + "\n")
 307                                         p = move(piece.x, piece.y, directions[dirIndex],1)
 308                                         if p[0] >= 0 and p[0] < self.width and p[1] >= 0 and p[1] < self.height:
 309                                                 target = self.board[p[0]][p[1]]
 310                                                 if target == None or (target.colour != piece.colour and target.colour != "NONE" and target.colour != "BOTH"):
 311                                                         scare = piece.getHeatmap(p[0], p[1],self.width, self.height) - currentScary
 312                                                         override = 0
 313                                                         if target != None:
 314                                                                 override = piece.getOverride(target)
 315
 316                                                         if (self.total_turns % 250 < 15) and (self.total_turns > 250):
 317                                                                 scare += random.randint(0, 5)
 318
 319
 320                                                         if override == 1:
 321                                                                 scare = 999
 322                                                         elif override == -1:
 323                                                                 piece.turnCount = 0
 324                                                                 print str(piece.x) + " " + str(piece.y) + " " + directions[dirIndex]
 325                                                                 return True
 326
 327
 328
 329
 330                                                         if scare < bestScare:
 331                                                                 bestdir = dirIndex
 332                                                                 bestScare = scare
 333                                                                 bestpiece = piece
 334
 335                                         dirIndex = (dirIndex + 1) % len(directions)
 336                                         if startDirIndex == dirIndex:
 337                                                 break
 338
 339
 340                         index = (index + 1) % len(self.units)
 341                         if startIndex == index:
 342                                 if bestScare != 999:
 343                                         bestpiece.turnCount = 0
 344                                         print str(bestpiece.x) + " " + str(bestpiece.y) + " "+directions[bestdir]
 345 #                                       bestpiece.debugPrintHeat(self.width, self.height)
 346                                         return True
 347                                 else:
 348                                         print "SURRENDER"
 349                                         return True
 350
 351
 352         def ReadBoard(self):
 353                 """ Reads in the board.
 354                         On the very first turn, sets up the self.board structure
 355                         On subsequent turns, the board is simply read, but the self.board structure is not updated here.
 356                 """
 357                 #sys.stderr.write("BasicAI ReadBoard here...\n");
 358                 for y in range(0,self.height):
 359                         row = sys.stdin.readline().strip()
 360                         if len(row) < self.width:
 361                                 sys.stderr.write("Row has length " + str(len(row)) + " vs " + str(self.width) + "\n")
 362                                 return False
 363                         for x in range(0,self.width):
 364                                 if self.turn == 0:
 365                                         if row[x] == '.':
 366                                                 pass
 367                                         elif row[x] == '#':
 368                                                 self.board[x][y] = Piece(oppositeColour(self.colour), '?',x,y)
 369                                                 self.enemyUnits.append(self.board[x][y])
 370                                         elif row[x] == '+':
 371                                                 self.board[x][y] = Piece("NONE", '+', x, y)
 372                                         else:
 373                                                 self.board[x][y] = Piece(self.colour, row[x],x,y)
 374                                                 self.units.append(self.board[x][y])
 375                                 else:
 376                                         pass
 377                 return True
 378
 379
 380         def InterpretResult(self):
 381                 """ Interprets the result of a move, and updates the board.
 382                         The very first move is ignored.
 383                         On subsequent moves, the self.board structure is updated
 384                 """
 385
 386                 self.total_turns = self.total_turns + 1
 387
 388                 #sys.stderr.write("BasicAI InterpretResult here...\n")
 389                 result = sys.stdin.readline().split(' ')
 390                 #sys.stderr.write("     Read status line \"" + str(result) + "\"\n")
 391                 if self.turn == 0:
 392                         return True
 393
 394                 if result[0].strip() == "QUIT": #Make sure we exit when the manager tells us to!
 395                         return False
 396
 397                 if result[0].strip() == "NO_MOVE": #No move was made, don't need to update anything
 398                         return True
 399
 400                 if len(result) < 4: #Should be at least 4 tokens (X Y DIRECTION OUTCOME) in any other case
 401                         return False
 402
 403                 x = int(result[0].strip())
 404                 y = int(result[1].strip())
 405
 406
 407                 # The piece moved! It's not a bomb
 408                 if self.board[x][y].rank == '?':
 409                         self.board[x][y].rank = '!'
 410                 #sys.stderr.write("     Board position " + str(x) + " " + str(y) + " is OK!\n")
 411
 412                 direction = result[2].strip()
 413
 414                 multiplier = 1
 415                 outcome = result[3].strip()
 416                 outIndex = 3
 417                 if is_integer(outcome):
 418                         multiplier = int(outcome)
 419                         outcome = result[4].strip()
 420                         outIndex = 4
 421
 422                 p = move(x,y,direction, multiplier)
 423
 424                 # It's a scout! I saw it move.
 425                 if multiplier > 1:
 426                         self.board[x][y].rank = '9'
 427
 428                 #Determine attacking piece
 429                 attacker = self.board[x][y]
 430                 self.board[x][y] = None
 431
 432                 if attacker == None:
 433                         return False
 434
 435                 lastMoved = attacker
 436
 437                 defender = self.board[p[0]][p[1]]
 438
 439                 #Update attacker's position (Don't overwrite the board yet though)
 440
 441                 attacker.x = p[0]
 442                 attacker.y = p[1]
 443                 attacker.positions.insert(0, (attacker.x, attacker.y))
 444
 445
 446                 #Determine ranks of pieces if supplied
 447                 if len(result) >= outIndex + 3:
 448                         if defender == None:
 449                                 return False
 450                         attacker.rank = result[outIndex+1].strip()
 451                         if attacker.beenRevealed == False:
 452                                 if attacker.colour == self.colour:
 453                                         self.hiddenAllies[attacker.rank] -= 1
 454                                 elif attacker.colour == oppositeColour(self.colour):
 455                                         self.hiddenEnemies[attacker.rank] -= 1
 456                         attacker.beenRevealed = True
 457                         defender.rank = result[outIndex+2].strip()
 458                         if defender.beenRevealed == False:
 459                                 if defender.colour == self.colour:
 460                                         self.hiddenAllies[defender.rank] -= 1
 461                                 elif defender.colour == oppositeColour(self.colour):
 462                                         self.hiddenEnemies[defender.rank] -= 1
 463
 464                         defender.beenRevealed = True
 465
 466
 467
 468                 if outcome == "OK":
 469                         self.board[p[0]][p[1]] = attacker
 470
 471                 elif outcome == "KILLS":
 472                         self.board[p[0]][p[1]] = attacker
 473
 474                         if defender.colour == self.colour:
 475                                 self.totalAllies[defender.rank] -= 1
 476                                 self.units.remove(defender)
 477                         elif defender.colour == oppositeColour(self.colour):
 478                                 self.totalEnemies[defender.rank] -= 1
 479                                 self.enemyUnits.remove(defender)
 480
 481                 elif outcome == "DIES":
 482                         if attacker.colour == self.colour:
 483                                 self.totalAllies[attacker.rank] -= 1
 484                                 self.units.remove(attacker)
 485                         elif attacker.colour == oppositeColour(self.colour):
 486                                 self.totalEnemies[attacker.rank] -= 1
 487                                 self.enemyUnits.remove(attacker)
 488
 489                 elif outcome == "BOTHDIE":
 490                         self.board[p[0]][p[1]] = None
 491
 492                         if defender.colour == self.colour:
 493                                 self.totalAllies[defender.rank] -= 1
 494                                 self.units.remove(defender)
 495                         elif defender.colour == oppositeColour(self.colour):
 496                                 self.totalEnemies[defender.rank] -= 1
 497                                 self.enemyUnits.remove(defender)
 498
 499                         if attacker.colour == self.colour:
 500                                 self.totalAllies[attacker.rank] -= 1
 501                                 self.units.remove(attacker)
 502                         elif attacker.colour == oppositeColour(self.colour):
 503                                 self.totalEnemies[attacker.rank] -= 1
 504                                 self.enemyUnits.remove(attacker)
 505
 506                 elif outcome == "FLAG":
 507                         #sys.stderr.write("     Game over!\n")
 508                         return False
 509                 elif outcome == "ILLEGAL":
 510                         #sys.stderr.write("     Illegal move!\n")
 511                         return False
 512                 else:
 513                         #sys.stderr.write("     Don't understand outcome \"" + outcome + "\"!\n");
 514                         return False
 515
 516                 #sys.stderr.write("     Completed interpreting move!\n");
 517                 return True
 518
 519
 520
 521         def debugPrintBoard(self):
 522                 """ For debug purposes only. Prints the board to stderr.
 523                         Does not indicate difference between allied and enemy pieces
 524                         Unknown (enemy) pieces are shown as '?'
 525                 """
 526                 for y in range(0, self.height):
 527                         for x in range(0, self.width):
 528                                 if self.board[x][y] == None:
 529                                         sys.stderr.write(".");
 530                                 else:
 531                                         sys.stderr.write(str(self.board[x][y].rank));
 532                         sys.stderr.write("\n")
 533
 534 if __name__ == "__main__":
 535         sulixAI = SulixAI()
 536         if sulixAI.Setup():
 537                 while sulixAI.MoveCycle():
 538                         pass
 539