forfax.cpp 26.9 KB
Newer Older
Sam Moore's avatar
Sam Moore committed
1
2
3
4
5
6
7
8
9
/**
 * "forfax", a sample Stratego AI for the UCC Programming Competition 2012
 * Implementations of classes Piece, Board and Forfax
 * @author Sam Moore (matches) [SZM]
 * @website http://matches.ucc.asn.au/stratego
 * @email [email protected] or [email protected]
 * @git git.ucc.asn.au/progcomp2012.git
 */

Sam Moore's avatar
Sam Moore committed
10
11
12
13
14
15
16
17
18
19
#include "forfax.h"

#include <cstdlib>
#include <sstream>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <cmath>

Sam Moore's avatar
Sam Moore committed
20
21
//#define DEBUG

Sam Moore's avatar
Sam Moore committed
22
23
using namespace std;

Sam Moore's avatar
Sam Moore committed
24
25
26



Sam Moore's avatar
Sam Moore committed
27
/**
Sam Moore's avatar
Sam Moore committed
28
29
 * The characters used to represent various pieces
 * NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
Sam Moore's avatar
Sam Moore committed
30
31
 */

32
char  Piece::tokens[] = {'.','*','F','s','9','8','7','6','5','4','3','2','1','B','?'};
Sam Moore's avatar
Sam Moore committed
33
34


Sam Moore's avatar
Sam Moore committed
35
36
37
38
39
40
41
42
43
/**
 * The number of units remaining for each colour
 * Accessed by [COLOUR][TYPE]
 * COLOUR: RED, BLUE
 * TYPE: NOTHING, BOULDER, FLAG, SPY, SCOUT, MINER, SERGEANT, LIETENANT, CAPTAIN, MAJOR, COLONEL, GENERAL, MARSHAL, BOMB, ERROR
 */
int Forfax::remainingUnits[][15] = {{0,0,1,1,8,5,4,4,4,3,2,1,1,6,0},{0,0,1,1,8,5,4,4,4,3,2,1,1,6,0}};


Sam Moore's avatar
Sam Moore committed
44
45
46


/**
Sam Moore's avatar
Sam Moore committed
47
 * Constructor for a piece of unknown rank
Sam Moore's avatar
Sam Moore committed
48
49
50
51
52
 * @param newX - x coord
 * @param newY - y coord
 * @param newColour - colour
 */
Piece::Piece(int newX, int newY,const Colour & newColour)
Sam Moore's avatar
Sam Moore committed
53
	: x(newX), y(newY), colour(newColour), minRank(Piece::FLAG), maxRank(Piece::BOMB), lastMove(0), lastx(newX), lasty(newY)
Sam Moore's avatar
Sam Moore committed
54
{
Sam Moore's avatar
Sam Moore committed
55

Sam Moore's avatar
Sam Moore committed
56
57
58
}

/**
Sam Moore's avatar
Sam Moore committed
59
 * Constructor for a piece of known rank
Sam Moore's avatar
Sam Moore committed
60
61
62
 * @param newX - x coord
 * @param newY - y coord
 * @param newColour - colour
Sam Moore's avatar
Sam Moore committed
63
 * @param fixedRank - rank of the new piece
Sam Moore's avatar
Sam Moore committed
64
 */
Sam Moore's avatar
Sam Moore committed
65
Piece::Piece(int newX, int newY,const Colour & newColour, const Type & fixedRank)
Sam Moore's avatar
Sam Moore committed
66
	: x(newX), y(newY), colour(newColour), minRank(fixedRank), maxRank(fixedRank), lastMove(0),  lastx(newX), lasty(newY)
Sam Moore's avatar
Sam Moore committed
67
{
Sam Moore's avatar
Sam Moore committed
68
	
Sam Moore's avatar
Sam Moore committed
69
70
71
72
73
74
75
76
77
	
}






/**
Sam Moore's avatar
Sam Moore committed
78
 * HELPER - Returns the Piece::Type matching a given character
Sam Moore's avatar
Sam Moore committed
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 * @param token - The character to match
 * @returns A Piece::Type corresponding to the character, or Piece::ERROR if none was found
 */
Piece::Type Piece::GetType(char token)
{
	for (int ii=0; ii < Piece::ERROR; ++ii)
	{
		if (Piece::tokens[ii] == token)
			return (Type)(ii);
	}
	return Piece::ERROR;
}

/**
 * Constructor for the board
 * @param newWidth - width of the board
 * @param newHeight - height of the board
 *
 */
Board::Board(int newWidth, int newHeight) : width(newWidth), height(newHeight), board(NULL), red(), blue()
{
Sam Moore's avatar
Sam Moore committed
100
	//Construct 2D array of Piece*'s
Sam Moore's avatar
Sam Moore committed
101
102
103
104
105
106
107
108
109
110
111
112
113
114
	board = new Piece**[width];
	for (int x=0; x < width; ++x)
	{
		board[x] = new Piece*[height];
		for (int y=0; y < height; ++y)
			board[x][y] = NULL;
	}
}

/**
 * Destroy the board
 */
Board::~Board()
{
Sam Moore's avatar
Sam Moore committed
115
	//Destroy the 2D array of Piece*'s
Sam Moore's avatar
Sam Moore committed
116
117
118
119
120
121
122
123
124
	for (int x=0; x < width; ++x)
	{
		for (int y=0; y < height; ++y)
			delete board[x][y];
		delete [] board[x];
	}
}

/**
Sam Moore's avatar
Sam Moore committed
125
 * Retrieve a piece from the board at specified coordinates
Sam Moore's avatar
Sam Moore committed
126
127
128
129
130
131
 * @param x - x coord of the piece
 * @param y - y coord of the piece
 * @returns Piece* to the piece found at (x,y), or NULL if there was no piece, or the coords were invalid
 */
