2 * UCC 2012 Programming Competition Entry
8 #define SHOW_TARGET_MAP 0
14 #include "interface.h"
15 #include "ai_common.h"
18 //! \brief Maximum recusion depth
19 #define MAX_SEARCH_DEPTH 5
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);
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)
31 * \name AI move outcome scores
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);
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);
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);
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);
66 enum eColours gMyColour;
67 tPiece gBlockPiece = {.Team = 2};
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;
77 tPiece *gLastMove_Target, *gLastMove_Piece;
80 void AI_Initialise(enum eColours Colour, const char *Opponent)
84 // TODO: Get opponent filename
85 gsOpponentDbFilename = DB_GetOpponentFile(Opponent);
88 // setup_id = rand() % 3;
92 // case 0: // Bomb-off (dick move)
93 // // 39 pieces, bombs blocking gates, high level pieces backing up
95 // const char *setup[] = {
101 // if( Colour == COLOUR_RED )
102 // for(int i = 0; i < 4; i ++ ) printf(setup[i]);
104 // for(int i = 4; i --; ) printf(setup[i]);
109 const char *setup[] = {
115 if( Colour == COLOUR_RED )
116 for(int i = 0; i < 4; i ++ ) printf(setup[i]);
118 for(int i = 4; i --; ) printf(setup[i]);
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*) );
134 void AI_int_InitialiseBoardState(void)
137 int my_piece_index = 0;
138 for( int y = 0; y < giBoardHeight; y ++ )
140 for( int x = 0; x < giBoardWidth; x ++ )
145 b = gaBoardState[y*giBoardWidth+x];
147 if( b == '.' ) continue ;
150 gpCurrentGameState->BoardState[ y*giBoardWidth+x ].Team = 3;
156 if( piece_index >= N_PIECES ) {
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);
172 if( my_piece_index >= N_PIECES ) {
176 p = &gpCurrentGameState->MyActual.Pieces[my_piece_index++];
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;
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);
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;
202 // Load guesses at what each piece is
203 DB_LoadGuesses(gsOpponentDbFilename, !gMyColour);
204 gpCurrentGameState->Opponent.bGuessValid = true;
207 void AI_HandleMove(int bMyMove, const tMove *Move)
213 AI_int_InitialiseBoardState();
215 // Reverse the first move
216 if( Move->dir != DIR_INVAL )
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 ;
227 MovePieceTo( p, Move->x, Move->y );
233 if(Move->result == RESULT_VICTORY)
235 // TODO: Distiguish between victory conditions?
236 // - Note flag location?
238 // TODO: Save back initial board state
239 DB_WriteBackInitialState(gsOpponentDbFilename, !gMyColour, gpCurrentGameState->Opponent.Pieces);
244 if( Move->dir != DIR_INVAL )
249 tPiece *p = GetPieceByPos(Move->x, Move->y);
252 int newx = p->X, newy = p->Y;
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;
261 tPiece *target = GetPieceByPos(newx, newy);
265 case RESULT_ILLEGAL: break;
266 case RESULT_INVAL: break;
268 MovePieceTo(p, newx, newy);
271 UpdateRank(target, Move->defender);
273 MovePieceTo(p, newx, newy);
274 PieceExposed(p); // TODO: Update oponent's view
275 giTurnsSinceLastTake = 0;
279 UpdateRank(target, Move->defender);
282 giTurnsSinceLastTake = 0;
285 UpdateRank(target, Move->defender);
289 giTurnsSinceLastTake = 0;
295 void UpdateStates(const tMove *OpponentMove)
297 // --- Get moved piece, update position ---
298 tPiece *moved_piece = GetPieceByPos(OpponentMove->x, OpponentMove->y);
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');
306 int newx = moved_piece->X, newy = moved_piece->Y;
307 switch(OpponentMove->dir)
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;
315 tPiece *my_piece = GetPieceByPos(newx, newy);
317 // Check if one of my pieces has been taken
318 switch( OpponentMove->result )
320 case RESULT_ILLEGAL: break;
321 case RESULT_INVAL: break;
323 MovePieceTo(moved_piece, newx, newy);
327 UpdateRank(moved_piece, OpponentMove->attacker);
328 PieceExposed(my_piece);
329 RemovePiece(my_piece);
330 MovePieceTo(moved_piece, newx, newy);
333 UpdateRank(moved_piece, OpponentMove->attacker);
334 PieceExposed(my_piece);
335 RemovePiece(moved_piece);
338 UpdateRank(moved_piece, OpponentMove->attacker);
339 RemovePiece(moved_piece);
340 PieceExposed(my_piece);
341 RemovePiece(my_piece);
345 // Update rank if revealed
346 if( moved_piece->Rank == RANK_UNKNOWN )
347 UpdateRank(moved_piece, gaBoardState[moved_piece->Y*giBoardWidth+moved_piece->X]);
349 // - Update piece states
350 DEBUG("Updating piece states");
351 for( int y = 0; y < giBoardHeight; y ++ )
353 for( int x = 0; x < giBoardWidth; x ++ )
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);
361 if( p->Team == gMyColour ) continue ;
362 if( p->Rank == RANK_UNKNOWN && c != '#' )
368 void AI_DoMove(tMove *MyMove)
372 for( int i = 0; i < N_PIECES; i ++ )
374 tPiece *p = &gpCurrentGameState->MyActual.Pieces[i];
375 if(p->bDead) continue;
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);
384 DEBUG("Deciding on move");
385 GetBestMove(&gpCurrentGameState->MyActual, &gpCurrentGameState->Opponent, MyMove, 0);
388 tPiece *GetPieceByPos(int X, int Y)
390 tPieceRef *pr = &gpCurrentGameState->BoardState[Y*giBoardWidth+X];
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;
401 void MovePieceTo(tPiece *Piece, int X, int Y)
403 DEBUG("Moved %p(%i,%i) to (%i,%i)",
404 Piece, Piece->X, Piece->Y, X, Y);
406 gpCurrentGameState->BoardState[Y*giBoardWidth + X]
407 = gpCurrentGameState->BoardState[Piece->Y*giBoardWidth + Piece->X];
408 gpCurrentGameState->BoardState[Piece->Y*giBoardWidth + Piece->X].Team = 0;
413 if( !Piece->bHasMoved )
415 if( Piece->Team == gMyColour )
417 gpCurrentGameState->MyExposed.nMoved ++;
421 gpCurrentGameState->Opponent.nMoved ++;
425 Piece->bHasMoved = true;
428 void UpdateRank(tPiece *Piece, char RankChar)
432 rank = CharToRank(RankChar);
434 if( Piece->Rank == rank )
437 if( Piece->Rank != RANK_UNKNOWN )
439 if(Piece->Rank != rank )
441 DEBUG("Rank of piece %p(%i,%i) has changed, was %i now %i",
442 Piece, Piece->X, Piece->Y, Piece->Rank, rank);
448 if( Piece->Team == !gMyColour && rank != RANK_UNKNOWN )
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);
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);
460 gpCurrentGameState->Opponent.nIdentified ++;
462 if( Piece->GuessedRank != RANK_UNKNOWN && Piece->GuessedRank != rank )
464 fprintf(stderr, "Assumption failed, saved %c != act %c",
465 cRANK_CHARS[Piece->GuessedRank], cRANK_CHARS[rank]);
466 gpCurrentGameState->Opponent.bGuessValid = false;
471 if( Piece->Team == !gMyColour )
473 // Expensive? What's that?
474 DB_WriteBackInitialState(gsOpponentDbFilename, !gMyColour, gpCurrentGameState->Opponent.Pieces);
478 void PieceExposed(tPiece *Piece)
480 ASSERT(Piece->Team == gMyColour);
481 if( Piece->bExposed == false )
483 gpCurrentGameState->MyExposed.nRanks[Piece->Rank] ++;
484 gpCurrentGameState->MyExposed.nIdentified ++;
485 Piece->bExposed = true;
490 * \brief Remove a piece from the board
492 void RemovePiece(tPiece *Piece)
495 gpCurrentGameState->BoardState[Piece->Y*giBoardWidth + Piece->X].Team = 0;
496 if( Piece->Team == !gMyColour ) {
497 owner = &gpCurrentGameState->Opponent;
500 owner = &gpCurrentGameState->MyExposed;
501 gpCurrentGameState->MyActual.nRanks[Piece->Rank] --;
503 owner->nKilledRanks[Piece->Rank] ++;
504 owner->nRanks[Piece->Rank] --;
505 owner->nIdentified --;
510 // ----------------------------------------------------------------------------
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 {
520 enum eDirections firstdir;
523 } tTargetGrid[TARGET_GRID_SIZE];
524 int GetTargetsFrom(tPiece *Piece, tTargetGrid *grid)
528 memset(*grid, 0, sizeof(*grid));
533 void _check_dir(struct sGridSlot *pgs, struct sGridSlot *gs, int x, int y, enum eDirections dir)
536 if( gs->dist ) return ;
537 if( pgs->p ) return ;
539 tPiece *p = GetPieceByPos(x, y);
540 if( p && (p == &gBlockPiece || p->Team == Piece->Team) )
542 gs->dist = cur_dist + 1;
544 DEBUG("%p at %i,%i %i away", p, x, y, cur_dist);
545 if( pgs->firstdir == DIR_INVAL || (pgs->firstdir == dir && pgs->bDirect) ) {
548 gs->firstdist = pgs->firstdist + 1;
551 gs->firstdist = pgs->firstdist;
552 gs->firstdir = pgs->firstdir;
558 (*grid)[ Piece->X + Piece->Y * TARGET_GRID_W ].dist = -1;
562 for( int i = 0; i < TARGET_GRID_SIZE; i ++ )
564 int x = i % TARGET_GRID_W;
565 int y = i / TARGET_GRID_H;
566 struct sGridSlot *gs = &(*grid)[i];
568 struct sGridSlot *gs_u = NULL, *gs_d = NULL;
569 struct sGridSlot *gs_l = NULL, *gs_r = NULL;
571 if( !gs->dist ) continue ;
573 // Get adjacent cells
575 gs_u = &(*grid)[i - TARGET_GRID_W];
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];
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);
593 fprintf(stderr, "%p Type %c\n", Piece, cRANK_CHARS[Piece->Rank]);
594 for( int i = 0; i < 10*10; i ++ )
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
602 fprintf(stderr, " "); // Empty
603 else if( np == (void*)-1 )
604 fprintf(stderr, "."); // My team/block
606 fprintf(stderr, "X"); // Viable target!
608 fprintf(stderr, "\n");
612 DEBUG("Getting targets");
614 for( int i = 0; i < TARGET_GRID_SIZE; i ++ )
616 if( (*grid)[i].p == (void*)-1 )
619 DEBUG("Target (%i,%i) %p %i dist",
620 i%10, i/10, (*grid)[i].p, (*grid)[i].dist);
621 (*grid)[i].dist -= 1;
629 int GetBestMove(tPlayerStats *Attacker, tPlayerStats *Defender, tMove *Move, int Level)
631 // Avoid infinite recursion
632 if( Level == MAX_SEARCH_DEPTH ) return 1;
634 int best_score = INT_MIN;
636 tPiece *best_p = NULL;
637 tPiece *best_target = NULL;
640 // - Check possible moves
641 for( int i = 0; i < N_PIECES; i ++ )
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
652 if( p->Rank == RANK_BOMB || p->Rank == RANK_FLAG )
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 ;
660 // Find the best target of those
661 for( int j = 0; j < TARGET_GRID_SIZE; j ++ )
663 struct sGridSlot *gs = &grid[j];
664 if( !gs->p ) continue ;
666 int t_score = GetScore(p, gs->p);
669 if( gs->p == gLastMove_Target && p == gLastMove_Piece && giNumRepeatedMove > REPEAT_THRESHOLD)
671 REPEAT_MOVE_MODIFY(t_score);
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);
680 if( !bt_gs || t_score > bt_score ) {
686 DEBUG("p_score = %i, bt_score = %i", p_score, bt_score);
688 // Best move is towards that piece
689 if( best_move.dir == DIR_INVAL || best_score < p_score )
691 best_move.dir = bt_gs->firstdir;
694 best_move.dist = (p->Rank == RANK_SCOUT) ? bt_gs->firstdist : 1;
695 best_score = p_score;
697 best_target = bt_gs->p;
704 ASSERT(best_move.dir != DIR_INVAL);
707 if( ((Move->dir-1)^1) == gLastMove.dir-1 && Move->dist == gLastMove.dist
708 && Move->x == gLastMove.x && Move->y == gLastMove.y )
710 giNumRepeatedMove ++;
711 DEBUG("Up to %i repititions", giNumRepeatedMove);
714 giNumRepeatedMove = 0;
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.
720 gLastMove_Target = best_target;
721 gLastMove_Piece = best_p;
722 giTurnsSinceLastTake ++;
725 DEBUG("best_score = %i", best_score);
733 int GetScore(tPiece *This, tPiece *Target)
735 tPlayerStats *attacker, *defender;
738 if( This->Team == gMyColour ) {
739 defender = &gpCurrentGameState->Opponent;
740 attacker = &gpCurrentGameState->MyExposed;
743 attacker = &gpCurrentGameState->Opponent;
744 defender = &gpCurrentGameState->MyExposed;
747 score = GetRawScore(This, Target);
749 if( This->Team == gMyColour )
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] )
757 case RANK_GENERAL: // General always attacks!
761 score = score * gpCurrentGameState->MyActual.nRanks[RANK_SCOUT] / MAX_RANK_COUNTS[RANK_SCOUT] + score;
771 int GetRawScore(tPiece *This, tPiece *Target)
773 tPlayerStats *this_team, *target_team;
775 ASSERT( This->Team != Target->Team );
777 if( This->Team == gMyColour ) {
778 target_team = &gpCurrentGameState->Opponent;
779 this_team = &gpCurrentGameState->MyExposed;
782 this_team = &gpCurrentGameState->Opponent;
783 target_team = &gpCurrentGameState->MyExposed;
786 // Both ranks known, used fixed rules
787 if( This->Rank != RANK_UNKNOWN && Target->Rank != RANK_UNKNOWN )
789 return GetOutcome(This->Rank, Target->Rank);
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
797 return GetOutcome(This->Rank, Target->GuessedRank);
802 int max = Target->bHasMoved ? RANK_SPY : RANK_FLAG;
805 if( target_team->nIdentified >= target_team->nPieces ) {
806 DEBUG("%i >= %i, what the fsck",
807 target_team->nIdentified, target_team->nPieces);
809 ASSERT(target_team->nPieces > target_team->nIdentified);
811 for( int i = RANK_MARSHAL; i <= max; i ++ )
813 int n_unk = MAX_RANK_COUNTS[i] - (target_team->nRanks[i] + target_team->nKilledRanks[i]);
818 // TODO: Fiddle with outcome score depending on respective ranks
819 sum += n_unk * GetOutcome(This->Rank, i);
823 // if( Target->bHasMoved )
824 // sum /= target_team->nPieces - target_team->nMoved;
826 // sum /= target_team->nPieces - target_team->nIdentified;
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 );
835 return sum - ABS(sum) / 10;
839 static inline int GetOutcome(int Attacker, int Defender)
841 if( Attacker == 0 ) return OC_UNK;
842 if( Defender == 0 ) return OC_UNK;
844 if( Defender == RANK_FLAG )
847 if( Attacker != RANK_MINER && Defender == RANK_BOMB )
849 if( Attacker == RANK_MINER && Defender == RANK_BOMB )
852 if( Attacker == RANK_SPY && Defender == RANK_MARSHAL )
855 if( Attacker == Defender )
858 if( Attacker < Defender )
865 static inline int ABS(int Val)
867 return Val < 0 ? -Val : Val;
870 static inline int RANGE(int Min, int Val, int Max)
872 return Min <= Val && Val <= Max;