18 using namespace std; // two of two, yay!
21 typedef unsigned long UInt32;
23 #include "peternlewis.h"
25 const char *gPieceCharacters = kPieceCharacters;
31 inline std::string to_string (const T& t)
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>
46 Only time we spend thinking is counted against out 10 seconds (not time in GetMove/ReportMove)
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.
55 At each turn, we simply apply a sequence of actions (listed below) and take the first action that works.
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)
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!).
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.
70 It actually plays a half decent game! The end game is not as good as I'd like, but time is up!
75 If our spy is next to their 1, kill it
78 if we have seen the spy, ignore this case
80 If an unknown piece is next to the 1, then
81 run, attack, have another piece attack, or ignore depending on a table
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
88 If a 6,7,9 is next to an unknown piece, attack it
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)
96 Try advancing scouts rapidly
99 If a known piece is distant, but a clear path leads a slightly better piece towards it, advance the better piece
103 Try exploring (advance lowly pieces towards unknown pieces)
105 ATTACK KNOWN WITH SAME DISTANT
106 If a known piece can be attacked by a known identical piece, attack it
109 When few unmoved pieces remain, start assuming they are bombs/flags
112 Move any piece we can forward
115 Move any piece we can
121 static void Output( string what )
124 gOutputFile << "<< " << what << "\n";
126 cout << what << "\n";
129 static void SaveInput( string what )
132 gOutputFile << ">> " << what << "\n";
136 static void Log( string what )
139 gOutputFile << what << "\n";
141 cerr << what << "\n";
144 static void Debug( string what )
147 gOutputFile << what << "\n";
150 cerr << what << "\n";
154 static void Assert( short must, string what )
158 Log( string("Assert failed! ") + what + "\n" );
163 std::vector<string> gLineBuffer;
166 kNoNothing = 0x00001FFE,
167 kStationaryBits = ((1 << kBomb) | (1 << kFlag))
171 kRepeatedBoards = 1000
174 typedef struct Square {
177 UInt32 possibilities;
180 typedef Square OurBoard[kBoardSize][kBoardSize];
182 typedef int Counts[kFlag+1];
184 typedef UInt32 BoardPossibilities[kBoardSize][kBoardSize];
186 typedef struct Storage {
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;
201 static void DumpBoard( StoragePtr storage )
204 Debug( "DumpBoard:" );
205 for ( int row = 0; row < kBoardSize; row++ ) {
207 for ( int col = 0; col < kBoardSize; col++ ) {
208 PieceRank rank = storage->board[row][col].rank;
209 if ( kMarshall <= rank && rank <= kFlag ) {
211 if ( storage->board[row][col].color == kRed ) {
219 line += gPieceCharacters[rank];
224 if ( rank == kEmpty ) {
226 } else if ( rank == kWater ) {
228 } else if ( rank == kMoved ) {
230 } else if ( rank == kAddForRankish ) {
232 } else if ( rank == kUnknown ) {
247 static PieceRank HelperGetRank(char token)
249 for ( unsigned int ii=0; ii <= strlen(gPieceCharacters); ++ii ) {
250 if (gPieceCharacters[ii] == token) {
251 return (PieceRank)(ii);
260 static int HelperTokenise(std::vector<string> & buffer, std::string & str, char split = ' ')
264 for (unsigned int x = 0; x < str.size(); ++x)
266 if (str[x] == split && token.size() > 0)
268 buffer.push_back(token);
274 if (token.size() > 0)
275 buffer.push_back(token);
276 return buffer.size();
280 * Convert string to integer
282 static int HelperInteger(std::string & fromStr)
284 stringstream s(fromStr);
291 * Read in a line from stdin
293 static void HelperReadLine()
295 std::string buffer = "";
296 for (char c = cin.get(); c != '\n' && cin.good(); c = cin.get()) {
300 HelperTokenise( gLineBuffer, buffer );
301 if ( gLineBuffer.size() == 0 ) {
302 Log( "No tokens on line" );
305 if ( gLineBuffer.size() == 0 ) {
306 Log( "No tokens on line" );
309 if ( gLineBuffer[0] == "QUIT" || gLineBuffer[0] == "NO_MOVE") {
310 Log( "QUIT token found" );
315 static void HelperJunkLine( int lines = 1 )
317 while ( lines > 0 ) {
330 static void HelperReadMove( StoragePtr storage, PiecePosition& from, PiecePosition& to, MoveOutcome& result, PieceRank& attacker, PieceRank& defender )
333 if ( gLineBuffer.size() < 4 ) {
334 Log( "Less than 4 tokens" );
337 from.col = HelperInteger( gLineBuffer[0] );
338 from.row = HelperInteger( gLineBuffer[1] );
339 int move = HelperInteger( gLineBuffer[3] );
341 gLineBuffer.insert( gLineBuffer.begin()+3, "1" );
345 std::string dir = gLineBuffer[2];
348 } else if (dir == "DOWN") {
350 } else if (dir == "LEFT") {
352 } else if (dir == "RIGHT") {
355 Log( "DIRECTION ERROR" );
360 std::string res = gLineBuffer[4];
361 if ( res == "ILLEGAL" ) {
362 Log( "Opponent (hopefully) made ILLEGAL move" );
364 } else if ( res == "OK" ) {
367 if ( res == "KILLS" ) {
369 } else if ( res == "DIES" ) {
371 } else if ( res == "BOTHDIE" ) {
372 result = kMR_BothDie;
374 Log( string("Unknown move result ") + res );
377 attacker = HelperGetRank( gLineBuffer[5][0] );
378 defender = HelperGetRank( gLineBuffer[6][0] );
385 static const char *board_setup_1[4] = { // 1 = Marshal, ..., 9 = Scout, : = Spy, ; = Bomb, < = Flag
392 static const char *bobs_board_setup[4] = { // 1 = Marshal, ..., 9 = Scout, : = Spy, ; = Bomb, < = Flag
401 static const char *board_setup[4] = { // 1 = Marshal, ..., 9 = Scout, : = Spy, ; = Bomb, < = Flag
409 static const char *start_piece_counts = "0112344458161";
411 static int dR[4] = { 1, 0, -1, 0 };
412 static int dC[4] = { 0, -1, 0, 1 };
416 static void AssertValidBoard( StoragePtr storage )
423 for ( piece = kMarshall; piece <= kFlag; piece++ ) {
424 count1 += storage->their_pieces[piece];
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 ) {
436 Assert( count1 == count2, "count1 == count2" );
441 #define AssertValidBoard( storage )
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 */
451 int row, our_row, their_row, col, board_col;
452 PlayerColor theirColor;
454 Boolean reverse = (time( NULL ) & 1) != 0;
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" );
461 for ( row = 0; row <= 3; row++ ) {
462 if ( playerColor == kRed ) {
464 their_row = (kBoardSize-1)-row;
468 our_row = (kBoardSize-1)-row;
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;
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;
480 storage->board[their_row][col].color = theirColor;
481 storage->board[their_row][col].rank = kUnknown;
482 storage->board[their_row][col].possibilities = kNoNothing;
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;
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';
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;
506 AssertValidBoard( storage );
509 static void Learn( StoragePtr storage, Boolean them, int row, int col, PieceRank rank )
512 PlayerColor thiscolor;
515 if ( storage->board[row][col].rank == kUnknown ) {
517 if ( rank == kMoved ) {
518 UInt32 possibilities = storage->board[row][col].possibilities;
519 possibilities &= ~kStationaryBits;
521 if ( (possibilities & (possibilities-1)) == 0 ) { // only one bit on! Now we know!
524 while ( (possibilities & 1) == 0 ) {
528 rank = (PieceRank)newrank;
530 storage->board[row][col].possibilities = possibilities;
534 if ( rank != kMoved ) {
535 storage->board[row][col].rank = rank;
536 storage->board[row][col].possibilities = (1 << rank);
538 gotall = --storage->their_pieces[rank] == 0;
540 gotall = --storage->our_pieces[rank] == 0;
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!
554 while ( (possibilities & 1) == 0 ) {
558 Learn( storage, them, r, c, (PieceRank)newrank );
566 Assert( rank == kMoved || storage->board[row][col].rank == rank, "rank == kMoved || storage->board[row][col].rank == rank" );
570 static void HandleTheirMove( StoragePtr storage, const PiecePosition moveFrom, const PiecePosition moveTo, Boolean moveStrike, const MoveResult moveResult )
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
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;
584 // storage->board[moveFrom.row][moveFrom.col] = storage->board[moveTo.row][moveTo.col];
585 // storage->board[moveTo.row][moveTo.col] = storage->blankSquare;
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;
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 );
598 Learn( storage, true, moveTo.row, moveTo.col, (PieceRank)kMoved );
602 AssertValidBoard( storage );
605 static Boolean FindPiece( StoragePtr storage, PlayerColor color, PieceRank rank, int *row, int *col )
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 ) {
622 static Boolean IsOnBoardWeak( int row, int col )
624 return 0 <= row && row < kBoardSize && 0 <= col && col < kBoardSize;
627 static Boolean IsOnBoard( int row, int col )
629 if ( 0 <= row && row < kBoardSize && 0 <= col && col < kBoardSize ) {
630 if ( row <= 3 || row >= 6 ) {
633 if ( col <= 1 || col >= 8 ) {
636 if ( 4 <= col && col <= 5 ) {
643 static Boolean IsColorPiece( StoragePtr storage, int row, int col, PlayerColor color )
645 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
646 return storage->board[row][col].color == color;
649 static Boolean IsOurPiece( StoragePtr storage, int row, int col )
651 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
652 return storage->board[row][col].color == storage->playerColor;
655 static Boolean IsTheirPiece( StoragePtr storage, int row, int col )
657 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
658 return storage->board[row][col].color == storage->theirColor;
661 static Boolean IsUnknownPiece( StoragePtr storage, int row, int col )
663 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
664 return storage->board[row][col].rank == kUnknown;
667 static Boolean IsRankPiece( StoragePtr storage, int row, int col, PieceRank rank )
669 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
670 return storage->board[row][col].rank == rank;
673 static Boolean IsEmptySquare( StoragePtr storage, int row, int col )
675 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
676 return storage->board[row][col].rank == (PieceRank)kEmpty;
679 static Boolean IsWaterSquare( StoragePtr storage, int row, int col )
681 Assert( IsOnBoardWeak( row, col ), "IsOnBoardWeak( row, col )" );
682 return storage->board[row][col].rank == (PieceRank)kWater;
685 static Boolean IsLowlyRank( PieceRank rank )
687 return kCaptain <= rank && rank <= kScout && rank != kMiner;
690 static Boolean IsLowlyPiece( StoragePtr storage, int row, int col )
692 Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
693 return IsLowlyRank( storage->board[row][col].rank );
696 static Boolean IsMovedPiece( StoragePtr storage, int row, int col )
698 Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
699 return (storage->board[row][col].possibilities & kStationaryBits) == 0;
702 static Boolean IsRevealedPiece( StoragePtr storage, int row, int col )
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 );
710 static int CountAdjacentUnknownPieces( StoragePtr storage, PlayerColor color, int row, int col )
715 for ( d = 0; d < 4; d++ ) {
719 if ( IsOnBoard( r, c ) && IsColorPiece( storage, r, c, color ) && IsUnknownPiece( storage, r, c ) ) {
727 static const char *defend_spy_table = "RARROAOORARRRARRXAXAOAOOXAXAXAXA";
728 // Run/Attack/Other/Nothing, >1 unknown:other:danger:moved
730 static Boolean LowlyCanAttack( StoragePtr storage, int row, int col, int *otherRow, int *otherCol )
732 for ( int d = 0; d < 4; d++ ) {
736 if ( IsOnBoard( r, c )
737 && IsOurPiece( storage, r, c )
738 && IsLowlyPiece( storage, r, c ) ) {
747 static void UpdateDangerPossibilities( StoragePtr storage )
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;
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;
764 if ( storage->board[row][col].rank != kUnknown ) {
765 known_possibilities = possibilities;
768 for ( int d = 0; d < 4; d++ ) {
772 if ( IsOnBoard( r, c ) ) {
773 storage->dangers[r][c] |= possibilities;
774 storage->known_dangers[r][c] |= known_possibilities;
784 static UInt32 GetDangerPossibilities( StoragePtr storage, int row, int col )
786 Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
787 return storage->dangers[row][col];
790 static Boolean PossibilitiesCouldKill( PieceRank rank, UInt32 possibilities )
792 if ( (possibilities & ~kStationaryBits) == 0 ) {
800 return (possibilities & (1 << kMiner)) != 0;
802 return (possibilities & ((1 << kMarshall) + (1<< kSpy))) != 0;
804 return (possibilities & ((1 << (rank+1)) - 1)) != 0;
808 static Boolean PossibilitiesCouldKillSafely( PieceRank rank, UInt32 possibilities )
810 if ( (possibilities & ~kStationaryBits) == 0 ) {
818 return (possibilities & (1 << kMiner)) != 0;
820 return (possibilities & ((1<< kSpy))) != 0;
822 return (possibilities & ((1 << rank) - 1)) != 0;
826 static Boolean WillKillPossibilities( PieceRank rank, UInt32 possibilities )
828 Assert( possibilities != 0, "possibilities != 0" );
836 return (possibilities & ~((1 << kScout) + (1 << kBomb) + (1 << kFlag))) == 0;
838 return (possibilities & ~(1 << kMarshall)) == 0;
840 return (possibilities & (((1 << (rank + 1)) - 1) + (1 << kBomb))) == 0;
844 static Boolean WillKillOrSuicidePossibilities( PieceRank rank, UInt32 possibilities )
846 Assert( possibilities != 0, "possibilities != 0" );
854 return (possibilities & ~((1 << kScout) + (1 << kMiner) + (1 << kBomb) + (1 << kFlag))) == 0;
856 return (possibilities & ~((1 << kMarshall) + (1 << kSpy))) == 0;
858 return (possibilities & (((1 << rank) - 1) + (1 << kBomb))) == 0;
862 static Boolean WillPossibilitiesKill( UInt32 possibilities, PieceRank rank )
864 Assert( possibilities != 0, "possibilities != 0" );
865 possibilities &= ~kStationaryBits;
866 if ( possibilities == 0 ) {
874 return possibilities == (1 << kMiner);
876 return (possibilities & ~((1 << (rank+1))-1)) == 0;
880 static Boolean FindSafeSquare( StoragePtr storage, int row, int col, int *safeRow, int *safeCol )
882 Assert( IsOnBoard( row, col ), "IsOnBoard( row, col )" );
884 PieceRank rank = storage->board[row][col].rank;
885 int doff = (storage->playerColor == kBlue ? 0 : 2); // Try backwards first
887 for ( int d = 0; d < 4; d++ ) {
888 int dr = dR[(d + doff) % 4];
889 int dc = dC[(d + doff) % 4];
893 while ( IsOnBoard( r, c ) && IsEmptySquare( storage, r, c ) ) {
894 if ( !PossibilitiesCouldKill( rank, GetDangerPossibilities( storage, r, c ) ) ) {
899 if ( rank != kScout ) {
909 static void CountEnemies( StoragePtr storage, int row, int col, int *knowns, int *unknowns )
914 for ( int d = 0; d < 4; d++ ) {
918 if ( IsOnBoard( r, c ) && IsTheirPiece( storage, r, c ) ) {
919 if ( storage->board[r][c].rank == kUnknown ) {
929 static Boolean CanRun( StoragePtr storage, int row, int col, int *runRow, int *runCol )
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];
935 if ( IsOnBoard( r, c ) && (storage->board[r][c].rank == kEmpty) ) {
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 )
947 Assert( IsOurPiece( storage, from_row, from_col ), "IsOurPiece( storage, from_row, from_col )" );
949 PieceRank rank = storage->board[from_row][from_col].rank;
950 BoardPossibilities *dangers = very_safe ? &storage->dangers : &storage->known_dangers;
952 if ( abs( from_row - to_row ) + abs( from_col - to_col ) > *best_path ) {
956 if ( abs( from_row - to_row ) + abs( from_col - to_col ) == 1 ) {
963 int path_length_to[kBoardSize][kBoardSize];
964 PiecePosition que[kBoardSize * kBoardSize];
967 int que_next_len = 0;
971 for ( row = 0; row < kBoardSize; row++ ) {
972 for( col = 0; col < kBoardSize; col++ ) {
973 path_length_to[row][col] = -1;
977 que[que_fin].row = from_row;
978 que[que_fin].col = from_col;
979 path_length_to[from_row][from_col] = 0;
981 que_next_len = que_fin;
983 while ( que_fin > que_start ) {
984 row = que[que_start].row;
985 col = que[que_start].col;
988 for ( int d = 0; d < 4; d++ ) {
995 if ( IsOnBoard( r, c ) && path_length_to[r][c] == -1
996 && IsEmptySquare( storage, r, c ) ) {
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];
1008 if ( path_length_to[backr][backc] == current_len ) {
1020 que[que_fin].row = r;
1021 que[que_fin].col = c;
1024 path_length_to[r][c] = 1000; // Cant go here
1029 if ( que_start == que_next_len ) {
1030 que_next_len = que_fin;
1038 static UInt32 CalcBoardCRC( StoragePtr storage, int from_row, int from_col, int to_row, int to_col )
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 )" );
1048 for ( row = 0; row < kBoardSize; row++ ) {
1049 for( col = 0; col < kBoardSize; col++ ) {
1050 if ( row == from_row && col == from_col ) {
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 ) ) {
1056 } else if ( IsOurPiece( storage, row, col ) ) {
1057 rankish = storage->board[row][col].rank;
1059 rankish = storage->board[row][col].rank + kAddForRankish;
1061 result += rankish; // Hmm, not a very good CRC
1062 result = result * 11 + (result >> 25);
1069 static Boolean OKMove( StoragePtr storage, int from_row, int from_col, int to_row, int to_col )
1071 if ( IsTheirPiece( storage, to_row, to_col ) ) {
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] ) {
1084 static void AppendRepeatedBoard( StoragePtr storage )
1086 UInt32 crc = CalcBoardCRC( storage, -1, -1, -1, -1 );
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]) );
1092 storage->repeated_board[storage->repeated_board_count++] = crc;
1096 #define RETURN( x ) Log( x ); return
1098 #define RETURN( x ) return
1101 static void FigureOutOurMove( StoragePtr storage, PiecePosition *moveFrom, PiecePosition *moveTo )
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;
1111 UpdateDangerPossibilities( storage );
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" );
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 );
1131 Boolean canrun = FindSafeSquare( storage, ourRow, ourCol, &runRow, &runCol );
1135 if ( unknowns > 1 ) {
1139 for ( int d = 0; d < 4; d++ ) {
1140 int r = ourRow + dR[d];
1141 int c = ourCol + dC[d];
1142 int otherRow, otherCol;
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 ) ) {
1151 if ( CountAdjacentUnknownPieces( storage, storage->theirColor, r, c ) > 0 ) {
1154 if ( IsMovedPiece( storage, r, c ) ) {
1158 if ( defend_spy_table[index] == 'A' ) { // Attack
1159 moveFrom->row = ourRow;
1160 moveFrom->col = ourCol;
1163 RETURN( "DEFEND AGAINST SPY 1" );
1164 } else if ( defend_spy_table[index] == 'O' ) { // Attack
1165 moveFrom->row = otherRow;
1166 moveFrom->col = otherCol;
1169 RETURN( "DEFEND AGAINST SPY 2" );
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" );
1181 // Give up! Next ruleÉ
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 );
1194 Boolean isBestRevealed = true;
1195 PieceRank bestRank = kUnknown;
1197 for ( int d = 0; d < 4; d++ ) {
1198 int r = row + dR[d];
1199 int c = col + dC[d];
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) ) {
1208 bestRank = storage->board[r][c].rank;
1209 isBestRevealed = thisRevealed;
1216 if ( bestDir != -1 ) {
1217 moveFrom->row = row + dR[bestDir];
1218 moveFrom->col = col + dC[bestDir];
1221 RETURN( "ATTACK WEAKER" );
1228 for ( int rnk = kScout; rnk >= kMarshall; rnk-- ) {
1229 PieceRank rank = (PieceRank) rnk;
1230 if ( IsLowlyRank( rank ) ) {
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 ) ) {
1237 for ( int d = 0; d < 4; d++ ) {
1238 int r = row + dR[d];
1239 int c = col + dC[d];
1241 if ( IsOnBoard( r, c )
1242 && IsTheirPiece( storage, r, c )
1243 && IsRankPiece( storage, r, c, kUnknown ) ) {
1244 moveFrom->row = row;
1245 moveFrom->col = col;
1248 RETURN( "EXPLORE ATTACK" );
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 ) ) {
1264 for ( int d = 0; d < 4; d++ ) {
1265 int r = row + dR[d];
1266 int c = col + dC[d];
1268 if ( IsOnBoard( r, c )
1269 && IsTheirPiece( storage, r, c )
1270 && WillPossibilitiesKill( storage->board[r][c].possibilities, storage->board[row][col].rank ) ) {
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;
1288 if ( bestPath < 1000 ) {
1289 RETURN( "RETREAT" );
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];
1308 while ( IsOnBoard( r, c ) && IsEmptySquare( storage, r, c ) ) {
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;
1327 if ( bestUnknowns > 0 ) {
1328 moveFrom->row = ourRow;
1329 moveFrom->col = ourCol;
1330 moveTo->row = runRow;
1331 moveTo->col = runCol;
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 );
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;
1357 moveTo->row = runRow;
1358 moveTo->col = runCol;
1372 if ( bestPath < 1000 ) {
1373 RETURN( "ATTACK DISTANT" );
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 ) {
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;
1393 moveTo->row = runRow;
1394 moveTo->col = runCol;
1405 if ( bestPath < 1000 ) {
1406 RETURN( "EXPLORE DISTANT" );
1409 // ATTACK KNOWN WITH SAME DISTANT
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;
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;
1429 moveTo->row = runRow;
1430 moveTo->col = runCol;
1443 if ( bestPath < 1000 ) {
1444 RETURN( "ATTACK KNOWN WITH SAME DISTANT" );
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;
1463 RETURN( "MOVE FORWARD" );
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 ) {
1478 for ( int d = 0; d < 4; d++ ) {
1479 int r = row + dR[d];
1480 int c = col + dC[d];
1482 if ( IsOnBoard( r, c ) && !IsOurPiece( storage, r, c ) && OKMove( storage, row, col, r, c ) ) {
1483 moveFrom->row = row;
1484 moveFrom->col = col;
1504 static void HandleOurMove( StoragePtr storage, PiecePosition moveFrom, PiecePosition moveTo, const MoveResult moveResult )
1508 if ( IsOnBoard( moveTo.row, moveTo.col ) ) {
1509 moveStrike = storage->board[moveTo.row][moveTo.col].color != kNoColor;
1514 if ( moveResult.victory ) { // We Win! :-)
1515 storage->victory = true;
1516 } else if ( !moveResult.legalMove ) { // We Lose! :-(
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 );
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;
1530 // storage->board[moveFrom.row][moveFrom.col] = storage->board[moveTo.row][moveTo.col];
1531 // storage->board[moveTo.row][moveTo.col] = storage->blankSquare;
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;
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 );
1544 Learn( storage, false, moveFrom.row, moveFrom.col, (PieceRank)kMoved );
1546 storage->board[moveTo.row][moveTo.col] = storage->board[moveFrom.row][moveFrom.col];
1547 storage->board[moveFrom.row][moveFrom.col] = storage->blankSquare;
1549 AppendRepeatedBoard( storage );
1552 AssertValidBoard( storage );
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 * /
1563 if ( storage->do_getmove ) {
1564 HandleTheirMove( storage, *GetMove );
1566 storage->do_getmove = true;
1568 HandleOurMove( storage, *ReportMove );
1570 return storage->victory;
1574 // Code to map UCC Challenge to MacTech Challenge
1576 static PlayerColor ReadPlayerLine()
1580 std::string colourStr = gLineBuffer[0];
1582 if ( colourStr == "RED" ) {
1584 } else if ( colourStr == "BLUE" ) {
1587 Log( string("What color? ") + colourStr );
1592 static PlayerColor OtherPlayerColor( PlayerColor player )
1594 return (player == kRed) ? kBlue : kRed;
1597 int main(int argc, char ** argv)
1600 cin.rdbuf()->pubsetbuf(NULL, 0);
1601 cout.rdbuf()->pubsetbuf(NULL, 0);
1602 cout.setf(std::ios::unitbuf);
1604 gOutputFile.open( (string("/tmp/peternlewis-output-") + to_string(time( NULL )) + "-" + to_string(rand() & 0xFFFF) + ".log").c_str() );
1605 gOutputFile.setf(std::ios::unitbuf);
1611 PlayerColor player = ReadPlayerLine();
1613 PositionPieces( &storage, player, &board );
1614 if ( player == kRed ) {
1615 for ( int r = 0; r <= 3; r++ ) {
1617 for ( int c = 0; c < kBoardSize; c++ ) {
1618 line += gPieceCharacters[board[r][c].thePieceRank];
1623 for ( int r = kBoardSize - 4; r < kBoardSize; r++ ) {
1625 for ( int c = 0; c < kBoardSize; c++ ) {
1626 line += gPieceCharacters[board[r][c].thePieceRank];
1632 bool expectStart = (player == kRed);
1635 if ( expectStart ) {
1637 expectStart = false;
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 );
1657 HelperJunkLine( kBoardSize );
1658 DumpBoard( &storage );
1660 PiecePosition moveFrom;
1661 PiecePosition moveTo;
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" );
1671 if ( moveTo.col > moveFrom.col ) {
1673 move = moveTo.col - moveFrom.col;
1674 } else if ( moveTo.col < moveFrom.col ) {
1676 move = moveFrom.col - moveTo.col;
1677 } else if ( moveTo.row < moveFrom.row ) {
1679 move = moveFrom.row - moveTo.row;
1680 } else if ( moveTo.row > moveFrom.row ) {
1682 move = moveTo.row - moveFrom.row;
1684 Output( to_string(moveFrom.col) + ' ' + to_string(moveFrom.row) + ' ' + dir + ' ' + to_string(move) );
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 );