Piece * Board::Get(int x, int y) const
{
Sam Moore's avatar
Sam Moore committed
132
	if (board == NULL || x < 0 || y < 0 || x >= width || y >= height)
Sam Moore's avatar
Sam Moore committed
133
134
135
136
137
138
139
140
141
142
		return NULL;
	return board[x][y];
}

/**
 * Add a piece to the board
 *	Also updates the red or blue arrays if necessary
 * @param x - x coord of the piece
 * @param y - y coord of the piece
 * @param newPiece - pointer to the piece to add
Sam Moore's avatar
Sam Moore committed
143
 * @returns newPiece if the piece was successfully added, NULL if it was not (ie invalid coordinates specified)
Sam Moore's avatar
Sam Moore committed
144
145
146
147
 *
 */
Piece * Board::Set(int x, int y, Piece * newPiece)
{
Sam Moore's avatar
Sam Moore committed
148
	if (board == NULL || x < 0 || y < 0 || x >= width || y >= height)
Sam Moore's avatar
Sam Moore committed
149
150
151
152
153
154
155
156
157
158
159
160
161
		return NULL;
	board[x][y] = newPiece;

	//if (newPiece->GetColour() == Piece::RED)
	//	red.push_back(newPiece);
	//else if (newPiece->GetColour() == Piece::BLUE)
	//	blue.push_back(newPiece);

	return newPiece;
}


/**
Sam Moore's avatar
Sam Moore committed
162
 * HELPER - Convert a string to a direction
Sam Moore's avatar
Sam Moore committed
163
 * @param str - The string to convert to a direction
Sam Moore's avatar
Sam Moore committed
164
 * @returns The equivalent Direction
Sam Moore's avatar
Sam Moore committed
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 */
Board::Direction Board::StrToDir(const string & str)
{
	if (str == "UP")
		return UP;
	else if (str == "DOWN")
		return DOWN;
	else if (str == "LEFT")
		return LEFT;
	else if (str == "RIGHT")
		return RIGHT;

	return NONE;
}

/**
Sam Moore's avatar
Sam Moore committed
181
 * HELPER - Convert a Direction to a string
Sam Moore's avatar
Sam Moore committed
182
 * @param dir - the Direction to convert
Sam Moore's avatar
Sam Moore committed
183
 * @param str - A buffer string, which will contain the string representation of the Direction once this function returns.
Sam Moore's avatar
Sam Moore committed
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 */
void Board::DirToStr(const Direction & dir, string & str)
{
	str.clear();
	switch (dir)
	{
		case UP:
			str = "UP";
			break;
		case DOWN:
			str = "DOWN";
			break;
		case LEFT:
			str = "LEFT";
			break;
		case RIGHT:
			str = "RIGHT";
			break;
		default:
			str = "NONE";
			break;
	}
}

/**
Sam Moore's avatar
Sam Moore committed
209
 * HELPER - Translates the given coordinates in a specified direction
Sam Moore's avatar
Sam Moore committed
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
 * @param x - x coord
 * @param y - y coord
 * @param dir - Direction to move in
 * @param multiplier - Number of times to move
 *
 */
void Board::MoveInDirection(int & x, int & y, const Direction & dir, int multiplier)
{
	switch (dir)
	{
		case UP:
			y -= multiplier;
			break;
		case DOWN:
			y += multiplier;
			break;
		case LEFT:
			x -= multiplier;
			break;
		case RIGHT:
			x += multiplier;
			break;
		default:
			break;
	}
}

/**
Sam Moore's avatar
Sam Moore committed
238
 * HELPER - Returns the best direction to move in to get from one point to another
Sam Moore's avatar
Sam Moore committed
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
 * @param x1 - x coord of point 1
 * @param y1 - y coord of point 1
 * @param x2 - x coord of point 2
 * @param y2 - y coord of point 2
 * @returns The best direction to move in
 */
Board::Direction Board::DirectionBetween(int x1, int y1, int x2, int y2)
{


	double xDist = (x2 - x1);
	double yDist = (y2 - y1);
	if (abs(xDist) >= abs(yDist))
	{
		if (xDist < 0)
			return LEFT;
		else 
			return RIGHT;
	}
	else
	{
		if (yDist < 0)
			return UP;
		else
			return DOWN;
	}
	return NONE;

	

	
Sam Moore's avatar
Sam Moore committed
270
271
272
273
274
275
276
277
278
279
280
281
282
}

/**
 * HELPER - Returns the number of moves between two points
 * @param x1 x coordinate of the first point
 * @param y1 y coordinate of the first point
 * @param x2 x coordinate of the second point
 * @param y2 y coordinate of the second point
 * @returns The number of moves taken to progress from (x1, y1) to (x2, y2), assuming no obstacles
 */
int Board::NumberOfMoves(int x1, int y1, int x2, int y2)
{
	return (abs(x2 - x1) + abs(y2 - y1)); //Pieces can't move diagonally, so this is pretty straight forward
Sam Moore's avatar
Sam Moore committed
283
284
285
286
287
288
289
290
291
292
293
294
295
296
}

/**
 * Searches the board's red and blue arrays for the piece, and removes it
 * DOES NOT delete the piece. Calling function should delete piece after calling this function.
 * @param forget - The Piece to forget about
 * @returns true if the piece was actually found
 */
