agents/peternlewis/peternlewis.cpp

   1 #define ASSERTIONS 1
   2 #define DEBUG_RULES 0
   3 #define DEBUG 0
   4 #define SAVE_OUTPUT 1
   5
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <time.h>
   9 #include <cstdlib>
  10 #include <iostream>
  11 #include <iostream>
  12 #include <fstream>
  13 #include <sstream>
  14 #include <vector>
  15 #include <cassert>
  16 #include <sstream>
  17
  18 using namespace std;    // two of two, yay!
  19
  20 typedef bool Boolean;
  21 typedef unsigned long UInt32;
  22
  23 #include "peternlewis.h"
  24
  25 const char *gPieceCharacters = kPieceCharacters;
  26 #if SAVE_OUTPUT
  27 ofstream gOutputFile;
  28 #endif
  29
  30 template <class T>
  31 inline std::string to_string (const T& t)
  32 {
  33         std::stringstream ss;
  34         ss << t;
  35         return ss.str();
  36 }
  37
  38
  39 /*
  40         Author: Peter N Lewis
  41
  42         Originally: Submitted in 1997 to MacTech Programming Challenge and won.
  43         <http://www.mactech.com/articles/mactech/Vol.13/13.11/Nov97Challenge/index.html>
  44
  45         Assumptions:
  46                 Only time we spend thinking is counted against out 10 seconds (not time in GetMove/ReportMove)
  47
  48         Method:
  49                 Basically we keep track of the board and what we know and what they know.
  50                 Each opponent piece has a bit map associated with it describing what pieces it could be.
  51                 As we see more pieces, the bit map is culled.  If the piece moves, the bomb & flag bits are removed.
  52                 If we've seen all Scouts (for example), then the Scout bit is removed from all remaining pieces.
  53                 If all but one bit is remvoed, then we know what the piece is.
  54
  55                 At each turn, we simply apply a sequence of actions (listed below) and take the first action that works.
  56
  57                 It does very little in the way of lookahead (it plans out a path, but doesn't remember it and
  58                 doesn't take it to account any movement by the opposition)
  59
  60                 It keeps a CRC of recent board positions (since the last strike) and doesn't replay any boards
  61                 (we want to win, not draw!).
  62
  63                 If we exceed 10 seconds thinking time, we resign.  Not that this is particularly likely,
  64                 in the games I tried, it spend less than half a second total.
  65
  66         Optimizations:
  67                 None.
  68
  69         Comment:
  70                 It actually plays a half decent game!  The end game is not as good as I'd like, but time is up!
  71 */
  72
  73 /*
  74 USE SPY
  75         If our spy is next to their 1, kill it
  76
  77 DEFEND AGAINST SPY
  78         if we have seen the spy, ignore this case
  79
  80         If an unknown piece is next to the 1, then
  81                 run, attack, have another piece attack, or ignore depending on a table
  82
  83 ATTACK WEAKER
  84         If a known piece is next to a weaker known piece, attack it
  85                 except if it places that piece in a dangerous location
  86
  87 EXPLORE ATTACK
  88         If a 6,7,9 is next to an unknown piece, attack it
  89
  90 RETREAT
  91         If a known piece is next to a stronger known piece, run away
  92                 (preferably towards something that can kill it
  93                 or if it's lowly, towards an unknown piece)
  94
  95 SCOUT
  96         Try advancing scouts rapidly
  97
  98 ATTACK DISTANT
  99         If a known piece is distant, but a clear path leads a slightly better piece towards it, advance the better piece
 100                 (includes miners)
 101
 102 EXPLORE DISTANT
 103         Try exploring (advance lowly pieces towards unknown pieces)
 104
 105 ATTACK KNOWN WITH SAME DISTANT
 106         If a known piece can be attacked by a known identical piece, attack it
 107
 108 FIND FLAG
 109         When few unmoved pieces remain, start assuming they are bombs/flags
 110
 111 MOVE FORWARD
 112         Move any piece we can forward
 113
 114 MOVE
 115         Move any piece we can
 116
 117 RESIGN
 118         Give up
 119 */
 120
 121 static void Output( string what )
 122 {
 123 #if SAVE_OUTPUT
 124         gOutputFile << "<< " << what << "\n";
 125 #endif
 126         cout << what << "\n";
 127 }
 128
 129 static void SaveInput( string what )
 130 {
 131 #if SAVE_OUTPUT
 132         gOutputFile << ">> " << what << "\n";
 133 #endif
 134 }
 135
 136 static void Log( string what )
 137 {
 138 #if SAVE_OUTPUT
 139         gOutputFile << what << "\n";
 140 #endif
 141         cerr << what << "\n";
 142 }
 143
 144 static void Debug( string what )
 145 {
 146 #if SAVE_OUTPUT
 147         gOutputFile << what << "\n";
 148 #endif
 149 #if DEBUG
 150         cerr << what << "\n";
 151 #endif
 152 }
 153
 154 static void Assert( short must, string what )
 155 {
 156         if ( !must ) {
 157 #if ASSERTIONS
 158                 Log( string("Assert failed! ") + what + "\n" );
 159 #endif
 160         }
 161 }
 162
 163 std::vector<string> gLineBuffer;
 164
 165 enum {
 166         kNoNothing = 0x00001FFE,
 167         kStationaryBits = ((1 << kBomb) | (1 << kFlag))
 168 };
 169
 170 enum {
 171         kRepeatedBoards = 1000
 172 };
 173
 174 typedef struct Square {
 175         PlayerColor color;
 176         PieceRank rank;
 177         UInt32 possibilities;
 178 } Square;
 179
 180 typedef Square OurBoard[kBoardSize][kBoardSize];
 181
 182 typedef int Counts[kFlag+1];
 183
 184 typedef UInt32 BoardPossibilities[kBoardSize][kBoardSize];
 185
 186 typedef struct Storage {
 187         OurBoard board;
 188         Counts our_pieces;
 189         Counts their_pieces;
 190         Boolean do_getmove;
 191         Boolean victory;
 192         Square blankSquare;
 193         PlayerColor playerColor;
 194         PlayerColor theirColor;
 195         BoardPossibilities dangers;
 196         BoardPossibilities known_dangers;
 197         UInt32 repeated_board[kRepeatedBoards];
 198         UInt32 repeated_board_count;
 199 } Storage, *StoragePtr;
 200
 201 static void DumpBoard( StoragePtr storage )
 202 {
 203 #if DEBUG
 204         Debug( "DumpBoard:" );
 205         for ( int row = 0; row < kBoardSize; row++ ) {
 206                 string line;
 207                 for ( int col = 0; col < kBoardSize; col++ ) {
 208                         PieceRank rank = storage->board[row][col].rank;
 209                         if ( kMarshall <= rank && rank <= kFlag ) {
 210                                 char left, right;
 211                                 if ( storage->board[row][col].color == kRed ) {
 212                                         left = '{';
 213                                         right = '}';
 214                                 } else {
 215                                         left = '[';
 216                                         right = ']';
 217                                 }
 218                                 line += left;
 219                                 line += gPieceCharacters[rank];
 220                                 line += right;
 221                                 line += ' ';
 222                         } else {
 223                                 line += ' ';
 224                                 if ( rank == kEmpty ) {
 225                                         line += '.';
 226                                 } else if ( rank == kWater ) {
 227                                         line += '*';
 228                                 } else if ( rank == kMoved ) {
 229                                         line += 'M';
 230                                 } else if ( rank == kAddForRankish ) {
 231                                         line += '%';
 232                                 } else if ( rank == kUnknown ) {
 233                                         line += '?';
 234                                 } else {
 235                                         line += '@';
 236                                 }
 237                                 line += ' ';
 238                                 line += ' ';
 239                         }
 240                 }
 241                 Debug( line );
 242         }
 243         Debug( "" );
 244 #endif
 245 }
 246
 247 static PieceRank HelperGetRank(char token)
 248 {
 249         for ( unsigned int ii=0; ii <= strlen(gPieceCharacters); ++ii ) {
 250                 if (gPieceCharacters[ii] == token) {
 251                         return (PieceRank)(ii);
 252                 }
 253         }
 254         return kUnknown;
 255 }
 256
 257 /**
 258  * Tokenise a string
 259  */
 260 static int HelperTokenise(std::vector<string> & buffer, std::string & str, char split = ' ')
 261 {
 262         buffer.clear();
 263         string token = "";
 264         for (unsigned int x = 0; x < str.size(); ++x)
 265         {
 266                 if (str[x] == split && token.size() > 0)
 267                 {
 268                         buffer.push_back(token);
 269                         token = "";
 270                 }
 271                 if (str[x] != split)
 272                         token += str[x];
 273         }
 274         if (token.size() > 0)
 275                 buffer.push_back(token);
 276         return buffer.size();
 277 }
 278
 279 /**
 280  * Convert string to integer
 281  */
 282 static int HelperInteger(std::string & fromStr)
 283 {
 284         stringstream s(fromStr);
 285         int result = 0;
 286         s >> result;
 287         return result;
 288 }
 289
 290 /**
 291  * Read in a line from stdin
 292  */
 293 static void HelperReadLine()
 294 {
 295         std::string buffer = "";
 296         for (char c = cin.get(); c != '\n' && cin.good(); c = cin.get()) {
 297                 buffer += c;
 298         }
 299         SaveInput( buffer );
 300         HelperTokenise( gLineBuffer, buffer );
 301         if ( gLineBuffer.size() == 0 ) {
 302                 Log( "No tokens on line" );
 303                 exit( 99 );
 304         }
 305         if ( gLineBuffer.size() == 0 ) {
 306                 Log( "No tokens on line" );
 307                 exit( 99 );
 308         }
 309         if ( gLineBuffer[0] == "QUIT" || gLineBuffer[0] == "NO_MOVE") {
 310                 Log( "QUIT token found" );
 311                 exit( 99 );
 312         }
 313 }
 314
 315 static void HelperJunkLine( int lines = 1 )
 316 {
 317         while ( lines > 0 ) {
 318                 HelperReadLine();
 319                 lines--;
 320         }
 321 }
 322
 323 enum MoveOutcome {
 324         kMR_OK,
 325         kMR_Kills,
 326         kMR_Dies,
 327         kMR_BothDie
 328 };
 329
 330 static void HelperReadMove( StoragePtr storage, PiecePosition& from, PiecePosition& to, MoveOutcome& result, PieceRank& attacker, PieceRank& defender )
 331 {
 332         HelperReadLine();
 333         if ( gLineBuffer.size() < 4 ) {
 334                 Log( "Less than 4 tokens" );
 335                 exit( 99 );
 336         }
 337         from.col = HelperInteger( gLineBuffer[0] );
 338         from.row = HelperInteger( gLineBuffer[1] );
 339         int move = HelperInteger( gLineBuffer[3] );
 340         if ( move == 0 ) {
 341                 gLineBuffer.insert( gLineBuffer.begin()+3, "1" );
 342                 move = 1;
 343         }
 344         to = from;
 345         std::string dir = gLineBuffer[2];
 346         if (dir == "UP") {
 347                 to.row -= move;
 348         } else if (dir == "DOWN") {
 349                 to.row += move;
 350         } else if (dir == "LEFT") {
 351                 to.col -= move;
 352         } else if (dir == "RIGHT") {
 353                 to.col += move;
 354         } else {
 355                 Log( "DIRECTION ERROR" );
 356                 exit( 99 );
 357         }
 358         attacker = kUnknown;
 359         defender = kUnknown;
 360         std::string res = gLineBuffer[4];
 361         if ( res == "ILLEGAL" ) {
 362                 Log( "Opponent (hopefully) made ILLEGAL move" );
 363                 exit( 99 );
 364         } else if ( res == "OK" ) {
 365                 result = kMR_OK;
 366         } else {
 367                 if ( res == "KILLS" ) {
 368                         result = kMR_Kills;
 369                 } else if ( res == "DIES" ) {
 370                         result = kMR_Dies;
 371                 } else if ( res == "BOTHDIE" ) {
 372                         result = kMR_BothDie;
 373                 } else {
 374                         Log( string("Unknown move result ") + res );
 375                         exit( 99 );
 376                 }
 377                 attacker = HelperGetRank( gLineBuffer[5][0] );
 378                 defender = HelperGetRank( gLineBuffer[6][0] );
 379         }
 380
 381 }
 382
 383 #ifdef false
 384
 385 static const char *board_setup_1[4] = { // 1 = Marshal, ..., 9 = Scout, : = Spy, ; = Bomb, < = Flag
 386         "8;<;77;6;7",
 387         "75;586896;",
 388         "6989954893",
 389         "943159:249",
 390 };
 391
 392 static const char *bobs_board_setup[4] = { // 1 = Marshal, ..., 9 = Scout, : = Spy, ; = Bomb, < = Flag
 393         "<8;645:1;6",
 394         "8277984893",
 395         ";;5756;7;8",
 396         "9949359969",
 397 };
 398
 399 #endif
 400
 401 static const char *board_setup[4] = { // 1 = Marshal, ..., 9 = Scout, : = Spy, ; = Bomb, < = Flag
 402 //      "8;<;67;;77",
 403         "8;<;67;7;7",
 404         "48;3862;89",
 405         "6359954865",
 406         "997159:499",
 407 };
 408
 409 static const char *start_piece_counts = "0112344458161";
 410
 411 static int dR[4] = { 1, 0, -1, 0 };
 412 static int dC[4] = { 0, -1, 0, 1 };
 413
 414 #if ASSERTIONS
 415
 416 static void AssertValidBoard( StoragePtr storage )
 417 {
 418         int piece;
 419         int count1 = 0;
 420         int count2 = 0;
 421         int row, col;
 422
 423         for ( piece = kMarshall; piece <= kFlag; piece++ ) {
 424                 count1 += storage->their_pieces[piece];
 425         }
 426
 427         for ( row = 0; row < kBoardSize; row++ ) {
 428                 for( col = 0; col < kBoardSize; col++ ) {
 429                         if ( storage->board[row][col].color == storage->theirColor
 430                                         && storage->board[row][col].rank == kUnknown ) {
 431                                 count2++;
 432                         }
 433                 }
 434         }
 435
 436         Assert( count1 == count2, "count1 == count2" );
 437 }
 438
 439 #else
 440
 441 #define AssertValidBoard( storage )
 442
 443 #endif
 444
 445 static void PositionPieces(
 446   StoragePtr storage,        /* 1MB of preinitialized storage for your use */
 447   PlayerColor playerColor,  /* you play red or blue, with red playing first */
 448   Board *theBoard           /* provide the initial position of your pieces */
 449 )
 450 {
 451         int row, our_row, their_row, col, board_col;
 452         PlayerColor theirColor;
 453         int piece;
 454         Boolean reverse = (time( NULL ) & 1) != 0;
 455
 456         Assert( strlen(board_setup[0]) == kBoardSize, "strlen(board_setup[0]) == kBoardSize" );
 457         Assert( strlen(board_setup[1]) == kBoardSize, "strlen(board_setup[1]) == kBoardSize" );
 458         Assert( strlen(board_setup[2]) == kBoardSize, "strlen(board_setup[2]) == kBoardSize" );
 459         Assert( strlen(board_setup[3]) == kBoardSize, "strlen(board_setup[3]) == kBoardSize" );
 460
 461         for ( row = 0; row <= 3; row++ ) {
 462                 if ( playerColor == kRed ) {
 463                         our_row = row;
 464                         their_row = (kBoardSize-1)-row;
 465                         theirColor = kBlue;
 466                 } else {
 467                         their_row = row;
 468                         our_row = (kBoardSize-1)-row;
 469                         theirColor = kRed;
 470                 }
 471                 for ( col = 0; col < 10; col++ ) {
 472                         board_col = reverse ? (kBoardSize-1) - col : col;
 473                         (*theBoard)[our_row][col].thePieceRank = (PieceRank) (board_setup[row][board_col] - '0');
 474                         (*theBoard)[our_row][col].thePieceColor = playerColor;
 475
 476                         storage->board[our_row][col].color = playerColor;
 477                         storage->board[our_row][col].rank = (*theBoard)[our_row][col].thePieceRank;
 478                         storage->board[our_row][col].possibilities = kNoNothing;
 479
 480                         storage->board[their_row][col].color = theirColor;
 481                         storage->board[their_row][col].rank = kUnknown;
 482                         storage->board[their_row][col].possibilities = kNoNothing;
 483                 }
 484         }
 485
 486         for ( row = 4; row <= 5; row++ ) {
 487                 for( col = 0; col < kBoardSize; col++ ) {
 488                         storage->board[row][col].color = (PlayerColor)kNoColor;
 489                         storage->board[row][col].rank = (PieceRank) ((col/2 % 2 == 1) ? kWater : kEmpty);
 490                         storage->board[row][col].possibilities = 0;
 491                 }
 492         }
 493
 494         for ( piece = kMarshall; piece <= kFlag; piece++ ) {
 495                 storage->our_pieces[piece] = start_piece_counts[piece] - '0';
 496                 storage->their_pieces[piece] = start_piece_counts[piece] - '0';
 497         }
 498
 499         storage->do_getmove = (playerColor == kBlue);
 500         storage->victory = false;
 501         storage->blankSquare = storage->board[4][0];
 502         storage->playerColor = playerColor;
 503         storage->theirColor = playerColor == kRed ? kBlue : kRed;
 504         storage->repeated_board_count = 0;
 505
 506         AssertValidBoard( storage );
 507 }
 508
 509 static void Learn( StoragePtr storage, Boolean them, int row, int col, PieceRank rank )
 510 {
 511         Boolean gotall;
 512         PlayerColor thiscolor;
 513         int r, c;
 514
 515         if ( storage->board[row][col].rank == kUnknown ) {
 516
 517                 if ( rank == kMoved ) {
 518                         UInt32 possibilities = storage->board[row][col].possibilities;
 519                         possibilities &= ~kStationaryBits;
 520
 521                         if ( (possibilities & (possibilities-1)) == 0 ) { // only one bit on! Now we know!
 522                                 int newrank;
 523                                 newrank = 0;
 524                                 while ( (possibilities & 1) == 0 ) {
 525                                         possibilities >>= 1;
 526                                         newrank++;
 527                                 }
 528                                 rank = (PieceRank)newrank;
 529                         } else {
 530                                 storage->board[row][col].possibilities = possibilities;
 531                         }
 532                 }
 533
 534                 if ( rank != kMoved ) {
 535                         storage->board[row][col].rank = rank;
 536                         storage->board[row][col].possibilities = (1 << rank);
 537                         if ( them ) {
 538                                 gotall = --storage->their_pieces[rank] == 0;
 539                         } else {
 540                                 gotall = --storage->our_pieces[rank] == 0;
 541                         }
 542                         if ( gotall ) {
 543                                 thiscolor = storage->board[row][col].color;
 544                                 for ( r = 0; r < kBoardSize; r++ ) {
 545                                         for ( c = 0; c < kBoardSize; c++ ) {
 546                                                 if ( storage->board[r][c].rank == kUnknown
 547                                                                 && storage->board[r][c].color == thiscolor ) {
 548                                                         UInt32 possibilities = storage->board[r][c].possibilities;
 549                                                         possibilities &= ~ (1 << rank);
 550                                                         storage->board[r][c].possibilities = possibilities;
 551                                                         if ( (possibilities & (possibilities-1)) == 0 ) { // only one bit on!
 552                                                                 int newrank;
 553                                                                 newrank = 0;
 554                                                                 while ( (possibilities & 1) == 0 ) {
 555                                                                         possibilities >>= 1;
 556                                                                         newrank++;
 557                                                                 }
 558                                                                 Learn( storage, them, r, c, (PieceRank)newrank );
 559                                                         }
 560                                                 }
 561                                         }
 562                                 }
 563                         }
 564                 }
 565         } else {
 566                 Assert( rank == kMoved || storage->board[row][col].rank == rank, "rank == kMoved || storage->board[row][col].rank == rank" );
 567         }
 568 }
 569
 570 static void HandleTheirMove( StoragePtr storage, const PiecePosition moveFrom, const PiecePosition moveTo, Boolean moveStrike, const MoveResult moveResult )
 571 {
 572         Assert( moveResult.legalMove, "moveResult.legalMove" ); // They must have made a legal move or we would not be called
 573         Assert( !moveResult.victory, "!moveResult.victory" ); // If they won we would not be called
 574         if ( moveStrike ) {
 575                 Learn( storage, true, moveFrom.row, moveFrom.col, moveResult.rankOfAttacker.thePieceRank );
 576                 Learn( storage, false, moveTo.row, moveTo.col, moveResult.rankOfDefender.thePieceRank );
 577                 if ( moveResult.attackerRemoved && moveResult.defenderRemoved ) {
 578                         storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
 579                         storage->board[moveTo.row][moveTo.col] = storage->blankSquare;
 580                 } else if ( moveResult.attackerRemoved ) {
 581 //                      if ( storage->board[moveTo.row][moveTo.col].rank == kBomb ) {
 582                                 storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
 583 //                      } else {
 584 //                              storage->board[moveFrom.row][moveFrom.col] = storage->board[moveTo.row][moveTo.col];
 585 //                              storage->board[moveTo.row][moveTo.col] = storage->blankSquare;
 586 //                      }
 587                 } else {
 588                         Assert( moveResult.defenderRemoved, "moveResult.defenderRemoved" );
 589                         storage->board[moveTo.row][moveTo.col] = storage->board[moveFrom.row][moveFrom.col];
 590                         storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
 591                 }
 592         } else {
 593                 storage->board[moveTo.row][moveTo.col] = storage->board[moveFrom.row][moveFrom.col];
 594                 storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
 595                 if ( abs(moveTo.row - moveFrom.row) + abs(moveTo.col - moveFrom.col) > 1 ) {
 596                         Learn( storage, true, moveTo.row, moveTo.col, kScout );
 597                 } else {
 598                         Learn( storage, true, moveTo.row, moveTo.col, (PieceRank)kMoved );
 599                 }
 600         }
 601
 602         AssertValidBoard( storage );
 603 }
 604
 605 static Boolean FindPiece( StoragePtr storage, PlayerColor color, PieceRank rank, int *row, int *col )
 606 {
 607         int r, c;
 608
 609         for ( r = 0; r < kBoardSize; r++ ) {
 610                 for( c = 0; c < kBoardSize; c++ ) {
 611                         if ( storage->board[r][c].color == color
 612                                         && storage->board[r][c].rank == rank ) {
 613                                 *row = r;
 614                                 *col = c;
 615                                 return true;
 616                         }
 617                 }
 618         }
 619         return false;
 620 }
 621
 622 static Boolean IsOnBoardWeak( int row, int col )
 623 {
 624         return 0 <= row && row < kBoardSize && 0 <= col && col < kBoardSize;
 625 }
 626
 627 static Boolean IsOnBoard( int row, int col )
 628 {
 629         if ( 0 <= row && row < kBoardSize && 0 <= col && col < kBoardSize ) {
 630                 if ( row <= 3 || row >= 6 ) {
 631                         return true;
 632                 }
 633                 if ( col <= 1 || col >= 8 ) {
 634                         return true;
 635                 }
 636                 if ( 4 <= col && col <= 5 ) {
 637                         return true;
 638                 }
 639         }
 640         return false;
 641 }
 642
 643 static Boolean IsColorPiece( StoragePtr storage, int row, int col, PlayerColor color )
 644 {
 645         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 646         return storage->board[row][col].color == color;
 647 }
 648
 649 static Boolean IsOurPiece( StoragePtr storage, int row, int col )
 650 {
 651         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 652         return storage->board[row][col].color == storage->playerColor;
 653 }
 654
 655 static Boolean IsTheirPiece( StoragePtr storage, int row, int col )
 656 {
 657         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 658         return storage->board[row][col].color == storage->theirColor;
 659 }
 660
 661 static Boolean IsUnknownPiece( StoragePtr storage, int row, int col )
 662 {
 663         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 664         return storage->board[row][col].rank == kUnknown;
 665 }
 666
 667 static Boolean IsRankPiece( StoragePtr storage, int row, int col, PieceRank rank )
 668 {
 669         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 670         return storage->board[row][col].rank == rank;
 671 }
 672
 673 static Boolean IsEmptySquare( StoragePtr storage, int row, int col )
 674 {
 675         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 676         return storage->board[row][col].rank == (PieceRank)kEmpty;
 677 }
 678
 679 static Boolean IsWaterSquare( StoragePtr storage, int row, int col )
 680 {
 681         Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
 682         return storage->board[row][col].rank == (PieceRank)kWater;
 683 }
 684
 685 static Boolean IsLowlyRank( PieceRank rank )
 686 {
 687         return kCaptain <= rank && rank <= kScout && rank != kMiner;
 688 }
 689
 690 static Boolean IsLowlyPiece( StoragePtr storage, int row, int col )
 691 {
 692         Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
 693         return IsLowlyRank( storage->board[row][col].rank );
 694 }
 695
 696 static Boolean IsMovedPiece( StoragePtr storage, int row, int col )
 697 {
 698         Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
 699         return (storage->board[row][col].possibilities & kStationaryBits) == 0;
 700 }
 701
 702 static Boolean IsRevealedPiece( StoragePtr storage, int row, int col )
 703 {
 704         Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
 705         Assert( IsOurPiece( storage, row, col ), "IsOurPiece( storage, row, col )" );
 706         UInt32 possibilities = storage->board[row][col].possibilities;
 707         return ( (possibilities & (possibilities-1)) == 0 );
 708 }
 709
 710 static int CountAdjacentUnknownPieces( StoragePtr storage, PlayerColor color, int row, int col )
 711 {
 712         int d;
 713         int unknowns = 0;
 714
 715         for ( d = 0; d < 4; d++ ) {
 716                 int r = row + dR[d];
 717                 int c = col + dC[d];
 718
 719                 if ( IsOnBoard( r, c ) && IsColorPiece( storage, r, c, color ) && IsUnknownPiece( storage, r, c ) ) {
 720                         unknowns++;
 721                 }
 722         }
 723
 724         return unknowns;
 725 }
 726
 727 static const char *defend_spy_table = "RARROAOORARRRARRXAXAOAOOXAXAXAXA";
 728 // Run/Attack/Other/Nothing, >1 unknown:other:danger:moved
 729
 730 static Boolean LowlyCanAttack( StoragePtr storage, int row, int col, int *otherRow, int *otherCol )
 731 {
 732         for ( int d = 0; d < 4; d++ ) {
 733                 int r = row + dR[d];
 734                 int c = col + dC[d];
 735
 736                 if ( IsOnBoard( r, c )
 737                                 && IsOurPiece( storage, r, c )
 738                                 && IsLowlyPiece( storage, r, c ) ) {
 739                         *otherRow = r;
 740                         *otherCol = c;
 741                         return true;
 742                 }
 743         }
 744         return false;
 745 }
 746
 747 static void UpdateDangerPossibilities( StoragePtr storage )
 748 {
 749         int row, col;
 750
 751         for ( row = 0; row < kBoardSize; row++ ) {
 752                 for( col = 0; col < kBoardSize; col++ ) {
 753                         storage->dangers[row][col] = 0;
 754                         storage->known_dangers[row][col] = 0;
 755                 }
 756         }
 757
 758         for ( row = 0; row < kBoardSize; row++ ) {
 759                 for( col = 0; col < kBoardSize; col++ ) {
 760                         if ( IsTheirPiece( storage, row, col ) ) {
 761                                 UInt32 possibilities = (storage->board[row][col].possibilities & ~kStationaryBits);
 762                                 UInt32 known_possibilities = 0;
 763
 764                                 if ( storage->board[row][col].rank != kUnknown ) {
 765                                         known_possibilities = possibilities;
 766                                 }
 767
 768                                 for ( int d = 0; d < 4; d++ ) {
 769                                         int r = row + dR[d];
 770                                         int c = col + dC[d];
 771
 772                                         if ( IsOnBoard( r, c ) ) {
 773                                                 storage->dangers[r][c] |= possibilities;
 774                                                 storage->known_dangers[r][c] |= known_possibilities;
 775                                         }
 776                                 }
 777
 778                         }
 779                 }
 780         }
 781
 782 }
 783
 784 static UInt32 GetDangerPossibilities( StoragePtr storage, int row, int col )
 785 {
 786         Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
 787         return storage->dangers[row][col];
 788 }
 789
 790 static Boolean PossibilitiesCouldKill( PieceRank rank, UInt32 possibilities )
 791 {
 792         if ( (possibilities & ~kStationaryBits) == 0 ) {
 793                 return false;
 794         }
 795
 796         switch ( rank ) {
 797                 case kFlag:
 798                         return true;
 799                 case kBomb:
 800                         return (possibilities & (1 << kMiner)) != 0;
 801                 case kMarshall:
 802                         return (possibilities & ((1 << kMarshall) + (1<< kSpy))) != 0;
 803                 default:
 804                         return (possibilities & ((1 << (rank+1)) - 1)) != 0;
 805         }
 806 }
 807
 808 static Boolean PossibilitiesCouldKillSafely( PieceRank rank, UInt32 possibilities )
 809 {
 810         if ( (possibilities & ~kStationaryBits) == 0 ) {
 811                 return false;
 812         }
 813
 814         switch ( rank ) {
 815                 case kFlag:
 816                         return true;
 817                 case kBomb:
 818                         return (possibilities & (1 << kMiner)) != 0;
 819                 case kMarshall:
 820                         return (possibilities & ((1<< kSpy))) != 0;
 821                 default:
 822                         return (possibilities & ((1 << rank) - 1)) != 0;
 823         }
 824 }
 825
 826 static Boolean WillKillPossibilities( PieceRank rank, UInt32 possibilities )
 827 {
 828         Assert( possibilities != 0, "possibilities != 0" );
 829
 830         switch ( rank ) {
 831                 case kFlag:
 832                         return false;
 833                 case kBomb:
 834                         return false;
 835                 case kMiner:
 836                         return (possibilities & ~((1 << kScout) + (1 << kBomb) + (1 << kFlag))) == 0;
 837                 case kSpy:
 838                         return (possibilities & ~(1 << kMarshall)) == 0;
 839                 default:
 840                         return (possibilities & (((1 << (rank + 1)) - 1) + (1 << kBomb))) == 0;
 841         }
 842 }
 843
 844 static Boolean WillKillOrSuicidePossibilities( PieceRank rank, UInt32 possibilities )
 845 {
 846         Assert( possibilities != 0, "possibilities != 0" );
 847
 848         switch ( rank ) {
 849                 case kFlag:
 850                         return false;
 851                 case kBomb:
 852                         return false;
 853                 case kMiner:
 854                         return (possibilities & ~((1 << kScout) + (1 << kMiner) + (1 << kBomb) + (1 << kFlag))) == 0;
 855                 case kSpy:
 856                         return (possibilities & ~((1 << kMarshall) + (1 << kSpy))) == 0;
 857                 default:
 858                         return (possibilities & (((1 << rank) - 1) + (1 << kBomb))) == 0;
 859         }
 860 }
 861
 862 static Boolean WillPossibilitiesKill( UInt32 possibilities, PieceRank rank )
 863 {
 864         Assert( possibilities != 0, "possibilities != 0" );
 865         possibilities &= ~kStationaryBits;
 866         if ( possibilities == 0 ) {
 867                 return false;
 868         }
 869
 870         switch ( rank ) {
 871                 case kFlag:
 872                         return true;
 873                 case kBomb:
 874                         return possibilities == (1 << kMiner);
 875                 default:
 876                         return (possibilities & ~((1 << (rank+1))-1)) == 0;
 877         }
 878 }
 879
 880 static Boolean FindSafeSquare( StoragePtr storage, int row, int col, int *safeRow, int *safeCol )
 881 {
 882         Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
 883
 884         PieceRank rank = storage->board[row][col].rank;
 885         int doff = (storage->playerColor == kBlue ? 0 : 2); // Try backwards first
 886
 887         for ( int d = 0; d < 4; d++ ) {
 888                 int dr = dR[(d + doff) % 4];
 889                 int dc = dC[(d + doff) % 4];
 890                 int r = row + dr;
 891                 int c = col + dc;
 892
 893                 while ( IsOnBoard( r, c ) && IsEmptySquare( storage, r, c ) ) {
 894                         if ( !PossibilitiesCouldKill( rank, GetDangerPossibilities( storage, r, c ) ) ) {
 895                                 *safeRow = r;
 896                                 *safeCol = c;
 897                                 return true;
 898                         }
 899                         if ( rank != kScout ) {
 900                                 break;
 901                         }
 902                         r += dr;
 903                         c += dc;
 904                 }
 905         }
 906         return false;
 907 }
 908
 909 static void CountEnemies( StoragePtr storage, int row, int col, int *knowns, int *unknowns )
 910 {
 911         *knowns = 0;
 912         *unknowns = 0;
 913
 914         for ( int d = 0; d < 4; d++ ) {
 915                 int r = row + dR[d];
 916                 int c = col + dC[d];
 917
 918                 if ( IsOnBoard( r, c ) && IsTheirPiece( storage, r, c ) ) {
 919                         if ( storage->board[r][c].rank == kUnknown ) {
 920                                 *unknowns += 1;
 921                         } else {
 922                                 *knowns += 1;
 923                         }
 924                 }
 925         }
 926 }
 927
 928 /*
 929 static Boolean CanRun( StoragePtr storage, int row, int col, int *runRow, int *runCol )
 930 {
 931         for ( int d = 0; d < 4; d++ ) {
 932                 int r = row + dR[(d + (storage->playerColor == kBlue ? 0 : 2)) % 4]; // Try backwards first
 933                 int c = col + dC[(d + (storage->playerColor == kBlue ? 0 : 2)) % 4];
 934
 935                 if ( IsOnBoard( r, c ) && (storage->board[r][c].rank == kEmpty) ) {
 936                         *runRow = r;
 937                         *runCol = c;
 938                         return true;
 939                 }
 940         }
 941         return false;
 942 }
 943 */
 944
 945 static Boolean FindSafePath( StoragePtr storage, Boolean very_safe, Boolean suicide_ok, int from_row, int from_col, int to_row, int to_col, int *best_path, int *first_row, int *first_col )
 946 {
 947         Assert( IsOurPiece( storage, from_row, from_col ), "IsOurPiece( storage, from_row, from_col )" );
 948
 949         PieceRank rank = storage->board[from_row][from_col].rank;
 950         BoardPossibilities *dangers = very_safe ? &storage->dangers : &storage->known_dangers;
 951
 952         if ( abs( from_row - to_row ) + abs( from_col - to_col ) > *best_path ) {
 953                 return false;
 954         }
 955
 956         if ( abs( from_row - to_row ) + abs( from_col - to_col ) == 1 ) {
 957                 *best_path = 0;
 958                 *first_row = to_row;
 959                 *first_col = to_col;
 960                 return true;
 961         }
 962
 963         int path_length_to[kBoardSize][kBoardSize];
 964         PiecePosition que[kBoardSize * kBoardSize];
 965         int que_start = 0;
 966         int que_fin = 0;
 967         int que_next_len = 0;
 968         int current_len = 0;
 969         int row, col;
 970
 971         for ( row = 0; row < kBoardSize; row++ ) {
 972                 for( col = 0; col < kBoardSize; col++ ) {
 973                         path_length_to[row][col] = -1;
 974                 }
 975         }
 976
 977         que[que_fin].row = from_row;
 978         que[que_fin].col = from_col;
 979         path_length_to[from_row][from_col] = 0;
 980         que_fin++;
 981         que_next_len = que_fin;
 982
 983         while ( que_fin > que_start ) {
 984                 row = que[que_start].row;
 985                 col = que[que_start].col;
 986                 que_start++;
 987
 988                 for ( int d = 0; d < 4; d++ ) {
 989                         int dr = dR[d];
 990                         int dc = dC[d];
 991 // scout moves NYI
 992                         int r = row + dr;
 993                         int c = col + dc;
 994
 995                         if ( IsOnBoard( r, c ) && path_length_to[r][c] == -1
 996                                                 && IsEmptySquare( storage, r, c ) ) {
 997                                 if ( suicide_ok
 998                                                                 ? !PossibilitiesCouldKillSafely( rank, (*dangers)[r][c] )
 999                                                                 : !PossibilitiesCouldKill( rank, (*dangers)[r][c] ) ) {
1000                                         path_length_to[r][c] = current_len + 1;
1001                                         if ( abs( to_row - r ) + abs( to_col - c ) == 1 ) {
1002                                                 *best_path = current_len + 1;
1003                                                 while ( current_len > 0 ) {
1004                                                         for ( int d = 0; d < 4; d++ ) {
1005                                                                 int backr = r + dR[d];
1006                                                                 int backc = c + dC[d];
1007
1008                                                                 if ( path_length_to[backr][backc] == current_len ) {
1009                                                                         r = backr;
1010                                                                         c = backc;
1011                                                                         break;
1012                                                                 }
1013                                                         }
1014                                                         current_len--;
1015                                                 }
1016                                                 *first_row = r;
1017                                                 *first_col = c;
1018                                                 return true;
1019                                         }
1020                                         que[que_fin].row = r;
1021                                         que[que_fin].col = c;
1022                                         que_fin++;
1023                                 } else {
1024                                         path_length_to[r][c] = 1000; // Cant go here
1025                                 }
1026                         }
1027                 }
1028
1029                 if ( que_start == que_next_len ) {
1030                         que_next_len = que_fin;
1031                         current_len++;
1032                 }
1033         }
1034
1035         return false;
1036 }
1037
1038 static UInt32 CalcBoardCRC( StoragePtr storage, int from_row, int from_col, int to_row, int to_col )
1039 {
1040         Assert( !IsOnBoard( from_row, from_col ) || IsOurPiece( storage, from_row, from_col ), "!IsOnBoard( from_row, from_col ) || IsOurPiece( storage, from_row, from_col )" );
1041         Assert( !IsOnBoard( to_row, to_col ) || IsEmptySquare( storage, to_row, to_col ), "!IsOnBoard( to_row, to_col ) || IsEmptySquare( storage, to_row, to_col )" );
1042
1043         UInt32 result = 0;
1044
1045         int row, col;
1046         int rankish;
1047
1048         for ( row = 0; row < kBoardSize; row++ ) {
1049                 for( col = 0; col < kBoardSize; col++ ) {
1050                         if ( row == from_row && col == from_col ) {
1051                                 rankish = 0;
1052                         } else if ( row == to_row && col == to_col ) {
1053                                 rankish = storage->board[from_row][from_col].rank;
1054                         } else if ( IsEmptySquare( storage, row, col ) || IsWaterSquare( storage, row, col ) ) {
1055                                 rankish = 0;
1056                         } else if ( IsOurPiece( storage, row, col ) ) {
1057                                 rankish = storage->board[row][col].rank;
1058                         } else {
1059                                 rankish = storage->board[row][col].rank + kAddForRankish;
1060                         }
1061                         result += rankish; // Hmm, not a very good CRC
1062                         result = result * 11 + (result >> 25);
1063                 }
1064         }
1065
1066         return result;
1067 }
1068
1069 static Boolean OKMove( StoragePtr storage, int from_row, int from_col, int to_row, int to_col )
1070 {
1071         if ( IsTheirPiece( storage, to_row, to_col ) ) {
1072                 return true;
1073         }
1074
1075         UInt32 crc = CalcBoardCRC( storage, from_row, from_col, to_row, to_col );
1076         for ( UInt32 i = 0; i < storage->repeated_board_count; i++ ) {
1077                 if ( crc == storage->repeated_board[i] ) {
1078                         return false;
1079                 }
1080         }
1081         return true;
1082 }
1083
1084 static void AppendRepeatedBoard( StoragePtr storage )
1085 {
1086         UInt32 crc = CalcBoardCRC( storage, -1, -1, -1, -1 );
1087
1088         if ( storage->repeated_board_count == kRepeatedBoards ) {
1089                 storage->repeated_board_count--;
1090                 memcpy( &storage->repeated_board[0], &storage->repeated_board[1], storage->repeated_board_count * sizeof(storage->repeated_board[0]) );
1091         }
1092         storage->repeated_board[storage->repeated_board_count++] = crc;
1093 }
1094
1095 #if DEBUG_RULES
1096         #define RETURN( x ) Log( x ); return
1097 #else
1098         #define RETURN( x ) return
1099 #endif
1100
1101 static void FigureOutOurMove( StoragePtr storage, PiecePosition *moveFrom, PiecePosition *moveTo )
1102 {
1103         int ourRow, ourCol, theirRow, theirCol, row, col, runRow, runCol;
1104         int rowFirst = storage->playerColor == kRed ? 0 : kBoardSize - 1;
1105         int rowLast = storage->playerColor == kRed ? kBoardSize - 1 : 0;
1106         int rowAdd = storage->playerColor == kRed ? 1 : -1;
1107         int bestUnknowns;
1108         int bestPath;
1109         int thisPath;
1110
1111         UpdateDangerPossibilities( storage );
1112
1113 // USE SPY
1114         if ( FindPiece( storage, storage->theirColor, kMarshall, &theirRow, &theirCol )
1115                         && FindPiece( storage, storage->playerColor, kSpy, &ourRow, &ourCol )
1116                         && abs( theirRow - ourRow ) + abs( theirCol - ourCol ) == 1 ) {
1117                 moveFrom->row = ourRow;
1118                 moveFrom->col = ourCol;
1119                 moveTo->row = theirRow;
1120                 moveTo->col = theirCol;
1121                 RETURN( "USE SPY" );
1122         }
1123
1124 // DEFEND AGAINST SPY
1125         if (storage->their_pieces[kSpy] > 0) {
1126                 if ( FindPiece( storage, storage->playerColor, kMarshall, &ourRow, &ourCol ) ) {
1127                         int unknowns = CountAdjacentUnknownPieces( storage, storage->theirColor, ourRow, ourCol );
1128
1129                         if ( unknowns ) {
1130                                 int base_index = 0;
1131                                 Boolean canrun = FindSafeSquare( storage, ourRow, ourCol, &runRow, &runCol );
1132                                 if ( !canrun ) {
1133                                         base_index += 16;
1134                                 }
1135                                 if ( unknowns > 1 ) {
1136                                         base_index += 8;
1137                                 }
1138
1139                                 for ( int d = 0; d < 4; d++ ) {
1140                                         int r = ourRow + dR[d];
1141                                         int c = ourCol + dC[d];
1142                                         int otherRow, otherCol;
1143
1144                                         if ( IsOnBoard( r, c )
1145                                                         && IsTheirPiece( storage, r, c )
1146                                                         && IsUnknownPiece( storage, r, c ) ) {
1147                                                 int index = base_index;
1148                                                 if ( LowlyCanAttack( storage, r, c, &otherRow, &otherCol ) ) {
1149                                                         index += 4;
1150                                                 }
1151                                                 if ( CountAdjacentUnknownPieces( storage, storage->theirColor, r, c ) > 0 ) {
1152                                                         index += 2;
1153                                                 }
1154                                                 if ( IsMovedPiece( storage, r, c ) ) {
1155                                                         index += 1;
1156                                                 }
1157
1158                                                 if ( defend_spy_table[index] == 'A' ) { // Attack
1159                                                         moveFrom->row = ourRow;
1160                                                         moveFrom->col = ourCol;
1161                                                         moveTo->row = r;
1162                                                         moveTo->col = c;
1163                                                         RETURN( "DEFEND AGAINST SPY 1" );
1164                                                 } else if ( defend_spy_table[index] == 'O' ) { // Attack
1165                                                         moveFrom->row = otherRow;
1166                                                         moveFrom->col = otherCol;
1167                                                         moveTo->row = r;
1168                                                         moveTo->col = c;
1169                                                         RETURN( "DEFEND AGAINST SPY 2" );
1170                                                 }
1171                                         }
1172                                 }
1173
1174                                 if ( canrun && OKMove( storage, ourRow, ourCol, runRow, runCol ) ) {
1175                                         moveFrom->row = ourRow;
1176                                         moveFrom->col = ourCol;
1177                                         moveTo->row = runRow;
1178                                         moveTo->col = runCol;
1179                                         RETURN( "DEFEND AGAINST SPY 3" );
1180                                 }
1181                                 // Give up!  Next ruleÉ
1182                         }
1183                 }
1184         }
1185
1186 // ATTACK WEAKER
1187         for ( row = rowFirst; 0 <= row && row < kBoardSize; row += rowAdd ) {
1188                 for( col = 0; col < kBoardSize; col++ ) {
1189                         if ( IsTheirPiece( storage, row, col ) ) {
1190                                 UInt32 enemy = storage->board[row][col].possibilities;
1191                                 UInt32 danger = GetDangerPossibilities( storage, row, col );
1192
1193                                 int bestDir = -1;
1194                                 Boolean isBestRevealed = true;
1195                                 PieceRank bestRank = kUnknown;
1196
1197                                 for ( int d = 0; d < 4; d++ ) {
1198                                         int r = row + dR[d];
1199                                         int c = col + dC[d];
1200
1201                                         if ( IsOnBoard( r, c ) && IsOurPiece( storage, r, c ) ) {
1202                                                 if ( !PossibilitiesCouldKill( storage->board[r][c].rank, danger ) ) {
1203                                                         if ( WillKillPossibilities( storage->board[r][c].rank, enemy ) ) {
1204                                                                 Boolean thisRevealed = IsRevealedPiece( storage, r, c );
1205                                                                 if ( isBestRevealed || !thisRevealed ) {
1206                                                                         if ( bestDir == -1 || (storage->board[r][c].rank > bestRank) ) {
1207                                                                                 bestDir = d;
1208                                                                                 bestRank = storage->board[r][c].rank;
1209                                                                                 isBestRevealed = thisRevealed;
1210                                                                         }
1211                                                                 }
1212                                                         }
1213                                                 }
1214                                         }
1215                                 }
1216                                 if ( bestDir != -1 ) {
1217                                         moveFrom->row = row + dR[bestDir];
1218                                         moveFrom->col = col + dC[bestDir];
1219                                         moveTo->row = row;
1220                                         moveTo->col = col;
1221                                         RETURN( "ATTACK WEAKER" );
1222                                 }
1223                         }
1224                 }
1225         }
1226
1227 // EXPLORE ATTACK
1228         for ( int rnk = kScout; rnk >= kMarshall; rnk-- ) {
1229                 PieceRank rank = (PieceRank) rnk;
1230                 if ( IsLowlyRank( rank ) ) {
1231
1232                         for ( row = rowLast; 0 <= row && row < kBoardSize; row -= rowAdd ) {
1233                                 for( col = 0; col < kBoardSize; col++ ) {
1234                                         if ( IsOurPiece( storage, row, col )
1235                                                         && IsRankPiece( storage, row, col, rank ) ) {
1236
1237                                                 for ( int d = 0; d < 4; d++ ) {
1238                                                         int r = row + dR[d];
1239                                                         int c = col + dC[d];
1240
1241                                                         if ( IsOnBoard( r, c )
1242                                                                                 && IsTheirPiece( storage, r, c )
1243                                                                                 && IsRankPiece( storage, r, c, kUnknown ) ) {
1244                                                                 moveFrom->row = row;
1245                                                                 moveFrom->col = col;
1246                                                                 moveTo->row = r;
1247                                                                 moveTo->col = c;
1248                                                                 RETURN( "EXPLORE ATTACK" );
1249                                                         }
1250                                                 }
1251                                         }
1252                                 }
1253                         }
1254
1255                 }
1256         }
1257
1258 // RETREAT
1259         for ( row = rowLast; 0 <= row && row < kBoardSize; row -= rowAdd ) {
1260                 for( col = 0; col < kBoardSize; col++ ) {
1261                         if ( IsOurPiece( storage, row, col )
1262                                         && IsMovedPiece( storage, row, col ) ) {
1263
1264                                 for ( int d = 0; d < 4; d++ ) {
1265                                         int r = row + dR[d];
1266                                         int c = col + dC[d];
1267
1268                                         if ( IsOnBoard( r, c )
1269                                                                 && IsTheirPiece( storage, r, c )
1270                                                                 && WillPossibilitiesKill( storage->board[r][c].possibilities, storage->board[row][col].rank ) ) {
1271                                                 bestPath = 1000;
1272                                                 for ( int to_row = rowLast; 0 <= to_row && to_row < kBoardSize; to_row -= rowAdd ) {
1273                                                         for( int to_col = 0; to_col < kBoardSize; to_col++ ) {
1274                                                                 thisPath = bestPath;
1275                                                                 if ( IsTheirPiece( storage, to_row, to_col )
1276                                                                                         && (IsRankPiece( storage, to_row, to_col, kUnknown )
1277                                                                                                                 || WillKillPossibilities( storage->board[row][col].rank, storage->board[to_row][to_col].possibilities ))
1278                                                                                         && FindSafePath( storage, false, true, row, col, to_row, to_col, &thisPath, &runRow, &runCol )
1279                                                                                         && OKMove( storage, row, col, runRow, runCol ) ) {
1280                                                                         bestPath = thisPath;
1281                                                                         moveFrom->row = row;
1282                                                                         moveFrom->col = col;
1283                                                                         moveTo->row = runRow;
1284                                                                         moveTo->col = runCol;
1285                                                                 }
1286                                                         }
1287                                                 }
1288                                                 if ( bestPath < 1000 ) {
1289                                                         RETURN( "RETREAT" );
1290                                                 }
1291                                         }
1292                                 }
1293                         }
1294                 }
1295         }
1296
1297 // SCOUT
1298         bestUnknowns = 0;
1299
1300         for ( row = rowLast; 0 <= row && row < kBoardSize; row -= rowAdd ) {
1301                 for( col = 0; col < kBoardSize; col++ ) {
1302                         if ( IsOurPiece( storage, row, col )
1303                                                 && IsRankPiece( storage, row, col, kScout ) ) {
1304                                 for ( int d = 0; d < 4; d++ ) {
1305                                         int r = row + dR[d];
1306                                         int c = col + dC[d];
1307
1308                                         while ( IsOnBoard( r, c ) && IsEmptySquare( storage, r, c ) ) {
1309
1310                                                 int knowns, unknowns;
1311                                                 CountEnemies( storage, r, c, &knowns, &unknowns );
1312                                                 if ( knowns == 0 && unknowns > bestUnknowns && OKMove( storage, row, col, r, c ) ) {
1313                                                         bestUnknowns = unknowns;
1314                                                         ourRow = row;
1315                                                         ourCol = col;
1316                                                         runRow = r;
1317                                                         runCol = c;
1318                                                 }
1319                                                 r += dR[d];
1320                                                 c += dC[d];
1321                                         }
1322                                 }
1323                         }
1324                 }
1325         }
1326
1327         if ( bestUnknowns > 0 ) {
1328                 moveFrom->row = ourRow;
1329                 moveFrom->col = ourCol;
1330                 moveTo->row = runRow;
1331                 moveTo->col = runCol;
1332                 RETURN( "SCOUT" );
1333         }
1334
1335 // ATTACK DISTANT
1336
1337         bestPath = 1000;
1338
1339         for ( row = rowFirst; 0 <= row && row < kBoardSize; row += rowAdd ) {
1340                 for( col = 0; col < kBoardSize; col++ ) {
1341                         if ( IsTheirPiece( storage, row, col ) ) {
1342                                 UInt32 possibilities = storage->board[row][col].possibilities;
1343                                 UInt32 danger = GetDangerPossibilities( storage, row, col );
1344
1345                                 if ( (possibilities & ((1 << kBomb) | (1 << kMarshall))) != ((1 << kBomb) | (1 << kMarshall)) ) {
1346                                         for ( int r = rowFirst; 0 <= r && r < kBoardSize; r += rowAdd ) {
1347                                                 for( int c = 0; c < kBoardSize; c++ ) {
1348                                                         if ( IsOurPiece( storage, r, c ) ) {
1349                                                                 if ( WillKillPossibilities( storage->board[r][c].rank, possibilities ) ) {
1350                                                                         if ( storage->board[r][c].rank >= kCaptain || !PossibilitiesCouldKill( storage->board[r][c].rank, danger ) ) {
1351                                                                                 thisPath = bestPath;
1352                                                                                 if ( FindSafePath( storage, true, false, r, c, row, col, &thisPath, &runRow, &runCol ) ) {
1353                                                                                         if ( OKMove( storage, r, c, runRow, runCol ) ) {
1354                                                                                                 bestPath = thisPath;
1355                                                                                                 moveFrom->row = r;
1356                                                                                                 moveFrom->col = c;
1357                                                                                                 moveTo->row = runRow;
1358                                                                                                 moveTo->col = runCol;
1359                                                                                         }
1360                                                                                 }
1361                                                                         }
1362                                                                 }
1363                                                         }
1364                                                 }
1365                                         }
1366                                 }
1367
1368                         }
1369                 }
1370         }
1371
1372         if ( bestPath < 1000 ) {
1373                 RETURN( "ATTACK DISTANT" );
1374         }
1375
1376 // EXPLORE DISTANT
1377
1378         bestPath = 1000;
1379
1380         for ( row = rowFirst; 0 <= row && row < kBoardSize; row += rowAdd ) {
1381                 for( col = 0; col < kBoardSize; col++ ) {
1382                         if ( IsTheirPiece( storage, row, col ) && storage->board[row][col].rank == kUnknown ) {
1383
1384                                 for ( int r = rowFirst; 0 <= r && r < kBoardSize; r += rowAdd ) {
1385                                         for( int c = 0; c < kBoardSize; c++ ) {
1386                                                 if ( IsOurPiece( storage, r, c ) && IsLowlyPiece( storage, r, c ) ) {
1387                                                         thisPath = bestPath;
1388                                                         if ( FindSafePath( storage, false, true, r, c, row, col, &thisPath, &runRow, &runCol ) ) {
1389                                                                 if ( OKMove( storage, r, c, runRow, runCol ) ) {
1390                                                                         bestPath = thisPath;
1391                                                                         moveFrom->row = r;
1392                                                                         moveFrom->col = c;
1393                                                                         moveTo->row = runRow;
1394                                                                         moveTo->col = runCol;
1395                                                                 }
1396                                                         }
1397                                                 }
1398                                         }
1399                                 }
1400
1401                         }
1402                 }
1403         }
1404
1405         if ( bestPath < 1000 ) {
1406                 RETURN( "EXPLORE DISTANT" );
1407         }
1408
1409 // ATTACK KNOWN WITH SAME DISTANT
1410
1411         bestPath = 1000;
1412
1413         for ( row = rowFirst; 0 <= row && row < kBoardSize; row += rowAdd ) {
1414                 for( col = 0; col < kBoardSize; col++ ) {
1415                         if ( IsTheirPiece( storage, row, col ) ) {
1416                                 UInt32 possibilities = storage->board[row][col].possibilities;
1417
1418                                 if ( (possibilities & ((1 << kBomb) | (1 << kMarshall))) != ((1 << kBomb) | (1 << kMarshall)) ) {
1419                                         for ( int r = rowFirst; 0 <= r && r < kBoardSize; r += rowAdd ) {
1420                                                 for( int c = 0; c < kBoardSize; c++ ) {
1421                                                         if ( IsOurPiece( storage, r, c ) ) {
1422                                                                 if ( WillKillOrSuicidePossibilities( storage->board[r][c].rank, possibilities ) ) {
1423                                                                         thisPath = bestPath;
1424                                                                         if ( FindSafePath( storage, true, true, r, c, row, col, &thisPath, &runRow, &runCol ) ) {
1425                                                                                 if ( OKMove( storage, r, c, runRow, runCol ) ) {
1426                                                                                         bestPath = thisPath;
1427                                                                                         moveFrom->row = r;
1428                                                                                         moveFrom->col = c;
1429                                                                                         moveTo->row = runRow;
1430                                                                                         moveTo->col = runCol;
1431                                                                                 }
1432                                                                         }
1433                                                                 }
1434                                                         }
1435                                                 }
1436                                         }
1437                                 }
1438
1439                         }
1440                 }
1441         }
1442
1443         if ( bestPath < 1000 ) {
1444                 RETURN( "ATTACK KNOWN WITH SAME DISTANT" );
1445         }
1446
1447 // FIND FLAG
1448 // NYI
1449
1450 // MOVE FORWARD
1451
1452         for ( row = rowLast; 0 <= row && row < kBoardSize; row -= rowAdd ) {
1453                 for( col = 0; col < kBoardSize; col++ ) {
1454                         if ( IsOurPiece( storage, row, col ) ) {
1455                                 PieceRank rank = storage->board[row][col].rank;
1456                                 if ( rank != kBomb && rank != kFlag ) {
1457                                         int r = row + rowAdd;
1458                                         if ( IsOnBoard( r, col ) && !IsOurPiece( storage, r, col ) && OKMove( storage, row, col, r, col ) ) {
1459                                                 moveFrom->row = row;
1460                                                 moveFrom->col = col;
1461                                                 moveTo->row = r;
1462                                                 moveTo->col = col;
1463                                                 RETURN( "MOVE FORWARD" );
1464                                         }
1465                                 }
1466                         }
1467                 }
1468         }
1469
1470 // MOVE
1471
1472         for ( row = rowLast; 0 <= row && row < kBoardSize; row -= rowAdd ) {
1473                 for( col = 0; col < kBoardSize; col++ ) {
1474                         if ( IsOurPiece( storage, row, col ) ) {
1475                                 PieceRank rank = storage->board[row][col].rank;
1476                                 if ( rank != kBomb && rank != kFlag ) {
1477
1478                                         for ( int d = 0; d < 4; d++ ) {
1479                                                 int r = row + dR[d];
1480                                                 int c = col + dC[d];
1481
1482                                                 if ( IsOnBoard( r, c ) && !IsOurPiece( storage, r, c ) && OKMove( storage, row, col, r, c ) ) {
1483                                                         moveFrom->row = row;
1484                                                         moveFrom->col = col;
1485                                                         moveTo->row = r;
1486                                                         moveTo->col = c;
1487                                                         RETURN( "MOVE" );
1488                                                 }
1489                                         }
1490                                 }
1491                         }
1492                 }
1493         }
1494
1495 // RESIGN
1496         moveFrom->row = -1;
1497         moveFrom->col = -1;
1498         moveTo->row = -1;
1499         moveTo->col = -1;
1500         RETURN( "RESIGN" );
1501
1502 }
1503
1504 static void HandleOurMove( StoragePtr storage, PiecePosition moveFrom, PiecePosition moveTo, const MoveResult moveResult )
1505 {
1506         Boolean moveStrike;
1507
1508         if ( IsOnBoard( moveTo.row, moveTo.col ) ) {
1509                 moveStrike = storage->board[moveTo.row][moveTo.col].color != kNoColor;
1510         } else {
1511                 moveStrike = false;
1512         }
1513
1514         if ( moveResult.victory ) { // We Win! :-)
1515                 storage->victory = true;
1516         } else if ( !moveResult.legalMove ) { // We Lose! :-(
1517         } else {
1518                 if ( moveStrike ) {
1519                         storage->repeated_board_count = 0;
1520                         Learn( storage, true, moveTo.row, moveTo.col, moveResult.rankOfDefender.thePieceRank );
1521                         Learn( storage, false, moveFrom.row, moveFrom.col, moveResult.rankOfAttacker.thePieceRank );
1522
1523                         if ( moveResult.attackerRemoved && moveResult.defenderRemoved ) {
1524                                 storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
1525                                 storage->board[moveTo.row][moveTo.col] = storage->blankSquare;
1526                         } else if ( moveResult.attackerRemoved ) {
1527 //                              if ( storage->board[moveTo.row][moveTo.col].rank == kBomb ) {
1528                                         storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
1529 //                              } else {
1530 //                                      storage->board[moveFrom.row][moveFrom.col] = storage->board[moveTo.row][moveTo.col];
1531 //                                      storage->board[moveTo.row][moveTo.col] = storage->blankSquare;
1532 //                              }
1533                         } else {
1534                                 Assert( moveResult.defenderRemoved, "moveResult.defenderRemoved" );
1535                                 storage->board[moveTo.row][moveTo.col] = storage->board[moveFrom.row][moveFrom.col];
1536                                 storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
1537                         }
1538
1539                 } else {
1540                         if ( abs( moveTo.row - moveFrom.row ) + abs( moveTo.col - moveFrom.col ) > 1 ) {
1541                                 Assert( storage->board[moveFrom.row][moveFrom.col].rank == kScout, "storage->board[moveFrom.row][moveFrom.col].rank == kScout" );
1542                                 Learn( storage, false, moveFrom.row, moveFrom.col, kScout );
1543                         } else {
1544                                 Learn( storage, false, moveFrom.row, moveFrom.col, (PieceRank)kMoved );
1545                         }
1546                         storage->board[moveTo.row][moveTo.col] = storage->board[moveFrom.row][moveFrom.col];
1547                         storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
1548                 }
1549                 AppendRepeatedBoard( storage );
1550         }
1551
1552         AssertValidBoard( storage );
1553 }
1554
1555 /*
1556 Boolean MakeAMove(
1557   StoragePtr storage,          / * 1MB of storage from PositionPieces * /
1558   PlayerColor playerColor,    / * you play red or blue, with red playing first * /
1559   GetOpponentMove *GetMove,  / * callback used to find about opponents last move * /
1560   ReportYourMove *ReportMove   / * callback used to make a move * /
1561 )
1562 {
1563         if ( storage->do_getmove ) {
1564                 HandleTheirMove( storage, *GetMove );
1565         }
1566         storage->do_getmove = true;
1567
1568         HandleOurMove( storage,  *ReportMove );
1569
1570         return storage->victory;
1571 }
1572 */
1573
1574 // Code to map UCC Challenge to MacTech Challenge
1575
1576 static PlayerColor ReadPlayerLine()
1577 {
1578         HelperReadLine();
1579
1580         std::string colourStr = gLineBuffer[0];
1581
1582         if ( colourStr == "RED" ) {
1583                 return kRed;
1584         } else if ( colourStr == "BLUE" ) {
1585                 return kBlue;
1586         } else {
1587                 Log( string("What color? ") + colourStr );
1588                 exit( 99 );
1589         }
1590 }
1591
1592 static PlayerColor OtherPlayerColor( PlayerColor player )
1593 {
1594         return (player == kRed) ? kBlue : kRed;
1595 }
1596
1597 int main(int argc, char ** argv)
1598 {
1599         srand(time(NULL));
1600         cin.rdbuf()->pubsetbuf(NULL, 0);
1601         cout.rdbuf()->pubsetbuf(NULL, 0);
1602         cout.setf(std::ios::unitbuf);
1603 #if SAVE_OUTPUT
1604         gOutputFile.open( (string("/tmp/peternlewis-output-") + to_string(time( NULL )) + "-" + to_string(rand() & 0xFFFF) + ".log").c_str() );
1605         gOutputFile.setf(std::ios::unitbuf);
1606 #endif
1607
1608         Storage storage;
1609         Board board;
1610
1611         PlayerColor player = ReadPlayerLine();
1612
1613         PositionPieces( &storage, player, &board );
1614         if ( player == kRed ) {
1615                 for ( int r = 0; r <= 3; r++ ) {
1616                         string line;
1617                         for ( int c = 0; c < kBoardSize; c++ ) {
1618                                 line += gPieceCharacters[board[r][c].thePieceRank];
1619                         }
1620                         Output( line );
1621                 }
1622         } else {
1623                 for ( int r = kBoardSize - 4; r < kBoardSize; r++ ) {
1624                         string line;
1625                         for ( int c = 0; c < kBoardSize; c++ ) {
1626                                 line += gPieceCharacters[board[r][c].thePieceRank];
1627                         }
1628                         Output( line );
1629                 }
1630         }
1631
1632         bool expectStart = (player == kRed);
1633         while ( 1 ) {
1634                 Debug( "LOOP" );
1635                 if ( expectStart ) {
1636                         HelperReadLine();
1637                         expectStart = false;
1638                 } else {
1639                         PiecePosition from;
1640                         PiecePosition to;
1641                         MoveOutcome result;
1642                         PieceRank attacker;
1643                         PieceRank defender;
1644                         HelperReadMove( &storage, from, to, result, attacker, defender );
1645                         Debug( to_string(from.col) + "," + to_string(from.row) + " -> " + to_string(to.col) + "," + to_string(to.row) );
1646                         MoveResult moveResult;
1647                         moveResult.rankOfAttacker.thePieceRank = attacker;
1648                         moveResult.rankOfAttacker.thePieceColor = OtherPlayerColor( player );
1649                         moveResult.rankOfDefender.thePieceRank = defender;
1650                         moveResult.rankOfDefender.thePieceColor = player;
1651                         moveResult.attackerRemoved = (result == kMR_Dies) || (result == kMR_BothDie);
1652                         moveResult.defenderRemoved = (result == kMR_Kills) || (result == kMR_BothDie);
1653                         moveResult.victory = false;
1654                         moveResult.legalMove = true;
1655                         HandleTheirMove( &storage, from, to, (result != kMR_OK), moveResult );
1656                 }
1657                 HelperJunkLine( kBoardSize );
1658                 DumpBoard( &storage );
1659
1660                 PiecePosition moveFrom;
1661                 PiecePosition moveTo;
1662
1663                 FigureOutOurMove( &storage, &moveFrom, &moveTo );
1664                 Debug( to_string(moveFrom.col) + ',' + to_string(moveFrom.row) + " -> " + to_string(moveTo.col) + ',' + to_string(moveTo.row) );
1665                 if ( moveFrom.row < 0 ) {
1666                         Output( "SURRENDER" );
1667                         exit(EXIT_SUCCESS);
1668                 }
1669                 std::string dir;
1670                 int move;
1671                 if ( moveTo.col > moveFrom.col ) {
1672                         dir = "RIGHT";
1673                         move = moveTo.col - moveFrom.col;
1674                 } else if ( moveTo.col < moveFrom.col ) {
1675                         dir = "LEFT";
1676                         move = moveFrom.col - moveTo.col;
1677                 } else if ( moveTo.row < moveFrom.row ) {
1678                         dir = "UP";
1679                         move = moveFrom.row - moveTo.row;
1680                 } else if ( moveTo.row > moveFrom.row ) {
1681                         dir = "DOWN";
1682                         move = moveTo.row - moveFrom.row;
1683                 }
1684                 Output( to_string(moveFrom.col) + ' ' + to_string(moveFrom.row) + ' ' + dir + ' ' + to_string(move) );
1685                 {
1686                         PiecePosition from;
1687                         PiecePosition to;
1688                         MoveOutcome result;
1689                         PieceRank attacker;
1690                         PieceRank defender;
1691                         HelperReadMove( &storage, from, to, result, attacker, defender );
1692                         MoveResult moveResult;
1693                         moveResult.rankOfAttacker.thePieceRank = attacker;
1694                         moveResult.rankOfAttacker.thePieceColor = player;
1695                         moveResult.rankOfDefender.thePieceRank = defender;
1696                         moveResult.rankOfDefender.thePieceColor = OtherPlayerColor( player );
1697                         moveResult.attackerRemoved = (result == kMR_Dies) || (result == kMR_BothDie);
1698                         moveResult.defenderRemoved = (result == kMR_Kills) || (result == kMR_BothDie);
1699                         moveResult.victory = false;
1700                         moveResult.legalMove = true;
1701                         HandleOurMove( &storage, from, to, moveResult );
1702                         DumpBoard( &storage );
1703                 }
1704         }
1705
1706         exit(EXIT_SUCCESS);
1707         return 0;
1708 }