agents/ramen/ai.c

   1 /*
   2  * UCC 2012 Programming Competition Entry
   3  * - "Ramen"
   4  *
   5  * By John Hodge [TPG]
   6  */
   7 #define ENABLE_DEBUG    0
   8 #define SHOW_TARGET_MAP 0
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <math.h>
  13 #include <limits.h>
  14 #include "interface.h"
  15 #include "ai_common.h"
  16
  17 // === CONSTANTS ===
  18 //! \brief Maximum recusion depth
  19 #define MAX_SEARCH_DEPTH        5
  20
  21 //! \brief Threshold before repeat modifier is applied
  22 #define REPEAT_THRESHOLD        3
  23 //! \brief Modifier applied to a repeated move
  24 #define REPEAT_MOVE_MODIFY(score)       do{score /= (giNumRepeatedMove <= 5 ? 2 : 10); score -= giNumRepeatedMove*10;}while(0);
  25
  26 //! \brief Number of moves by this AI before the defensive modifier kicks in
  27 #define DEFENSIVE_THRESHOLD     20
  28 //! \brief Modifier applied to offensive moves when > DEFENSIVE_THRESHOLD defensive moves have been done in a row
  29 #define DEFENSIVE_MODIFY(score) do{score *= 1+(giTurnsSinceLastTake/15);}while(0)
  30 /**
  31  * \name AI move outcome scores
  32  * \{
  33  */
  34 #define OC_LOSE -100
  35 #define OC_DRAW 0
  36 #define OC_UNK  40
  37 #define OC_WIN  100
  38 #define OC_FLAG 150
  39 /**
  40  * \}
  41  */
  42
  43 // === PROTOTYPES ===
  44 // - Wrapper and Initialisation
  45 void    AI_Initialise(enum eColours Colour, const char *Opponent);
  46 void    AI_HandleMove(int bMyMove, const tMove *Move);
  47 void    UpdateStates(const tMove *OpponentMove);
  48 void    AI_DoMove(tMove *MyMove);
  49 // - Management
  50 tPiece  *GetPieceByPos(int X, int Y);
  51 void    MovePieceTo(tPiece *Piece, int X, int Y);
  52 void    UpdateRank(tPiece *Piece, char RankChar);
  53 void    PieceExposed(tPiece *Piece);
  54 void    RemovePiece(tPiece *Piece);
  55 // -- AI Core
  56  int    GetBestMove(tPlayerStats *Attacker, tPlayerStats *Defender, tMove *Move, int Level);
  57  int    GetPositionScore(tPlayerStats *Attacker, tPlayerStats *Defender, int Level, int X, int Y, tPiece *Piece);
  58  int    GetScore(tPiece *This, tPiece *Target);
  59  int    GetRawScore(tPiece *This, tPiece *Target);
  60 // -- Helpers
  61 static inline int       GetOutcome(int Attacker, int Defender);
  62 static inline int       ABS(int Val);
  63 static inline int       RANGE(int Min, int Val, int Max);
  64
  65 // === GLOBALS ===
  66 enum eColours   gMyColour;
  67 tPiece  gBlockPiece = {.Team = 2};
  68  int    giGameStateSize;
  69 tGameState      *gpCurrentGameState;
  70 BOOL    gbFirstTurn = true;
  71 //tPiece        **gaBoardPieces;
  72 const char *gsOpponentDbFilename;
  73 // -- State variables to avoid deadlocking
  74  int    giNumRepeatedMove;
  75  int    giTurnsSinceLastTake;
  76 tMove   gLastMove;
  77 tPiece  *gLastMove_Target, *gLastMove_Piece;
  78
  79 // === CODE ===
  80 void AI_Initialise(enum eColours Colour, const char *Opponent)
  81 {
  82         gMyColour = Colour;
  83
  84         // TODO: Get opponent filename
  85         gsOpponentDbFilename = DB_GetOpponentFile(Opponent);
  86
  87         // Select setup
  88 //      setup_id = rand() % 3;
  89         int setup_id = 1;
  90         switch( setup_id )
  91         {
  92 //      case 0: // Bomb-off (dick move)
  93 //              // 39 pieces, bombs blocking gates, high level pieces backing up
  94 //              {
  95 //              const char *setup[] = {
  96 //                      "8.88979993\n",
  97 //                      "6689995986\n",
  98 //                      "F72434s174\n",
  99 //                      "BB56BB55BB\n"
 100 //                      };
 101 //              if( Colour == COLOUR_RED )
 102 //                      for(int i = 0; i < 4; i ++ )    printf(setup[i]);
 103 //              else
 104 //                      for(int i = 4; i --; )          printf(setup[i]);
 105 //              break;
 106 //              }
 107         case 1:
 108                 {
 109                 const char *setup[] = {
 110                         "FB8sB479B8\n",
 111                         "BB31555583\n",
 112                         "6724898974\n",
 113                         "967B669999\n"
 114                         };
 115                 if( Colour == COLOUR_RED )
 116                         for(int i = 0; i < 4; i ++ )    printf(setup[i]);
 117                 else
 118                         for(int i = 4; i --; )          printf(setup[i]);
 119                 }
 120                 break ;
 121         default:
 122                 exit(1);
 123         }
 124
 125
 126         giGameStateSize = sizeof(tGameState) + giBoardHeight*giBoardWidth*sizeof(tPieceRef);
 127         gpCurrentGameState = calloc( giGameStateSize, 1 );
 128         gpCurrentGameState->Opponent.Colour = !Colour;
 129         gpCurrentGameState->MyExposed.Colour = Colour;
 130         gpCurrentGameState->MyActual.Colour = Colour;
 131 //      gaBoardPieces = calloc( giBoardHeight*giBoardWidth, sizeof(tPiece*) );
 132 }
 133
 134 void AI_int_InitialiseBoardState(void)
 135 {
 136          int    piece_index = 0;
 137          int    my_piece_index = 0;
 138         for( int y = 0; y < giBoardHeight; y ++ )
 139         {
 140                 for( int x = 0; x < giBoardWidth; x ++ )
 141                 {
 142                         tPiece  *p;
 143                         char b;
 144
 145                         b = gaBoardState[y*giBoardWidth+x];
 146
 147                         if( b == '.' )  continue ;
 148                         if( b == '+' )
 149                         {
 150                                 gpCurrentGameState->BoardState[ y*giBoardWidth+x ].Team = 3;
 151                                 continue ;
 152                         }
 153
 154                         if( b == '#' )
 155                         {
 156                                 if( piece_index >= N_PIECES ) {
 157                                         piece_index ++;
 158                                         continue ;
 159                                 }
 160                                 p = &gpCurrentGameState->Opponent.Pieces[piece_index++];
 161                                 p->Rank = RANK_UNKNOWN;
 162                                 p->X = x;       p->StartX = x;
 163                                 p->Y = y;       p->StartY = y;
 164                                 p->bHasMoved = false;
 165                                 p->Team = !gMyColour;
 166                                 gpCurrentGameState->BoardState[ y*giBoardWidth+x ].Team = 2;
 167                                 gpCurrentGameState->BoardState[ y*giBoardWidth+x ].Index = piece_index - 1;
 168                                 DEBUG("Enemy at %i,%i", x, y);
 169                         }
 170                         else
 171                         {
 172                                 if( my_piece_index >= N_PIECES ) {
 173                                         my_piece_index ++;
 174                                         continue ;
 175                                 }
 176                                 p = &gpCurrentGameState->MyActual.Pieces[my_piece_index++];
 177                                 p->X = x;
 178                                 p->Y = y;
 179                                 p->Team = gMyColour;
 180                                 UpdateRank(p, b);
 181                                 gpCurrentGameState->MyActual.nRanks[p->Rank] ++;
 182                                 gpCurrentGameState->BoardState[ y*giBoardWidth+x ].Team = 1;
 183                                 gpCurrentGameState->BoardState[ y*giBoardWidth+x ].Index = my_piece_index - 1;
 184                         }
 185
 186
 187                 }
 188         }
 189         gpCurrentGameState->Opponent.nPieces = piece_index;
 190         if( piece_index > N_PIECES )
 191                 DEBUG("GAH! Too many opposing pieces (%i > 40)", piece_index);
 192         if( my_piece_index > N_PIECES )
 193                 DEBUG("GAH! Too many of my pieces (%i > 40)", my_piece_index);
 194
 195         // Catch for if I don't put enough pieces out (shouldn't happen)
 196         while( my_piece_index < N_PIECES ) {
 197                 gpCurrentGameState->MyActual.Pieces[my_piece_index].bDead = true;
 198                 gpCurrentGameState->MyActual.Pieces[my_piece_index].Rank = RANK_UNKNOWN;
 199                 my_piece_index ++;
 200         }
 201
 202         // Load guesses at what each piece is
 203         DB_LoadGuesses(gsOpponentDbFilename, !gMyColour);
 204         gpCurrentGameState->Opponent.bGuessValid = true;
 205 }
 206
 207 void AI_HandleMove(int bMyMove, const tMove *Move)
 208 {
 209         if( gbFirstTurn )
 210         {
 211                 gbFirstTurn = false;
 212
 213                 AI_int_InitialiseBoardState();
 214
 215                 // Reverse the first move
 216                 if( Move->dir != DIR_INVAL )
 217                 {
 218                         tPiece  *p;
 219                         switch(Move->dir)
 220                         {
 221                         case DIR_INVAL: ASSERT(Move->dir != DIR_INVAL); break;
 222                         case DIR_LEFT:  p = GetPieceByPos( Move->x-1, Move->y );        break ;
 223                         case DIR_RIGHT: p = GetPieceByPos( Move->x+1, Move->y );        break ;
 224                         case DIR_UP:    p = GetPieceByPos( Move->x, Move->y-1 );        break ;
 225                         case DIR_DOWN:  p = GetPieceByPos( Move->x, Move->y+1 );        break ;
 226                         }
 227                         MovePieceTo( p, Move->x, Move->y );
 228                         p->StartX = Move->x;
 229                         p->StartY = Move->y;
 230                 }
 231         }
 232
 233         if(Move->result == RESULT_VICTORY)
 234         {
 235                 // TODO: Distiguish between victory conditions?
 236                 // - Note flag location?
 237
 238                 // TODO: Save back initial board state
 239                 DB_WriteBackInitialState(gsOpponentDbFilename, !gMyColour, gpCurrentGameState->Opponent.Pieces);
 240         }
 241
 242         if( !bMyMove )
 243         {
 244                 if( Move->dir != DIR_INVAL )
 245                         UpdateStates(Move);
 246         }
 247         else
 248         {
 249                 tPiece  *p = GetPieceByPos(Move->x, Move->y);
 250                 ASSERT(p);
 251
 252                 int newx = p->X, newy = p->Y;
 253                 switch(Move->dir)
 254                 {
 255                 case DIR_INVAL: break;
 256                 case DIR_LEFT:  newx -= Move->dist;     break;
 257                 case DIR_RIGHT: newx += Move->dist;     break;
 258                 case DIR_UP:    newy -= Move->dist;     break;
 259                 case DIR_DOWN:  newy += Move->dist;     break;
 260                 }
 261                 tPiece  *target = GetPieceByPos(newx, newy);
 262
 263                 switch(Move->result)
 264                 {
 265                 case RESULT_ILLEGAL:    break;
 266                 case RESULT_INVAL:      break;
 267                 case RESULT_OK:
 268                         MovePieceTo(p, newx, newy);
 269                         break;
 270                 case RESULT_KILL:
 271                         UpdateRank(target, Move->defender);
 272                         RemovePiece(target);
 273                         MovePieceTo(p, newx, newy);
 274                         PieceExposed(p);        // TODO: Update oponent's view
 275                         giTurnsSinceLastTake = 0;
 276                         break;
 277                 case RESULT_DIES:
 278                 case RESULT_VICTORY:
 279                         UpdateRank(target, Move->defender);
 280                         PieceExposed(p);
 281                         RemovePiece(p);
 282                         giTurnsSinceLastTake = 0;
 283                         break;
 284                 case RESULT_BOTHDIE:
 285                         UpdateRank(target, Move->defender);
 286                         PieceExposed(p);
 287                         RemovePiece(p);
 288                         RemovePiece(target);
 289                         giTurnsSinceLastTake = 0;
 290                         break;
 291                 }
 292         }
 293 }
 294
 295 void UpdateStates(const tMove *OpponentMove)
 296 {
 297         // --- Get moved piece, update position ---
 298         tPiece  *moved_piece = GetPieceByPos(OpponentMove->x, OpponentMove->y);
 299         // - Sanity
 300         ASSERT( moved_piece );
 301         ASSERT( moved_piece->Team == !gMyColour );
 302         // - Only scouts can move multiple squares
 303         if( moved_piece->Rank == RANK_UNKNOWN && OpponentMove->dist > 1 )
 304                 UpdateRank(moved_piece, '9');
 305         // - Update position
 306          int newx = moved_piece->X, newy = moved_piece->Y;
 307         switch(OpponentMove->dir)
 308         {
 309         case DIR_INVAL: break;
 310         case DIR_LEFT:  newx -= OpponentMove->dist;     break;
 311         case DIR_RIGHT: newx += OpponentMove->dist;     break;
 312         case DIR_UP:    newy -= OpponentMove->dist;     break;
 313         case DIR_DOWN:  newy += OpponentMove->dist;     break;
 314         }
 315         tPiece  *my_piece = GetPieceByPos(newx, newy);
 316
 317         // Check if one of my pieces has been taken
 318         switch( OpponentMove->result )
 319         {
 320         case RESULT_ILLEGAL:    break;
 321         case RESULT_INVAL:      break;
 322         case RESULT_OK:
 323                 MovePieceTo(moved_piece, newx, newy);
 324                 break;
 325         case RESULT_KILL:
 326         case RESULT_VICTORY:
 327                 UpdateRank(moved_piece, OpponentMove->attacker);
 328                 PieceExposed(my_piece);
 329                 RemovePiece(my_piece);
 330                 MovePieceTo(moved_piece, newx, newy);
 331                 break;
 332         case RESULT_DIES:
 333                 UpdateRank(moved_piece, OpponentMove->attacker);
 334                 PieceExposed(my_piece);
 335                 RemovePiece(moved_piece);
 336                 break;
 337         case RESULT_BOTHDIE:
 338                 UpdateRank(moved_piece, OpponentMove->attacker);
 339                 RemovePiece(moved_piece);
 340                 PieceExposed(my_piece);
 341                 RemovePiece(my_piece);
 342                 break;
 343         }
 344
 345         // Update rank if revealed
 346         if( moved_piece->Rank == RANK_UNKNOWN )
 347                 UpdateRank(moved_piece, gaBoardState[moved_piece->Y*giBoardWidth+moved_piece->X]);
 348
 349         // - Update piece states
 350         DEBUG("Updating piece states");
 351         for( int y = 0; y < giBoardHeight; y ++ )
 352         {
 353                 for( int x = 0; x < giBoardWidth; x ++ )
 354                 {
 355                         char    c = gaBoardState[y*giBoardWidth+x];
 356                         if( c == '.' )  continue;
 357                         if( c == '+' )  continue;
 358                         tPiece *p = GetPieceByPos(x, y);
 359                         if(!p) DEBUG("c = %c", c);
 360                         ASSERT(p);
 361                         if( p->Team == gMyColour )      continue ;
 362                         if( p->Rank == RANK_UNKNOWN && c != '#' )
 363                                 UpdateRank(p, c);
 364                 }
 365         }
 366 }
 367
 368 void AI_DoMove(tMove *MyMove)
 369 {
 370 #if 1
 371         // Sanity checks
 372         for( int i = 0; i < N_PIECES; i ++ )
 373         {
 374                 tPiece  *p = &gpCurrentGameState->MyActual.Pieces[i];
 375                 if(p->bDead)    continue;
 376
 377                 if( p != GetPieceByPos(p->X, p->Y) ) {
 378                         DEBUG("Piece %p(%i,%i R%i) not at stated position",
 379                                 p, p->X, p->Y, p->Rank);
 380                 }
 381         }
 382 #endif
 383
 384         DEBUG("Deciding on move");
 385         GetBestMove(&gpCurrentGameState->MyActual, &gpCurrentGameState->Opponent, MyMove, 0);
 386 }
 387
 388 tPiece *GetPieceByPos(int X, int Y)
 389 {
 390         tPieceRef       *pr = &gpCurrentGameState->BoardState[Y*giBoardWidth+X];
 391         switch( pr->Team )
 392         {
 393         case 0: return NULL;
 394         case 1: return &gpCurrentGameState->MyActual.Pieces[ (int)pr->Index ];
 395         case 2: return &gpCurrentGameState->Opponent.Pieces[ (int)pr->Index ];
 396         case 3: return &gBlockPiece;
 397         }
 398         return NULL;
 399 }
 400
 401 void MovePieceTo(tPiece *Piece, int X, int Y)
 402 {
 403         DEBUG("Moved %p(%i,%i) to (%i,%i)",
 404                 Piece, Piece->X, Piece->Y, X, Y);
 405
 406         gpCurrentGameState->BoardState[Y*giBoardWidth + X]
 407                 = gpCurrentGameState->BoardState[Piece->Y*giBoardWidth + Piece->X];
 408         gpCurrentGameState->BoardState[Piece->Y*giBoardWidth + Piece->X].Team = 0;
 409
 410         Piece->X = X;
 411         Piece->Y = Y;
 412
 413         if( !Piece->bHasMoved )
 414         {
 415                 if( Piece->Team == gMyColour )
 416                 {
 417                         gpCurrentGameState->MyExposed.nMoved ++;
 418                 }
 419                 else
 420                 {
 421                         gpCurrentGameState->Opponent.nMoved ++;
 422                 }
 423         }
 424
 425         Piece->bHasMoved = true;
 426 }
 427
 428 void UpdateRank(tPiece *Piece, char RankChar)
 429 {
 430         enum eRanks rank;
 431
 432         rank = CharToRank(RankChar);
 433
 434         if( Piece->Rank == rank )
 435                 return ;
 436
 437         if( Piece->Rank != RANK_UNKNOWN )
 438         {
 439                 if(Piece->Rank != rank )
 440                 {
 441                         DEBUG("Rank of piece %p(%i,%i) has changed, was %i now %i",
 442                                 Piece, Piece->X, Piece->Y, Piece->Rank, rank);
 443                         Piece->Rank = rank;
 444                 }
 445                 return ;
 446         }
 447
 448         if( Piece->Team == !gMyColour && rank != RANK_UNKNOWN )
 449         {
 450                 if( gpCurrentGameState->Opponent.nRanks[rank] >= MAX_RANK_COUNTS[rank] ) {
 451                         DEBUG("ERROR: Bookkeeping failed, >%i units of rank %i on board",
 452                                 MAX_RANK_COUNTS[rank], rank);
 453                 }
 454                 DEBUG("Found a %i", rank);
 455                 gpCurrentGameState->Opponent.nRanks[rank] ++;
 456                 if( gpCurrentGameState->Opponent.nIdentified == gpCurrentGameState->Opponent.nPieces ) {
 457                         DEBUG("ERROR: Bookkeeping failed, >%i units identified",
 458                                 gpCurrentGameState->Opponent.nPieces);
 459                 }
 460                 gpCurrentGameState->Opponent.nIdentified ++;
 461
 462                 if( Piece->GuessedRank != RANK_UNKNOWN && Piece->GuessedRank != rank )
 463                 {
 464                         fprintf(stderr, "Assumption failed, saved %c != act %c",
 465                                 cRANK_CHARS[Piece->GuessedRank], cRANK_CHARS[rank]);
 466                         gpCurrentGameState->Opponent.bGuessValid = false;
 467                 }
 468
 469         }
 470         Piece->Rank = rank;
 471         if( Piece->Team == !gMyColour )
 472         {
 473                 // Expensive? What's that?
 474                 DB_WriteBackInitialState(gsOpponentDbFilename, !gMyColour, gpCurrentGameState->Opponent.Pieces);
 475         }
 476 }
 477
 478 void PieceExposed(tPiece *Piece)
 479 {
 480         ASSERT(Piece->Team == gMyColour);
 481         if( Piece->bExposed == false )
 482         {
 483                 gpCurrentGameState->MyExposed.nRanks[Piece->Rank] ++;
 484                 gpCurrentGameState->MyExposed.nIdentified ++;
 485                 Piece->bExposed = true;
 486         }
 487 }
 488
 489 /**
 490  * \brief Remove a piece from the board
 491  */
 492 void RemovePiece(tPiece *Piece)
 493 {
 494         tPlayerStats    *owner;
 495         gpCurrentGameState->BoardState[Piece->Y*giBoardWidth + Piece->X].Team = 0;
 496         if( Piece->Team == !gMyColour ) {
 497                 owner = &gpCurrentGameState->Opponent;
 498         }
 499         else {
 500                 owner = &gpCurrentGameState->MyExposed;
 501                 gpCurrentGameState->MyActual.nRanks[Piece->Rank] --;
 502         }
 503         owner->nKilledRanks[Piece->Rank] ++;
 504         owner->nRanks[Piece->Rank] --;
 505         owner->nIdentified --;
 506         owner->nPieces --;
 507         Piece->bDead = true;
 508 }
 509
 510 // ----------------------------------------------------------------------------
 511 // - AI Core
 512 // ----------------------------------------------------------------------------
 513 #define TARGET_GRID_W   10
 514 #define TARGET_GRID_H   10
 515 #define TARGET_GRID_SIZE        (TARGET_GRID_W*TARGET_GRID_H)
 516 typedef struct sGridSlot {
 517         tPiece  *p;
 518         char    dist;
 519         char    complexity;
 520         enum eDirections        firstdir;
 521         char    firstdist;
 522         char    bDirect;
 523 } tTargetGrid[TARGET_GRID_SIZE];
 524 int GetTargetsFrom(tPiece *Piece, tTargetGrid *grid)
 525 {
 526          int    n_targets;
 527
 528         memset(*grid, 0, sizeof(*grid));
 529
 530         int cur_dist = 1;
 531         int b_updates = 0;
 532
 533         void _check_dir(struct sGridSlot *pgs, struct sGridSlot *gs, int x, int y, enum eDirections dir)
 534         {
 535                 if( !gs )       return ;
 536                 if( gs->dist )  return ;
 537                 if( pgs->p )    return ;
 538
 539                 tPiece *p = GetPieceByPos(x, y);
 540                 if( p && (p == &gBlockPiece || p->Team == Piece->Team) )
 541                         p = (void*)-1;
 542                 gs->dist = cur_dist + 1;
 543                 gs->p = p;
 544                 DEBUG("%p at %i,%i %i away", p, x, y, cur_dist);
 545                 if( pgs->firstdir == DIR_INVAL || (pgs->firstdir == dir && pgs->bDirect) ) {
 546                         gs->bDirect = 1;
 547                         gs->firstdir = dir;
 548                         gs->firstdist = pgs->firstdist + 1;
 549                 }
 550                 else {
 551                         gs->firstdist = pgs->firstdist;
 552                         gs->firstdir = pgs->firstdir;
 553                         gs->bDirect = 0;
 554                 }
 555                 b_updates = 1;
 556         }
 557
 558         (*grid)[ Piece->X + Piece->Y * TARGET_GRID_W ].dist = -1;
 559
 560         do {
 561                 b_updates = 0;
 562                 for( int i = 0; i < TARGET_GRID_SIZE; i ++ )
 563                 {
 564                         int x = i % TARGET_GRID_W;
 565                         int y = i / TARGET_GRID_H;
 566                         struct sGridSlot        *gs = &(*grid)[i];
 567
 568                         struct sGridSlot        *gs_u = NULL, *gs_d = NULL;
 569                         struct sGridSlot        *gs_l = NULL, *gs_r = NULL;
 570
 571                         if( !gs->dist ) continue ;
 572
 573                         // Get adjacent cells
 574                         if( y > 0 )
 575                                 gs_u = &(*grid)[i - TARGET_GRID_W];
 576                         if( x > 0 )
 577                                 gs_l = &(*grid)[i - 1];
 578                         if( y < TARGET_GRID_H - 1 )
 579                                 gs_d = &(*grid)[i + TARGET_GRID_W];
 580                         if( x < TARGET_GRID_W - 1 )
 581                                 gs_r = &(*grid)[i + 1];
 582
 583                         _check_dir(gs, gs_u, x, y-1, DIR_UP);
 584                         _check_dir(gs, gs_d, x, y+1, DIR_DOWN);
 585                         _check_dir(gs, gs_l, x-1, y, DIR_LEFT);
 586                         _check_dir(gs, gs_r, x+1, y, DIR_RIGHT);
 587                 }
 588
 589                 cur_dist ++;
 590         } while(b_updates);
 591
 592 #if SHOW_TARGET_MAP
 593         fprintf(stderr, "%p Type %c\n", Piece, cRANK_CHARS[Piece->Rank]);
 594         for( int i = 0; i < 10*10; i ++ )
 595         {
 596                 tPiece  *np = (*grid)[i].p;
 597                 if( i == Piece->X + Piece->Y * TARGET_GRID_W )
 598                         fprintf(stderr, "?");
 599                 else if( (*grid)[i].dist == 0 )
 600                         fprintf(stderr, "#");   // Unreachable
 601                 else if( !np )
 602                         fprintf(stderr, " ");   // Empty
 603                 else if( np == (void*)-1 )
 604                         fprintf(stderr, ".");   // My team/block
 605                 else
 606                         fprintf(stderr, "X");   // Viable target!
 607                 if( i % 10 == 9 )
 608                         fprintf(stderr, "\n");
 609         }
 610 #endif
 611
 612         DEBUG("Getting targets");
 613         n_targets = 0;
 614         for( int i = 0; i < TARGET_GRID_SIZE; i ++ )
 615         {
 616                 if( (*grid)[i].p == (void*)-1 )
 617                         (*grid)[i].p = NULL;
 618                 if( (*grid)[i].p ) {
 619                         DEBUG("Target (%i,%i) %p %i dist",
 620                                 i%10, i/10, (*grid)[i].p, (*grid)[i].dist);
 621                         (*grid)[i].dist -= 1;
 622                         n_targets ++;
 623                 }
 624         }
 625
 626         return n_targets;
 627 }
 628
 629 int GetBestMove(tPlayerStats *Attacker, tPlayerStats *Defender, tMove *Move, int Level)
 630 {
 631         // Avoid infinite recursion
 632         if( Level == MAX_SEARCH_DEPTH ) return 1;
 633
 634          int    best_score = INT_MIN;
 635         tMove   best_move;
 636         tPiece  *best_p = NULL;
 637         tPiece  *best_target = NULL;
 638         tTargetGrid     grid;
 639
 640         // - Check possible moves
 641         for( int i = 0; i < N_PIECES; i ++ )
 642         {
 643                 tPiece  *p = &Attacker->Pieces[i];
 644                  int    p_score = 0;    // Piece score
 645                 struct sGridSlot        *bt_gs = NULL;
 646                  int    bt_score;       // Best target score
 647
 648                 // Dead, ignore
 649                 if( p->bDead )
 650                         continue ;
 651                 // These cannot move
 652                 if( p->Rank == RANK_BOMB || p->Rank == RANK_FLAG )
 653                         continue ;
 654
 655                 // Get what pieces are able to be attacked from this piece
 656                 int nt = GetTargetsFrom(p, &grid);
 657                 DEBUG("(%i,%i) %i targets", p->X, p->Y, nt);
 658                 if( nt <= 0 )   continue ;
 659
 660                 // Find the best target of those
 661                 for( int j = 0; j < TARGET_GRID_SIZE; j ++ )
 662                 {
 663                         struct sGridSlot *gs = &grid[j];
 664                         if( !gs->p )    continue ;
 665
 666                         int t_score = GetScore(p, gs->p);
 667
 668 #if 1
 669                         if( gs->p == gLastMove_Target && p == gLastMove_Piece && giNumRepeatedMove > REPEAT_THRESHOLD)
 670                         {
 671                                 REPEAT_MOVE_MODIFY(t_score);
 672                         }
 673 #endif
 674
 675                         // TODO: For scouts, use gs->complexity
 676                         // TODO: Don't use a linear relationship on distance
 677                         p_score += t_score / (gs->dist < 2 ? 1 : 2);
 678
 679                         // Best target
 680                         if( !bt_gs || t_score > bt_score ) {
 681                                 bt_score = t_score;
 682                                 bt_gs = gs;
 683                         }
 684                 }
 685
 686                 DEBUG("p_score = %i, bt_score = %i", p_score, bt_score);
 687
 688                 // Best move is towards that piece
 689                 if( best_move.dir == DIR_INVAL || best_score < p_score )
 690                 {
 691                         best_move.dir = bt_gs->firstdir;
 692                         best_move.x = p->X;
 693                         best_move.y = p->Y;
 694                         best_move.dist = (p->Rank == RANK_SCOUT) ? bt_gs->firstdist : 1;
 695                         best_score = p_score;
 696                         best_p = p;
 697                         best_target = bt_gs->p;
 698                 }
 699         }
 700
 701
 702         if( Move )
 703         {
 704                 ASSERT(best_move.dir != DIR_INVAL);
 705                 *Move = best_move;
 706
 707                 if( ((Move->dir-1)^1) == gLastMove.dir-1 && Move->dist == gLastMove.dist
 708                 && Move->x == gLastMove.x && Move->y == gLastMove.y )
 709                 {
 710                         giNumRepeatedMove ++;
 711                         DEBUG("Up to %i repititions", giNumRepeatedMove);
 712                 }
 713                 else
 714                         giNumRepeatedMove = 0;
 715
 716                 // TODO: Recurse once on this to determine what the other team will do
 717                 // Record that move, then check when the move is performed to see if we were right.
 718
 719                 gLastMove = *Move;
 720                 gLastMove_Target = best_target;
 721                 gLastMove_Piece = best_p;
 722                 giTurnsSinceLastTake ++;
 723         }
 724
 725         DEBUG("best_score = %i", best_score);
 726
 727         return best_score;
 728 }
 729
 730 /**
 731  * \brief
 732  */
 733 int GetScore(tPiece *This, tPiece *Target)
 734 {
 735         tPlayerStats    *attacker, *defender;
 736         int score;
 737
 738         if( This->Team == gMyColour ) {
 739                 defender = &gpCurrentGameState->Opponent;
 740                 attacker = &gpCurrentGameState->MyExposed;
 741         }
 742         else {
 743                 attacker = &gpCurrentGameState->Opponent;
 744                 defender = &gpCurrentGameState->MyExposed;
 745         }
 746
 747         score = GetRawScore(This, Target);
 748
 749         if( This->Team == gMyColour )
 750         {
 751                 switch( This->Rank )
 752                 {
 753                 case RANK_MARSHAL:      // Marshal has balls of steel if the spy and enemy marshal are dead
 754                         if( defender->nKilledRanks[RANK_MARSHAL] && defender->nKilledRanks[RANK_SPY] )
 755                                 score *= 2;
 756                         break;
 757                 case RANK_GENERAL:      // General always attacks!
 758                         score *= 2;
 759                         break;
 760                 case RANK_SCOUT:
 761                         score = score * gpCurrentGameState->MyActual.nRanks[RANK_SCOUT] / MAX_RANK_COUNTS[RANK_SCOUT] + score;
 762                         break;
 763                 default:
 764                         break;
 765                 }
 766         }
 767
 768         return score;
 769 }
 770
 771 int GetRawScore(tPiece *This, tPiece *Target)
 772 {
 773         tPlayerStats    *this_team, *target_team;
 774
 775         ASSERT( This->Team != Target->Team );
 776
 777         if( This->Team == gMyColour ) {
 778                 target_team = &gpCurrentGameState->Opponent;
 779                 this_team = &gpCurrentGameState->MyExposed;
 780         }
 781         else {
 782                 this_team = &gpCurrentGameState->Opponent;
 783                 target_team = &gpCurrentGameState->MyExposed;
 784         }
 785
 786         // Both ranks known, used fixed rules
 787         if( This->Rank != RANK_UNKNOWN && Target->Rank != RANK_UNKNOWN )
 788         {
 789                 return GetOutcome(This->Rank, Target->Rank);
 790         }
 791         // If it's our move, and the guesses are valid, then use the guess
 792         else if( This->Team == gMyColour
 793                 && gpCurrentGameState->Opponent.bGuessValid
 794                 && Target->GuessedRank != RANK_UNKNOWN
 795                 )
 796         {
 797                 return GetOutcome(This->Rank, Target->GuessedRank);
 798         }
 799         else
 800         {
 801                  int    sum = 0;
 802                  int    max = Target->bHasMoved ? RANK_SPY : RANK_FLAG;
 803                  int    count = 0;
 804
 805                 if( target_team->nIdentified >= target_team->nPieces ) {
 806                         DEBUG("%i >= %i, what the fsck",
 807                                 target_team->nIdentified, target_team->nPieces);
 808                 }
 809                 ASSERT(target_team->nPieces > target_team->nIdentified);
 810
 811                 for( int i = RANK_MARSHAL; i <= max; i ++ )
 812                 {
 813                          int    n_unk = MAX_RANK_COUNTS[i] - (target_team->nRanks[i] + target_team->nKilledRanks[i]);
 814                         if( n_unk == 0 )
 815                                 continue ;
 816                         ASSERT( n_unk > 0 );
 817
 818                         // TODO: Fiddle with outcome score depending on respective ranks
 819                         sum += n_unk * GetOutcome(This->Rank, i);
 820                         count += n_unk;
 821                 }
 822
 823 //              if( Target->bHasMoved )
 824 //                      sum /= target_team->nPieces - target_team->nMoved;
 825 //              else
 826 //                      sum /= target_team->nPieces - target_team->nIdentified;
 827                 sum /= count;
 828
 829                 if( sum > OC_FLAG ) {
 830                         fprintf(stderr, "sum (%i) > OC_WIN (%i) -- nUnIdent=%i\n",
 831                                 sum, OC_WIN, target_team->nPieces - target_team->nIdentified);
 832                         ASSERT( sum <= OC_FLAG );
 833                 }
 834
 835                 return sum - ABS(sum) / 10;
 836         }
 837 }
 838
 839 static inline int GetOutcome(int Attacker, int Defender)
 840 {
 841         if( Attacker == 0 )     return OC_UNK;
 842         if( Defender == 0 )     return OC_UNK;
 843
 844         if( Defender == RANK_FLAG )
 845                 return OC_FLAG;
 846
 847         if( Attacker != RANK_MINER && Defender == RANK_BOMB )
 848                 return OC_LOSE;
 849         if( Attacker == RANK_MINER && Defender == RANK_BOMB )
 850                 return OC_WIN;
 851
 852         if( Attacker == RANK_SPY && Defender == RANK_MARSHAL )
 853                 return OC_WIN;
 854
 855         if( Attacker == Defender )
 856                 return OC_DRAW;
 857
 858         if( Attacker < Defender )
 859                 return OC_WIN;
 860         else
 861                 return OC_LOSE;
 862 }
 863
 864
 865 static inline int ABS(int Val)
 866 {
 867         return Val < 0 ? -Val : Val;
 868 }
 869
 870 static inline int RANGE(int Min, int Val, int Max)
 871 {
 872         return Min <= Val && Val <= Max;
 873 }
 874