bool Board::ForgetPiece(Piece * forget)
{	
	if (forget == NULL)
		return false;
	
	vector<Piece*> & in = GetPieces(forget->colour); bool result = false;
Sam Moore's avatar
Sam Moore committed
297
298
	vector<Piece*>::iterator i=in.begin(); 
	while (i != in.end())
Sam Moore's avatar
Sam Moore committed
299
300
301
302
303
304
305
306
307
	{
		
		if ((*i) == forget)
		{
			i = in.erase(i);
			result = true;
			
			continue;
		}
Sam Moore's avatar
Sam Moore committed
308
		++i;
Sam Moore's avatar
Sam Moore committed
309
310
311
312
313
		
	}

	
	return result;
Sam Moore's avatar
Sam Moore committed
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
}

/**
 * Gets the closest Piece of a specified colour to a point
 * @param x The x coordinate of the point
 * @param y The y coordinate of the point
 * @param colour The colour that the piece must match (may be Piece::BOTH to match either colour)
 * @returns Piece* pointing to the closest piece of a matching colour, NULL if no piece found
 */
Piece * Board::GetClosest(int x, int y, const Piece::Colour & colour) const
{
	if (x < 0 || y < 0 || x >= width || y >= height)
		return NULL;

	for (int dist = 0; dist < max<int>(width, height); ++dist)
	{
		
		for (int yy = y-dist; yy <= y+dist; ++yy)
		{
			Piece * get = Get(x+dist, y);
			if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
				return get;
		}
		for (int yy = y-dist; yy <= y+dist; ++yy)
		{
			Piece * get = Get(x-dist, y);
			if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
				return get;
		}
		for (int xx = x-dist; xx <= x+dist; ++xx)
		{
			Piece * get = Get(xx, y+dist);
			if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
				return get;
		}
		for (int xx = x-dist; xx <= y+dist; ++xx)
		{
			Piece * get = Get(xx, y-dist);
			if ((get != NULL) && (get->colour == colour || colour == Piece::BOTH))
				return get;
		}

	}
	
	return NULL;
	
	
	
	
Sam Moore's avatar
Sam Moore committed
363
364
365
}

/**
Sam Moore's avatar
Sam Moore committed
366
 * Construct the Forfax AI
Sam Moore's avatar
Sam Moore committed
367
368
369
 */
Forfax::Forfax() : board(NULL), colour(Piece::NONE), strColour("NONE"), turnNumber(0)
{
Sam Moore's avatar
Sam Moore committed
370
	//By default, Forfax knows nothing; the main function in main.cpp calls Forfax's initialisation functions
Sam Moore's avatar
Sam Moore committed
371
	srand(time(NULL));
Sam Moore's avatar
Sam Moore committed
372
373
374
375
376
377
378
379
380
381
382
383
384
385
}

/**
 * Destroy Forfax
 */
Forfax::~Forfax()
{
	//fprintf(stderr,"Curse you mortal for casting me into the fires of hell!\n");
	//Errr...
	if (board != NULL)
		delete board;
}

/**
Sam Moore's avatar
Sam Moore committed
386
387
388
389
 * Calculate the probability that attacker beats defender in combat
 * @param attacker The attacking piece
 * @param defender The defending piece
 * @returns A double between 0 and 1 indicating the probability of success
Sam Moore's avatar
Sam Moore committed
390
391
 */

Sam Moore's avatar
Sam Moore committed
392
double Forfax::CombatSuccessChance(Piece * attacker, Piece * defender) const
Sam Moore's avatar
Sam Moore committed
393
394
{
	double probability=1;
Sam Moore's avatar
Sam Moore committed
395
	for (Piece::Type aRank = attacker->minRank; aRank <= attacker->maxRank; aRank = (Piece::Type)((int)(aRank) + 1))
Sam Moore's avatar
Sam Moore committed
396
	{
Sam Moore's avatar
Sam Moore committed
397
398
		double lesserRanks=0; double greaterRanks=0;
		for (Piece::Type dRank = defender->minRank; dRank <= defender->maxRank; dRank = (Piece::Type)((int)(dRank) + 1))
Sam Moore's avatar
Sam Moore committed
399
400
		{
			if (dRank < aRank)
Sam Moore's avatar
Sam Moore committed
401
				lesserRanks += remainingUnits[defender->colour][(int)(dRank)];
Sam Moore's avatar
Sam Moore committed
402
			else if (dRank > aRank)
Sam Moore's avatar
Sam Moore committed
403
				greaterRanks += remainingUnits[defender->colour][(int)(dRank)];
Sam Moore's avatar
Sam Moore committed
404
405
406
407
408
409
410
411
412
413
414
			else
			{
				lesserRanks++; greaterRanks++;
			}
		}
		probability *= lesserRanks/(lesserRanks + greaterRanks);
	}
	return probability;
}

/**
Sam Moore's avatar
Sam Moore committed
415
416
 * Calculate the score of a move
 * TODO: Alter this to make it better
Sam Moore's avatar
Sam Moore committed
417
418
 * @param piece - The Piece to move
 * @param dir - The direction in which to move
419
 * @returns a number between 0 and 1, indicating how worthwhile the move is, or a negative number (-1) if the move is illegal
Sam Moore's avatar
Sam Moore committed
420
 */
