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.numEnemies = 6+1+1+2+3+4+4+4+5+8+1+1
 249                 self.numStillEnemies = 6+1
 250                 self.lastMoved = None
 251
 252
 253
 254         def Setup(self):
 255                 """ Implements Setup part of protocol. Always uses the same setup. Override to create custom setups """
 256                 #sys.stderr.write("BasicAI Setup here...\n");
 257                 setup = sys.stdin.readline().split(' ')
 258                 if len(setup) != 4:
 259                         sys.stderr.write("BasicAI setup fails, expected 4 tokens, got " + str(len(setup)) + " "+str(setup) + "\n")
 260                 self.colour = setup[0]
 261                 self.opponentName = setup[1]
 262                 self.width = int(setup[2])
 263                 self.height = int(setup[3])
 264                 for x in range(0, self.width):
 265                         self.board.append([])
 266                         for y in range(0, self.height):
 267                                 self.board[x].append(None)
 268                 if self.colour == "RED":
 269                         print "FB8sB979B8\nBB99555583\n6724898974\nB314676699"
 270                 elif self.colour == "BLUE":
 271                         print "B314676699\n6724898974\nBB99555583\nFB8sB979B8"
 272                 return True
 273
 274         def MoveCycle(self):
 275                 #sys.stderr.write("BasicAI MakeMove here...\n");
 276                 if self.InterpretResult() == False or self.ReadBoard() == False or self.MakeMove() == False:
 277                         return False
 278                 self.turn += 1
 279                 return self.InterpretResult()
 280
 281         def MakeMove(self):
 282                 """ Randomly moves any moveable piece, or prints "NO_MOVE" if there are none """
 283                 #TODO: Over-ride this function in base classes with more complex move behaviour
 284
 285                 #sys.stderr.write("Sulix's AI makes a move...\n")
 286                 #self.debugPrintBoard()
 287
 288                 if len(self.units) <= 0:
 289                         return False
 290
 291                 index = random.randint(0, len(self.units)-1)
 292                 startIndex = index
 293
 294                 directions = ("UP", "DOWN", "LEFT", "RIGHT")
 295                 bestdir = 0
 296                 bestScare = 999
 297                 bestpiece = None
 298                 while True:
 299                         piece = self.units[index]
 300
 301                         if piece != None and piece.mobile():
 302                                 dirIndex = random.randint(0, len(directions)-1)
 303                                 startDirIndex = dirIndex
 304                                 piece.generateHeatmap(self.width, self.height, self.board)
 305                                 currentScary = piece.getHeatmap(piece.x, piece.y, self.width, self.height) * 0 + piece.turnCount*0 #Perhaps just look for the best move
 306                                 piece.turnCount = piece.turnCount + 1
 307                                 while True:
 308                                         #sys.stderr.write("Trying index " + str(dirIndex) + "\n")
 309                                         p = move(piece.x, piece.y, directions[dirIndex],1)
 310                                         if p[0] >= 0 and p[0] < self.width and p[1] >= 0 and p[1] < self.height:
 311                                                 target = self.board[p[0]][p[1]]
 312                                                 if target == None or (target.colour != piece.colour and target.colour != "NONE" and target.colour != "BOTH"):
 313                                                         scare = piece.getHeatmap(p[0], p[1],self.width, self.height) - currentScary
 314                                                         override = 0
 315                                                         if target != None:
 316                                                                 override = piece.getOverride(target)
 317
 318                                                         if (self.total_turns % 250 < 15) and (self.total_turns > 250):
 319                                                                 scare += random.randint(0, 5)
 320
 321
 322                                                         if override == 1:
 323                                                                 scare = 998
 324                                                         elif override == -1:
 325                                                                 piece.turnCount = 0
 326                                                                 print str(piece.x) + " " + str(piece.y) + " " + directions[dirIndex]
 327                                                                 return True
 328
 329
 330
 331
 332                                                         if scare < bestScare:
 333                                                                 bestdir = dirIndex
 334                                                                 bestScare = scare
 335                                                                 bestpiece = piece
 336
 337                                         dirIndex = (dirIndex + 1) % len(directions)
 338                                         if startDirIndex == dirIndex:
 339                                                 break
 340
 341
 342                         index = (index + 1) % len(self.units)
 343                         if startIndex == index:
 344                                 if bestScare != 999:
 345                                         bestpiece.turnCount = 0
 346                                         print str(bestpiece.x) + " " + str(bestpiece.y) + " "+directions[bestdir]
 347 #                                       bestpiece.debugPrintHeat(self.width, self.height)
 348                                         return True
 349                                 else:
 350                                         print "SURRENDER"
 351                                         return True
 352
 353
 354         def ReadBoard(self):
 355                 """ Reads in the board.
 356                         On the very first turn, sets up the self.board structure
 357                         On subsequent turns, the board is simply read, but the self.board structure is not updated here.
 358                 """
 359                 #sys.stderr.write("BasicAI ReadBoard here...\n");
 360                 for y in range(0,self.height):
 361                         row = sys.stdin.readline().strip()
 362                         if len(row) < self.width:
 363                                 sys.stderr.write("Row has length " + str(len(row)) + " vs " + str(self.width) + "\n")
 364                                 return False
 365                         for x in range(0,self.width):
 366                                 if self.turn == 0:
 367                                         if row[x] == '.':
 368                                                 pass
 369                                         elif row[x] == '#':
 370                                                 self.board[x][y] = Piece(oppositeColour(self.colour), '?',x,y)
 371                                                 self.enemyUnits.append(self.board[x][y])
 372                                         elif row[x] == '+':
 373                                                 self.board[x][y] = Piece("NONE", '+', x, y)
 374                                         else:
 375                                                 self.board[x][y] = Piece(self.colour, row[x],x,y)
 376                                                 self.units.append(self.board[x][y])
 377                                 else:
 378                                         pass
 379                 return True
 380
 381
 382         def InterpretResult(self):
 383                 """ Interprets the result of a move, and updates the board.
 384                         The very first move is ignored.
 385                         On subsequent moves, the self.board structure is updated
 386                 """
 387
 388                 self.total_turns = self.total_turns + 1
 389
 390                 #sys.stderr.write("BasicAI InterpretResult here...\n")
 391                 result = sys.stdin.readline().split(' ')
 392                 #sys.stderr.write("     Read status line \"" + str(result) + "\"\n")
 393                 if self.turn == 0:
 394                         return True
 395
 396                 if result[0].strip() == "QUIT": #Make sure we exit when the manager tells us to!
 397                         return False
 398
 399                 if result[0].strip() == "NO_MOVE": #No move was made, don't need to update anything
 400                         return True
 401
 402                 if len(result) < 4: #Should be at least 4 tokens (X Y DIRECTION OUTCOME) in any other case
 403                         return False
 404
 405                 x = int(result[0].strip())
 406                 y = int(result[1].strip())
 407
 408
 409                 # The piece moved! It's not a bomb
 410                 if self.board[x][y].rank == '?':
 411                         self.board[x][y].rank = '!'
 412                 #sys.stderr.write("     Board position " + str(x) + " " + str(y) + " is OK!\n")
 413
 414                 direction = result[2].strip()
 415
 416                 multiplier = 1
 417                 outcome = result[3].strip()
 418                 outIndex = 3
 419                 if is_integer(outcome):
 420                         multiplier = int(outcome)
 421                         outcome = result[4].strip()
 422                         outIndex = 4
 423
 424                 p = move(x,y,direction, multiplier)
 425
 426                 # It's a scout! I saw it move.
 427                 if multiplier > 1:
 428                         self.board[x][y].rank = '9'
 429
 430                 #Determine attacking piece
 431                 attacker = self.board[x][y]
 432                 self.board[x][y] = None
 433
 434                 if attacker == None:
 435                         return False
 436
 437                 lastMoved = attacker
 438
 439                 defender = self.board[p[0]][p[1]]
 440
 441                 #Update attacker's position (Don't overwrite the board yet though)
 442
 443                 attacker.x = p[0]
 444                 attacker.y = p[1]
 445                 attacker.positions.insert(0, (attacker.x, attacker.y))
 446
 447
 448                 #Determine ranks of pieces if supplied
 449                 if len(result) >= outIndex + 3:
 450                         if defender == None:
 451                                 return False
 452                         attacker.rank = result[outIndex+1].strip()
 453                         if attacker.beenRevealed == False:
 454                                 if attacker.colour == self.colour:
 455                                         self.hiddenAllies[attacker.rank] -= 1
 456                                 elif attacker.colour == oppositeColour(self.colour):
 457                                         self.hiddenEnemies[attacker.rank] -= 1
 458                         attacker.beenRevealed = True
 459                         defender.rank = result[outIndex+2].strip()
 460                         if defender.beenRevealed == False:
 461                                 if defender.colour == self.colour:
 462                                         self.hiddenAllies[defender.rank] -= 1
 463                                 elif defender.colour == oppositeColour(self.colour):
 464                                         self.hiddenEnemies[defender.rank] -= 1
 465
 466                         defender.beenRevealed = True
 467
 468
 469
 470                 if outcome == "OK":
 471                         self.board[p[0]][p[1]] = attacker
 472
 473                 elif outcome == "KILLS":
 474                         self.board[p[0]][p[1]] = attacker
 475
 476                         if defender.colour == self.colour:
 477                                 self.totalAllies[defender.rank] -= 1
 478                                 self.units.remove(defender)
 479                         elif defender.colour == oppositeColour(self.colour):
 480                                 self.totalEnemies[defender.rank] -= 1
 481                                 self.enemyUnits.remove(defender)
 482
 483                 elif outcome == "DIES":
 484                         if attacker.colour == self.colour:
 485                                 self.totalAllies[attacker.rank] -= 1
 486                                 self.units.remove(attacker)
 487                         elif attacker.colour == oppositeColour(self.colour):
 488                                 self.totalEnemies[attacker.rank] -= 1
 489                                 self.enemyUnits.remove(attacker)
 490                         if attacker.rank == 'B':
 491                                 self.numStillEnemies -= 1
 492                                 #if self.numStillEnemies == 0: # There are no bombs left
 493                                 for i in range(0,ranks['s']):
 494                                         scaretable[i][ranks['?']] -= 2
 495
 496                 elif outcome == "BOTHDIE":
 497                         self.board[p[0]][p[1]] = None
 498
 499                         if defender.colour == self.colour:
 500                                 self.totalAllies[defender.rank] -= 1
 501                                 self.units.remove(defender)
 502                         elif defender.colour == oppositeColour(self.colour):
 503                                 self.totalEnemies[defender.rank] -= 1
 504                                 self.enemyUnits.remove(defender)
 505
 506                         if attacker.colour == self.colour:
 507                                 self.totalAllies[attacker.rank] -= 1
 508                                 self.units.remove(attacker)
 509                         elif attacker.colour == oppositeColour(self.colour):
 510                                 self.totalEnemies[attacker.rank] -= 1
 511                                 self.enemyUnits.remove(attacker)
 512                 elif outcome == "FLAG":
 513                         #sys.stderr.write("     Game over!\n")
 514                         return False
 515                 elif outcome == "ILLEGAL":
 516                         #sys.stderr.write("     Illegal move!\n")
 517                         return False
 518                 else:
 519                         #sys.stderr.write("     Don't understand outcome \"" + outcome + "\"!\n");
 520                         return False
 521
 522
 523
 524
 525                 #sys.stderr.write("     Completed interpreting move!\n");
 526                 return True
 527
 528
 529
 530         def debugPrintBoard(self):
 531                 """ For debug purposes only. Prints the board to stderr.
 532                         Does not indicate difference between allied and enemy pieces
 533                         Unknown (enemy) pieces are shown as '?'
 534                 """
 535                 for y in range(0, self.height):
 536                         for x in range(0, self.width):
 537                                 if self.board[x][y] == None:
 538                                         sys.stderr.write(".");
 539                                 else:
 540                                         sys.stderr.write(str(self.board[x][y].rank));
 541                         sys.stderr.write("\n")
 542
 543 if __name__ == "__main__":
 544         sulixAI = SulixAI()
 545         if sulixAI.Setup():
 546                 while sulixAI.MoveCycle():
 547                         pass
 548