Sam Moore's avatar
Sam Moore committed
421
double Forfax::MovementScore(Piece * piece, const Board::Direction & dir) const
Sam Moore's avatar
Sam Moore committed
422
{
Sam Moore's avatar
Sam Moore committed
423
424
425
	assert(piece != NULL);

	
Sam Moore's avatar
Sam Moore committed
426
427
428
	int x2 = piece->x; int y2 = piece->y;
	Board::MoveInDirection(x2, y2, dir);

Sam Moore's avatar
Sam Moore committed
429
	
Sam Moore's avatar
Sam Moore committed
430

Sam Moore's avatar
Sam Moore committed
431
432
	double basevalue;
	if (!board->ValidPosition(x2, y2) || !piece->Mobile())
Sam Moore's avatar
Sam Moore committed
433
	{
Sam Moore's avatar
Sam Moore committed
434
		
435
		return -1; //No point attempting to move immobile units, or moving off the edges of the board
Sam Moore's avatar
Sam Moore committed
436
437
438
	}
	else if (board->Get(x2, y2) == NULL)
	{
Sam Moore's avatar
Sam Moore committed
439
440
441
442
443
444
445
446
447
		//If the position is empty...
		Piece * closestEnemy = board->GetClosest(x2, y2, Piece::Opposite(piece->colour));
		if (closestEnemy == NULL)
		{
			basevalue = 0.05*IntrinsicWorth(x2, y2); //Should never get this unless there are no enemies left
		}
		else
		{
			//Allocate score based on score of Combat with nearest enemy to the target square, decrease with distance between target square and the enemy
448
449
450
451
			double multiplier = (double)(max<int>(board->Width(), board->Height()) - Board::NumberOfMoves(closestEnemy->x, closestEnemy->y, x2, y2)) / (double)(max<int>(board->Width(), board->Height()));

			basevalue = CombatScore(closestEnemy->x, closestEnemy->y, piece)*multiplier*multiplier;

Sam Moore's avatar
Sam Moore committed
452
453
		}
		
Sam Moore's avatar
Sam Moore committed
454
455
456
457
		
	}
	else if (board->Get(x2, y2)->colour != Piece::Opposite(piece->colour))
	{
458
		return -1; //The position is occupied by an ally, and so its pointless to try and move there
Sam Moore's avatar
Sam Moore committed
459
460
461
	}
	else 
	{
Sam Moore's avatar
Sam Moore committed
462
		basevalue = CombatScore(x2, y2, piece); //The position is occupied by an enemy; compute combat score
463
		
Sam Moore's avatar
Sam Moore committed
464
465
	}

Sam Moore's avatar
Sam Moore committed
466
467
	if (basevalue > 0)
	{
Sam Moore's avatar
Sam Moore committed
468
469
		//Hack which decreases score for units that moved recently
		//Does not decrease below a threshold (so that at the start of the game units will actually move!)
Sam Moore's avatar
Sam Moore committed
470
471
		double oldValue = basevalue;
		basevalue -= (double)(1.0/((double)(1.0 + (turnNumber - piece->lastMove))));
Sam Moore's avatar
Sam Moore committed
472
473
		if (basevalue < oldValue/1000.0)
			basevalue = oldValue/1000.0;
Sam Moore's avatar
Sam Moore committed
474
	}
Sam Moore's avatar
Sam Moore committed
475
	
Sam Moore's avatar
Sam Moore committed
476
477

	if (x2 == piece->lastx && y2 == piece->lasty) //Hack which decreases score for backtracking moves
478
		basevalue = basevalue/100;
Sam Moore's avatar
Sam Moore committed
479
480
481
482
483

	if (rand() % 10 == 0) //Hack which introduces some randomness by boosting one in every 10 scores
		basevalue *= 4;
	if (basevalue > 1)
		basevalue = 1;
Sam Moore's avatar
Sam Moore committed
484
	return basevalue;
Sam Moore's avatar
Sam Moore committed
485
486
487
488
}


/**
Sam Moore's avatar
Sam Moore committed
489
490
491
 * Initialisation for Forfax
 * Reads information from stdin about the board, and Forfax's colour. Initialises board, and prints appropriate setup to stdout.
 * @returns true if Forfax was successfully initialised, false otherwise.
Sam Moore's avatar
Sam Moore committed
492
 */
Sam Moore's avatar
Sam Moore committed
493
Forfax::Status Forfax::Setup()
Sam Moore's avatar
Sam Moore committed
494
495
{
	//The first line is used to identify Forfax's colour, and the size of the board
Sam Moore's avatar
Sam Moore committed
496
497
498
499
500
501
502
	//Currently the name of the opponent is ignored.

	//Forfax then responds with a setup.
	//Forfax only uses one of two setups, depending on what colour he was assigned.
	
	
	//Variables to store information read from stdin
Sam Moore's avatar
Sam Moore committed
503
504
505
506
507
	strColour.clear();
	string strOpponent; int boardWidth; int boardHeight;

	cin >> strColour; cin >> strOpponent; cin >> boardWidth; cin >> boardHeight;
	if (cin.get() != '\n')
Sam Moore's avatar
Sam Moore committed
508
		return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
509
	
Sam Moore's avatar
Sam Moore committed
510
	//Determine Forfax's colour and respond with an appropriate setup
Sam Moore's avatar
Sam Moore committed
511
512
513
	if (strColour == "RED")
	{
		colour = Piece::RED;
514
515
516
517
		cout << "FB8sB479B8\n";
		cout << "BB31555583\n";
		cout << "6724898974\n";
		cout << "967B669999\n";
Sam Moore's avatar
Sam Moore committed
518
519
520
521
	}
	else if (strColour == "BLUE")
	{
		colour = Piece::BLUE;
522
523
524
525
		cout << "967B669999\n";	
		cout << "6724898974\n";
		cout << "BB31555583\n";
		cout << "FB8sB479B8\n";
Sam Moore's avatar
Sam Moore committed
526
527
	}
	else
Sam Moore's avatar
Sam Moore committed
528
		return INVALID_QUERY;
Sam Moore's avatar
Sam Moore committed
529
530


Sam Moore's avatar
Sam Moore committed
531
532
533
534
	//Create the board
	//NOTE: At this stage, the board is still empty. The board is filled on Forfax's first turn
	//	The reason for this is because the opponent AI has not placed pieces yet, so there is no point adding only half the pieces to the board
	
Sam Moore's avatar
Sam Moore committed
535
	board = new Board(boardWidth, boardHeight);
Sam Moore's avatar
Sam Moore committed
536
537
538
	if (board == NULL)
		return BOARD_ERROR;
	return OK;
Sam Moore's avatar
Sam Moore committed
539
540
541
}

/**
Sam Moore's avatar
Sam Moore committed
542
543
544
545
546
547
548
 * Make a single move
 * 1. Read result of previous move from stdin (or "START" if Forfax is RED and it is the very first move)
 * 2. Read in board state from stdin (NOTE: Unused - all information needed to maintain board state is in 1. and 4.)
 *	TODO: Considering removing this step from the protocol? (It makes debugging annoying because I have to type a lot more!)
 * 3. Print desired move to stdout
 * 4. Read in result of chosen move from stdin
 * @returns true if everything worked, false if there was an error or unexpected query
Sam Moore's avatar
Sam Moore committed
549
 */
Sam Moore's avatar
Sam Moore committed
550
Forfax::Status Forfax::MakeMove()
Sam Moore's avatar
Sam Moore committed
551
552
{
	++turnNumber;
Sam Moore's avatar
Sam Moore committed
553
	
Sam Moore's avatar
Sam Moore committed
554
555
	if (turnNumber == 1)
	{
Sam Moore's avatar
Sam Moore committed
556
557
558
		Status firstMove = MakeFirstMove();
		if (firstMove != OK)
			return firstMove;
Sam Moore's avatar
Sam Moore committed
559
560
561
	}
	else
	{
Sam Moore's avatar
Sam Moore committed
562
563
564
		//Read and interpret the result of the previous move
		Status interpret = InterpretMove();
		if (interpret != OK) {return interpret;}
Sam Moore's avatar
Sam Moore committed
565
566

		//Forfax ignores the board state; he only uses the move result lines
Sam Moore's avatar
Sam Moore committed
567
		#ifndef DEBUG
Sam Moore's avatar
Sam Moore committed
568
569
570
571
572
		for (int y=0; y < board->Height(); ++y)
		{
			for (int x = 0; x < board->Width(); ++x)
				cin.get();
			if (cin.get() != '\n')
Sam Moore's avatar
Sam Moore committed
573
				return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
574
		}
Sam Moore's avatar
Sam Moore committed
575
		#endif //DEBUG
Sam Moore's avatar
Sam Moore committed
576
		
Sam Moore's avatar
Sam Moore committed
577
578
	}
	
Sam Moore's avatar
Sam Moore committed
579
580
581
582
583
584
585
586
	//Now compute the best move
	// 1. Construct list of all possible moves
 	//	As each move is added to the list, a score is calculated for that move. 
	//	WARNING: This is the "tricky" part!
 	// 2. Sort the moves based on their score
	// 3. Simply use the highest scoring move!
	
	list<MovementChoice> choices;
Sam Moore's avatar
Sam Moore committed
587
588
589
	vector<Piece*> & allies = board->GetPieces(colour);
	for (vector<Piece*>::iterator i = allies.begin(); i != allies.end(); ++i)
	{
Sam Moore's avatar
Sam Moore committed
590
591
592
593
		choices.push_back(MovementChoice((*i), Board::UP, *this));
		choices.push_back(MovementChoice((*i), Board::DOWN, *this));
		choices.push_back(MovementChoice((*i), Board::LEFT, *this));
		choices.push_back(MovementChoice((*i), Board::RIGHT, *this));
Sam Moore's avatar
Sam Moore committed
594
595
596

	}
	
Sam Moore's avatar
Sam Moore committed
597
598
599
600
601
602
603
604
605
	choices.sort(); //Actually sort the choices!!!
	MovementChoice & choice = choices.back(); //The best one is at the back, because sort() sorts the list in ascending order
	
	

	//Convert information about the move into a printable form
	string direction;  Board::DirToStr(choice.dir, direction);

	//Print chosen move to stdout
Sam Moore's avatar
Sam Moore committed
606
607
	cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";

608
	//cerr << "\nForfax move " << choice.piece->x << " " << choice.piece->y << " " << direction << " [score = " << choice.score << "]\n";
Sam Moore's avatar
Sam Moore committed
609

Sam Moore's avatar
Sam Moore committed
610

Sam Moore's avatar
Sam Moore committed
611
612
613

	
	//Interpret the result of the chosen move
Sam Moore's avatar
Sam Moore committed
614
	return InterpretMove();
Sam Moore's avatar
Sam Moore committed
615

Sam Moore's avatar
Sam Moore committed
616
617
618
619
	

}

Sam Moore's avatar
Sam Moore committed
620
621
622
623
624
625
/**
 * Reads and interprets the result of a move
 * Reads information from stdin
 * @returns true if the result was successfully interpreted, false if there was a contradiction or error
 */
Forfax::Status Forfax::InterpretMove()
Sam Moore's avatar
Sam Moore committed
626
{
Sam Moore's avatar
Sam Moore committed
627
	//Variables to store move information
628
629
630
	int x; int y; string direction; string result = ""; int multiplier = 1; 
	Piece::Type attackerRank = Piece::NOTHING;
	Piece::Type defenderRank = Piece::NOTHING;
Sam Moore's avatar
Sam Moore committed
631

Sam Moore's avatar
Sam Moore committed
632
	//Read in information from stdin
Sam Moore's avatar
Sam Moore committed
633
	cin >> x; cin >> y; cin >> direction; cin >> result;
Sam Moore's avatar
Sam Moore committed
634
635

	//If necessary, read in the ranks of involved pieces (this happens if the outcome was DIES or KILLS or BOTHDIE)
Sam Moore's avatar
Sam Moore committed
636
637
	if (cin.peek() != '\n')
	{
Sam Moore's avatar
Sam Moore committed
638
639
640
641
		string buf = "";		
		stringstream s(buf);
		cin >> buf;
		s.clear(); s.str(buf);
642
643
644
		char temp;
		s >> temp;
		attackerRank = Piece::GetType(temp);
Sam Moore's avatar
Sam Moore committed
645
646
647
648

		buf.clear();
		cin >> buf;	
		s.clear(); s.str(buf);
649
650
		s >> temp;
		defenderRank = Piece::GetType(temp);
Sam Moore's avatar
Sam Moore committed
651
652

		
Sam Moore's avatar
Sam Moore committed
653
	}
Sam Moore's avatar
Sam Moore committed
654
655
656
657
	
	//TODO: Deal with move multipliers somehow (when a scout moves more than one space)

	//Check that the line ends where expected...
Sam Moore's avatar
Sam Moore committed
658
659
	if (cin.get() != '\n')
	{
Sam Moore's avatar
Sam Moore committed
660
		return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
661
662
	}

Sam Moore's avatar
Sam Moore committed
663

664
665

	
666

Sam Moore's avatar
Sam Moore committed
667
668


Sam Moore's avatar
Sam Moore committed
669
	//Work out the square moved into
Sam Moore's avatar
Sam Moore committed
670
671
672
673
674
	int x2 = x; int y2 = y;
	Board::Direction dir = Board::StrToDir(direction);

	Board::MoveInDirection(x2, y2, dir, multiplier);

Sam Moore's avatar
Sam Moore committed
675
676

	//Determine the attacker and defender (if it exists)
Sam Moore's avatar
Sam Moore committed
677
678
679
	Piece * attacker = board->Get(x, y);
	Piece * defender = board->Get(x2, y2);

Sam Moore's avatar
Sam Moore committed
680
681
682
683

	//If ranks were supplied, update the known ranks of the involved pieces
	if (attackerRank != Piece::NOTHING && attacker != NULL)
	{
Sam Moore's avatar
Sam Moore committed
684
		//assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
Sam Moore's avatar
Sam Moore committed
685
686
687
688
689
		attacker->minRank = attackerRank;
		attacker->maxRank = attackerRank;
	}
	if (defenderRank != Piece::NOTHING && defender != NULL)
	{
Sam Moore's avatar
Sam Moore committed
690
		//assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
Sam Moore's avatar
Sam Moore committed
691
692
693
694
695
696
		defender->minRank = defenderRank;
		defender->maxRank = defenderRank;

	}

	//There should always be an attacking piece (but not necessarily a defender)
Sam Moore's avatar
Sam Moore committed
697
	if (attacker == NULL)
Sam Moore's avatar
Sam Moore committed
698
		return EXPECTED_ATTACKER;
Sam Moore's avatar
Sam Moore committed
699
700


Sam Moore's avatar
Sam Moore committed
701
702
703
704
705
706
707
708
	attacker->lastMove = turnNumber; //Update stats of attacking piece (last move)

	//Eliminate certain ranks from the possibilities for the piece based on its movement
	//(This is useful if the piece was an enemy piece)
	if (attacker->minRank == Piece::FLAG)
		attacker->minRank = Piece::SPY;
	if (attacker->maxRank == Piece::BOMB)
		attacker->maxRank = Piece::MARSHAL;
Sam Moore's avatar
Sam Moore committed
709
710
	if (multiplier > 1)
	{
Sam Moore's avatar
Sam Moore committed
711
712
		attacker->maxRank = Piece::SCOUT;
		attacker->minRank = Piece::SCOUT;
Sam Moore's avatar
Sam Moore committed
713
714
715
716
717
	}




Sam Moore's avatar
Sam Moore committed
718
719
	//Now look at the result of the move (I wish you could switch strings in C++)

Sam Moore's avatar
Sam Moore committed
720

Sam Moore's avatar
Sam Moore committed
721
	//The move was uneventful (attacker moved into empty square)
Sam Moore's avatar
Sam Moore committed
722
723
724
	if (result == "OK")
	{
		if (defender != NULL)
Sam Moore's avatar
Sam Moore committed
725
726
727
			return UNEXPECTED_DEFENDER;

		//Update board and piece
Sam Moore's avatar
Sam Moore committed
728
729
		board->Set(x2, y2, attacker);
		board->Set(x, y, NULL);
Sam Moore's avatar
Sam Moore committed
730
731
		attacker->lastx = attacker->x;
		attacker->lasty = attacker->y;
Sam Moore's avatar
Sam Moore committed
732
733
734
		attacker->x = x2;
		attacker->y = y2;
	}
Sam Moore's avatar
Sam Moore committed
735
	else if (result == "KILLS") //The attacking piece killed the defending piece
Sam Moore's avatar
Sam Moore committed
736
737
	{
		if (defender == NULL || defender->colour == attacker->colour)
Sam Moore's avatar
Sam Moore committed
738
			return COLOUR_MISMATCH;
Sam Moore's avatar
Sam Moore committed
739
740
741
742
743
744


		

		board->Set(x2, y2, attacker);
		board->Set(x, y, NULL);
Sam Moore's avatar
Sam Moore committed
745
746
		attacker->lastx = attacker->x;
		attacker->lasty = attacker->y;
Sam Moore's avatar
Sam Moore committed
747
748
749
		attacker->x = x2;
		attacker->y = y2;

Sam Moore's avatar
Sam Moore committed
750
		remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
Sam Moore's avatar
Sam Moore committed
751
752
753
		

		if (!board->ForgetPiece(defender))
Sam Moore's avatar
Sam Moore committed
754
			return NO_DEFENDER;
Sam Moore's avatar
Sam Moore committed
755
756
757
		delete defender;

	}
Sam Moore's avatar
Sam Moore committed
758
	else if (result == "DIES") //The attacking piece was killed by the defending piece
Sam Moore's avatar
Sam Moore committed
759
760
761
	{
		
		if (defender == NULL || defender->colour == attacker->colour)
Sam Moore's avatar
Sam Moore committed
762
763
764
765
			return COLOUR_MISMATCH;

		remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;

Sam Moore's avatar
Sam Moore committed
766
		if (!board->ForgetPiece(attacker))
Sam Moore's avatar
Sam Moore committed
767
			return NO_ATTACKER;
Sam Moore's avatar
Sam Moore committed
768
769
770
771
		delete attacker;

		board->Set(x, y, NULL);
	}
Sam Moore's avatar
Sam Moore committed
772
	else if (result == "BOTHDIE") //Both attacking and defending pieces died
Sam Moore's avatar
Sam Moore committed
773
774
	{
		if (defender == NULL || defender->colour == attacker->colour)
Sam Moore's avatar
Sam Moore committed
775
776
777
778
779
			return COLOUR_MISMATCH;

		remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
		remainingUnits[(int)(attacker->colour)][(int)(attackerRank)]--;

Sam Moore's avatar
Sam Moore committed
780
		if (board->ForgetPiece(attacker) == false)
Sam Moore's avatar
Sam Moore committed
781
			return NO_ATTACKER;
Sam Moore's avatar
Sam Moore committed
782
		if (board->ForgetPiece(defender) == false)
Sam Moore's avatar
Sam Moore committed
783
			return NO_DEFENDER;
Sam Moore's avatar
Sam Moore committed
784
785
786
787
788
		delete attacker;
		delete defender;
		board->Set(x2, y2, NULL);
		board->Set(x, y, NULL);
	}
Sam Moore's avatar
Sam Moore committed
789
	else if (result == "VICTORY") //The attacking piece captured a flag
Sam Moore's avatar
Sam Moore committed
790
	{
Sam Moore's avatar
Sam Moore committed
791
792
		return VICTORY; 
		
Sam Moore's avatar
Sam Moore committed
793
	}
Sam Moore's avatar
Sam Moore committed
794
	return OK;
Sam Moore's avatar
Sam Moore committed
795
796
797
}

/**
Sam Moore's avatar
Sam Moore committed
798
799
800
 * Forfax's first move
 * Sets the state of the board
 * @returns true if the board was successfully read, false if an error occurred.
Sam Moore's avatar
Sam Moore committed
801
802
 *
 */
Sam Moore's avatar
Sam Moore committed
803
Forfax::Status Forfax::MakeFirstMove()
Sam Moore's avatar
Sam Moore committed
804
805
806
807
808
809
{
	if (colour == Piece::RED)
	{
		string derp;
		cin >> derp;
		if (derp != "START")
Sam Moore's avatar
Sam Moore committed
810
			return INVALID_QUERY;
Sam Moore's avatar
Sam Moore committed
811
		if (cin.get() != '\n')
Sam Moore's avatar
Sam Moore committed
812
			return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
813
814
815
816
817
818
819
820
821
822
823
824
825
826
	}
	else
	{
		//TODO: Fix hack where BLUE ignores RED's first move
		while (cin.get() != '\n');
	}
	
	for (int y=0; y < board->Height(); ++y)
	{
		for (int x = 0; x < board->Width(); ++x)	
		{
			char c = cin.get();
			switch (c)
			{
Sam Moore's avatar
Sam Moore committed
827
				case '.': //Empty square
Sam Moore's avatar
Sam Moore committed
828
					break;
Sam Moore's avatar
Sam Moore committed
829
830
				case '+': //Boulder/Obstacle
					board->Set(x, y, new Piece(x, y, Piece::NONE, Piece::BOULDER));
Sam Moore's avatar
Sam Moore committed
831
					break;
Sam Moore's avatar
Sam Moore committed
832
				case '#': //Enemy piece occupies square
Sam Moore's avatar
Sam Moore committed
833
834
835
836
837
838
839
				case '*':
				{
					Piece * toAdd = new Piece(x, y, Piece::Opposite(colour));
					board->Set(x, y, toAdd);
					board->GetPieces(toAdd->colour).push_back(toAdd);
					break;
				}
Sam Moore's avatar
Sam Moore committed
840
				default: //Allied piece occupies square
Sam Moore's avatar
Sam Moore committed
841
842
				{
					Piece::Type type = Piece::GetType(c);
Sam Moore's avatar
Sam Moore committed
843
					Piece * toAdd = new Piece(x, y, colour, type);
Sam Moore's avatar
Sam Moore committed
844
845
846
847
848
849
850
					board->Set(x, y, toAdd);
					board->GetPieces(toAdd->colour).push_back(toAdd);
					break;
				}
			}
		}
		if (cin.get() != '\n')
Sam Moore's avatar
Sam Moore committed
851
			return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
852
853
	}
	
Sam Moore's avatar
Sam Moore committed
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
	return OK;
}

/**
 * Calculates the intrinsic strategic worth of a point on the board
 * @param x the x coordinate of the point
 * @param y the y coordinate of the point
 * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 * (NOTE: No points will actually be worth 0)
 */
double Forfax::IntrinsicWorth(int x, int y) const
{
	static double intrinsicWorth[][10][10] =
	{
		//Red
		{
		{0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
		{0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
		{0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
		{0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
		{0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
		{0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
		{0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
		{0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
		{0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
		{0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7}


		},
		//Blue
		{
		{0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7},
		{0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
		{0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
		{0.6,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.7,0.6},
		{0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
		{0.6,0.6,0.1,0.1,0.65,0.65,0.1,0.1,0.6,0.6},
		{0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3},
		{0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2},
		{0.5,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1},
		{0.1,0.5,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1}
		}
	};

	return intrinsicWorth[(int)(colour)][x][y];
}

/**
 * Calculates a score assuming that attacker will beat defender, indicating how much killing that piece is worth
 * @param attacker the Attacking piece
 * @param defender the Defending piece
 * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 */
double Forfax::VictoryScore(Piece * attacker, Piece * defender) const
{
Sam Moore's avatar
Sam Moore committed
909
910

	//If defender's rank is known, flags or bombs are worth more than usual
Sam Moore's avatar
Sam Moore committed
911
912
913
914
915
916
917
	if (defender->minRank == defender->maxRank)
	{
		if (defender->minRank == Piece::FLAG)
			return 1;
		else if (defender->minRank == Piece::BOMB)
			return 0.9;
	}
Sam Moore's avatar
Sam Moore committed
918
	//Return average of normalised defender ranks
919
	return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 1);
Sam Moore's avatar
Sam Moore committed
920
921
922
923
924
925
926
927
928
929
}

/**
 * Calculates a score assuming that attacker will lose to defender, indicating how much learning the rank of that piece is worth
 * @param attacker the Attacking piece
 * @param defender the Defending piece
 * @returns a value between 0 and 1, with 0 indicating worthless and 1 indicating highly desirable
 */
double Forfax::DefeatScore(Piece * attacker, Piece * defender) const
{
Sam Moore's avatar
Sam Moore committed
930
931
932
	
	double result = 0;
	if (defender->minRank == defender->maxRank) //If the defender's rank is known for certain...
Sam Moore's avatar
Sam Moore committed
933
	{
Sam Moore's avatar
Sam Moore committed
934
935
936
937
		if (defender->minRank == Piece::BOMB) //Committing suicide to destroy bombs has a value that decreases with the attacker's rank
			result = 1 - 0.5*(double)((double)(attacker->minRank) / (double)(Piece::BOMB));
		else if (defender->minRank == Piece::FLAG)
			result = 1; //Its impossible to lose to the flag anyway...
Sam Moore's avatar
Sam Moore committed
938
		else
Sam Moore's avatar
Sam Moore committed
939
940
941
942
943
		{
			//This is committing suicide on a higher ranked non-bomb enemy piece.
			//Basically pointless, but the greater the attacker's rank the more pointless!
			double temp = (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
			result = 0.01*(1 - temp)*(1 - temp);
Sam Moore's avatar
Sam Moore committed
944

Sam Moore's avatar
Sam Moore committed
945
946
947
948
			
		}
	}	
	else //The defender's rank is not known
Sam Moore's avatar
Sam Moore committed
949
	{
Sam Moore's avatar
Sam Moore committed
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972

		//Score is allocated based on how much knowledge is gained by attacking defender
		//The more possible ranks for the defender, the greater the score
		//The score decreases as the rank of the attacker is increased.

		double possibleRanks = 0; double totalRanks = 0; double bonus = 0; 
		for (Piece::Type rank = Piece::NOTHING; rank <= Piece::BOMB; rank = Piece::Type((int)(rank) + 1))
		{
			totalRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];

			if (rank >= defender->minRank && rank <= defender->maxRank)
			{
				possibleRanks += remainingUnits[(int)(defender->colour)][(int)(rank)];
				if (rank == Piece::BOMB)
					bonus += remainingUnits[(int)(defender->colour)][(int)(rank)];
				if (rank == Piece::FLAG)
					bonus += 2*remainingUnits[(int)(defender->colour)][(int)(rank)];
			}
			
		}


		if (totalRanks > 0)
973
974
975
976
		{
			double multiplier = ((double)(Piece::BOMB) - (double)(attacker->minRank)) / (double)(Piece::BOMB);
			result = (possibleRanks/totalRanks) * multiplier * multiplier;
		}
Sam Moore's avatar
Sam Moore committed
977
978

		result += bonus / totalRanks;
Sam Moore's avatar
Sam Moore committed
979
		
Sam Moore's avatar
Sam Moore committed
980
981
		if (result > 1)
			result = 1;
Sam Moore's avatar
Sam Moore committed
982
983
	}

Sam Moore's avatar
Sam Moore committed
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
	if (attacker->minRank == Piece::SPY) //Spies are slightly more valuable than usual since they kill the Marshal
		result = result / 1.5;
	return result;

}

/**
 * Calculates a score indicating the worth of invoking combat in a square
 * @param x The x coordinate
 * @param y The y coordinate
 * @param attacker The piece invoking the combat
 * @returns A value between 0 in 1, with 0 indicating worthless (or no combat) and 1 indicating highest value
 */
double Forfax::CombatScore(int x, int y, Piece * attacker) const
{
	Piece * defender = board->Get(x, y);
	if (defender == NULL)
		return 0;
	double combatSuccess = CombatSuccessChance(attacker, defender);
	return IntrinsicWorth(x, y)*combatSuccess*VictoryScore(attacker, defender) + (1.0 - combatSuccess)*DefeatScore(attacker, defender);		
}
Sam Moore's avatar
Sam Moore committed
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036

/**
 * DEBUG - Print the board seen by Forfax to a stream
 * @param out The stream to print to
 */
void Forfax::PrintBoard(ostream & out)
{
	for (int y = 0; y < board->Height(); ++y)
	{
		for (int x = 0; x < board->Width(); ++x)
		{
			Piece * at = board->Get(x, y);
			if (at == NULL)
				out << ".";
			else
			{
				if (at->colour == colour)
				{
					out << Piece::tokens[(int)(at->minRank)];
				}
				else if (at->colour == Piece::Opposite(colour))
				{
					out << "#";
				}
				else
				{
					out << "+";
				}
			}
		}
		out << "\n";
	}
Sam Moore's avatar
Sam Moore committed
1037
1038
1039
1040
}

//EOF