forfax.cpp 21.7 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
20
21
#include "forfax.h"

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

using namespace std;

Sam Moore's avatar
Sam Moore committed
22
23
24



Sam Moore's avatar
Sam Moore committed
25
/**
Sam Moore's avatar
Sam Moore committed
26
27
 * 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
28
29
30
31
32
 */

char  Piece::tokens[] = {'.','+','F','y','s','n','S','L','c','m','C','G','M','B','?'};


Sam Moore's avatar
Sam Moore committed
33
34
35
36
37
38
39
40
41
/**
 * 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
42
43
44


/**
Sam Moore's avatar
Sam Moore committed
45
 * Constructor for a piece of unknown rank
Sam Moore's avatar
Sam Moore committed
46
47
48
49
50
 * @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
51
	: x(newX), y(newY), colour(newColour), minRank(Piece::FLAG), maxRank(Piece::BOMB), lastMove(0)
Sam Moore's avatar
Sam Moore committed
52
{
Sam Moore's avatar
Sam Moore committed
53

Sam Moore's avatar
Sam Moore committed
54
55
56
}

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






/**
Sam Moore's avatar
Sam Moore committed
76
 * HELPER - Returns the Piece::Type matching a given character
Sam Moore's avatar
Sam Moore committed
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 * @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
98
	//Construct 2D array of Piece*'s
Sam Moore's avatar
Sam Moore committed
99
100
101
102
103
104
105
106
107
108
109
110
111
112
	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
113
	//Destroy the 2D array of Piece*'s
Sam Moore's avatar
Sam Moore committed
114
115
116
117
118
119
120
121
122
	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
123
 * Retrieve a piece from the board at specified coordinates
Sam Moore's avatar
Sam Moore committed
124
125
126
127
128
129
 * @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
130
	if (board == NULL || x < 0 || y < 0 || x >= width || y >= height)
Sam Moore's avatar
Sam Moore committed
131
132
133
134
135
136
137
138
139
140
		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
141
 * @returns newPiece if the piece was successfully added, NULL if it was not (ie invalid coordinates specified)
Sam Moore's avatar
Sam Moore committed
142
143
144
145
 *
 */
Piece * Board::Set(int x, int y, Piece * newPiece)
{
Sam Moore's avatar
Sam Moore committed
146
	if (board == NULL || x < 0 || y < 0 || x >= width || y >= height)
Sam Moore's avatar
Sam Moore committed
147
148
149
150
151
152
153
154
155
156
157
158
159
		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
160
 * HELPER - Convert a string to a direction
Sam Moore's avatar
Sam Moore committed
161
 * @param str - The string to convert to a direction
Sam Moore's avatar
Sam Moore committed
162
 * @returns The equivalent Direction
Sam Moore's avatar
Sam Moore committed
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 */
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
179
 * HELPER - Convert a Direction to a string
Sam Moore's avatar
Sam Moore committed
180
 * @param dir - the Direction to convert
Sam Moore's avatar
Sam Moore committed
181
 * @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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 */
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
207
 * HELPER - Translates the given coordinates in a specified direction
Sam Moore's avatar
Sam Moore committed
208
209
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
 * @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
236
 * HELPER - Returns the best direction to move in to get from one point to another
Sam Moore's avatar
Sam Moore committed
237
238
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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
 * @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;

	

	
}

/**
 * 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;
	for (vector<Piece*>::iterator i=in.begin(); i != in.end(); ++i)
	{
		
		if ((*i) == forget)
		{
			i = in.erase(i);
			result = true;
			
			continue;
		}
		
		
	}

	
	return result;
}

/**
Sam Moore's avatar
Sam Moore committed
301
 * Construct the Forfax AI
Sam Moore's avatar
Sam Moore committed
302
303
304
 */
Forfax::Forfax() : board(NULL), colour(Piece::NONE), strColour("NONE"), turnNumber(0)
{
Sam Moore's avatar
Sam Moore committed
305
	//By default, Forfax knows nothing; the main function in main.cpp calls Forfax's initialisation functions
Sam Moore's avatar
Sam Moore committed
306
307
308
309
310
311
312
313
314
315
316
317
318
319
}

/**
 * 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
320
321
322
323
 * 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
324
325
 */

Sam Moore's avatar
Sam Moore committed
326
double Forfax::CombatSuccessChance(Piece * attacker, Piece * defender) const
Sam Moore's avatar
Sam Moore committed
327
328
{
	double probability=1;
Sam Moore's avatar
Sam Moore committed
329
	for (Piece::Type aRank = attacker->minRank; aRank <= attacker->maxRank; aRank = (Piece::Type)((int)(aRank) + 1))
Sam Moore's avatar
Sam Moore committed
330
	{
Sam Moore's avatar
Sam Moore committed
331
332
		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
333
334
		{
			if (dRank < aRank)
Sam Moore's avatar
Sam Moore committed
335
				lesserRanks += remainingUnits[defender->colour][(int)(dRank)];
Sam Moore's avatar
Sam Moore committed
336
			else if (dRank > aRank)
Sam Moore's avatar
Sam Moore committed
337
				greaterRanks += remainingUnits[defender->colour][(int)(dRank)];
Sam Moore's avatar
Sam Moore committed
338
339
340
341
342
343
344
345
346
347
348
			else
			{
				lesserRanks++; greaterRanks++;
			}
		}
		probability *= lesserRanks/(lesserRanks + greaterRanks);
	}
	return probability;
}

/**
Sam Moore's avatar
Sam Moore committed
349
350
 * Calculate the score of a move
 * TODO: Alter this to make it better
Sam Moore's avatar
Sam Moore committed
351
352
 * @param piece - The Piece to move
 * @param dir - The direction in which to move
Sam Moore's avatar
Sam Moore committed
353
 * @returns a number between 0 and 1, indicating how worthwhile the move is
Sam Moore's avatar
Sam Moore committed
354
 */
Sam Moore's avatar
Sam Moore committed
355
double Forfax::MovementScore(Piece * piece, const Board::Direction & dir) const
Sam Moore's avatar
Sam Moore committed
356
{
Sam Moore's avatar
Sam Moore committed
357
358
359
	assert(piece != NULL);

	
Sam Moore's avatar
Sam Moore committed
360
361
362
	int x2 = piece->x; int y2 = piece->y;
	Board::MoveInDirection(x2, y2, dir);

Sam Moore's avatar
Sam Moore committed
363
	
Sam Moore's avatar
Sam Moore committed
364

Sam Moore's avatar
Sam Moore committed
365
366
	double basevalue;
	if (!board->ValidPosition(x2, y2) || !piece->Mobile())
Sam Moore's avatar
Sam Moore committed
367
	{
Sam Moore's avatar
Sam Moore committed
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
		
		basevalue = 0;
	}
	else if (board->Get(x2, y2) == NULL)
	{
		basevalue = 0.5*IntrinsicWorth(x2, y2);
		
	}
	else if (board->Get(x2, y2)->colour != Piece::Opposite(piece->colour))
	{
		basevalue = 0;
	}
	else 
	{
		Piece * defender = board->Get(x2, y2);
		double combatSuccess = CombatSuccessChance(piece, defender);
		basevalue = IntrinsicWorth(x2, y2)*combatSuccess*VictoryScore(piece, defender) + (1.0 - combatSuccess)*DefeatScore(piece, defender);
Sam Moore's avatar
Sam Moore committed
385
386
	}

Sam Moore's avatar
Sam Moore committed
387
388
389
390
391
392
393
	if (basevalue > 0)
	{
		double oldValue = basevalue;
		basevalue -= (double)(1.0/((double)(1.0 + (turnNumber - piece->lastMove))));
		if (basevalue < oldValue/8.0)
			basevalue = oldValue/8.0;
	}
Sam Moore's avatar
Sam Moore committed
394
	
Sam Moore's avatar
Sam Moore committed
395
	return basevalue;
Sam Moore's avatar
Sam Moore committed
396
397
398
399
}


/**
Sam Moore's avatar
Sam Moore committed
400
401
402
 * 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
403
 */
Sam Moore's avatar
Sam Moore committed
404
Forfax::Status Forfax::Setup()
Sam Moore's avatar
Sam Moore committed
405
406
{
	//The first line is used to identify Forfax's colour, and the size of the board
Sam Moore's avatar
Sam Moore committed
407
408
409
410
411
412
413
	//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
414
415
416
417
418
	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
419
		return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
420
	
Sam Moore's avatar
Sam Moore committed
421
	//Determine Forfax's colour and respond with an appropriate setup
Sam Moore's avatar
Sam Moore committed
422
423
424
	if (strColour == "RED")
	{
		colour = Piece::RED;
Sam Moore's avatar
Sam Moore committed
425
426
427
428
		cout <<  "FBmSsnsnBn\n";
		cout << "BBCMccccyC\n";
		cout << "LSGmnsBsSm\n";
		cout << "sLSBLnLsss\n";
Sam Moore's avatar
Sam Moore committed
429
430
431
432
	}
	else if (strColour == "BLUE")
	{
		colour = Piece::BLUE;
Sam Moore's avatar
Sam Moore committed
433
434
435
436
		cout << "sLSBLnLsss\n";	
		cout << "LSGmnsBsSm\n";
		cout << "BBCMccccyC\n";
		cout <<  "FBmSsnsnBn\n";		
Sam Moore's avatar
Sam Moore committed
437
438
	}
	else
Sam Moore's avatar
Sam Moore committed
439
		return INVALID_QUERY;
Sam Moore's avatar
Sam Moore committed
440
441


Sam Moore's avatar
Sam Moore committed
442
443
444
445
	//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
446
	board = new Board(boardWidth, boardHeight);
Sam Moore's avatar
Sam Moore committed
447
448
449
	if (board == NULL)
		return BOARD_ERROR;
	return OK;
Sam Moore's avatar
Sam Moore committed
450
451
452
}

/**
Sam Moore's avatar
Sam Moore committed
453
454
455
456
457
458
459
 * 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
460
 */
Sam Moore's avatar
Sam Moore committed
461
Forfax::Status Forfax::MakeMove()
Sam Moore's avatar
Sam Moore committed
462
463
{
	++turnNumber;
Sam Moore's avatar
Sam Moore committed
464
	
Sam Moore's avatar
Sam Moore committed
465
466
	if (turnNumber == 1)
	{
Sam Moore's avatar
Sam Moore committed
467
468
469
		Status firstMove = MakeFirstMove();
		if (firstMove != OK)
			return firstMove;
Sam Moore's avatar
Sam Moore committed
470
471
472
	}
	else
	{
Sam Moore's avatar
Sam Moore committed
473
474
475
		//Read and interpret the result of the previous move
		Status interpret = InterpretMove();
		if (interpret != OK) {return interpret;}
Sam Moore's avatar
Sam Moore committed
476
477

		//Forfax ignores the board state; he only uses the move result lines
Sam Moore's avatar
Sam Moore committed
478
		
Sam Moore's avatar
Sam Moore committed
479
480
481
482
483
		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
484
				return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
485
		}
Sam Moore's avatar
Sam Moore committed
486
		
Sam Moore's avatar
Sam Moore committed
487
488
	}
	
Sam Moore's avatar
Sam Moore committed
489
490
491
492
493
494
495
496
	//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
497
498
499
	vector<Piece*> & allies = board->GetPieces(colour);
	for (vector<Piece*>::iterator i = allies.begin(); i != allies.end(); ++i)
	{
Sam Moore's avatar
Sam Moore committed
500
501
502
503
		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
504
505
506

	}
	
Sam Moore's avatar
Sam Moore committed
507
508
509
510
511
512
513
514
515
	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
516
517
	cout << choice.piece->x << " " << choice.piece->y << " " << direction << "\n";

Sam Moore's avatar
Sam Moore committed
518
519
	

Sam Moore's avatar
Sam Moore committed
520

Sam Moore's avatar
Sam Moore committed
521
522
523

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

Sam Moore's avatar
Sam Moore committed
526
527
528
529
	

}

Sam Moore's avatar
Sam Moore committed
530
531
532
533
534
535
/**
 * 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
536
{
Sam Moore's avatar
Sam Moore committed
537
538
539
	//Variables to store move information
	int x; int y; string direction; string result = ""; int multiplier = 1; int attackerVal = (int)(Piece::BOMB); int defenderVal = (int)(Piece::BOMB);

Sam Moore's avatar
Sam Moore committed
540

Sam Moore's avatar
Sam Moore committed
541
	//Read in information from stdin
Sam Moore's avatar
Sam Moore committed
542
	cin >> x; cin >> y; cin >> direction; cin >> result;
Sam Moore's avatar
Sam Moore committed
543
544

	//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
545
546
	if (cin.peek() != '\n')
	{
Sam Moore's avatar
Sam Moore committed
547
548
549
550
551
		string buf = "";		
		stringstream s(buf);
		cin >> buf;
		s.clear(); s.str(buf);
		s >> attackerVal;
552

Sam Moore's avatar
Sam Moore committed
553
554
555
556
557
558
559

		buf.clear();
		cin >> buf;	
		s.clear(); s.str(buf);
		s >> defenderVal;

		
Sam Moore's avatar
Sam Moore committed
560
	}
Sam Moore's avatar
Sam Moore committed
561
562
563
564
	
	//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
565
566
	if (cin.get() != '\n')
	{
Sam Moore's avatar
Sam Moore committed
567
		return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
568
569
	}

Sam Moore's avatar
Sam Moore committed
570
571

	//Convert printed ranks into internal Piece::Type ranks
572
573
574
	Piece::Type attackerRank = Piece::Type(Piece::BOMB - attackerVal);
	Piece::Type defenderRank = Piece::Type(Piece::BOMB - defenderVal);

Sam Moore's avatar
Sam Moore committed
575
576


Sam Moore's avatar
Sam Moore committed
577
	//Work out the square moved into
Sam Moore's avatar
Sam Moore committed
578
579
580
581
582
	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
583
584

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

Sam Moore's avatar
Sam Moore committed
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604

	//If ranks were supplied, update the known ranks of the involved pieces
	if (attackerRank != Piece::NOTHING && attacker != NULL)
	{
		assert(attacker->minRank <= attackerRank && attacker->maxRank >= attackerRank);
		attacker->minRank = attackerRank;
		attacker->maxRank = attackerRank;
	}
	if (defenderRank != Piece::NOTHING && defender != NULL)
	{
		assert(defender->minRank <= defenderRank && defender->maxRank >= defenderRank);
		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
605
	if (attacker == NULL)
Sam Moore's avatar
Sam Moore committed
606
		return EXPECTED_ATTACKER;
Sam Moore's avatar
Sam Moore committed
607
608


Sam Moore's avatar
Sam Moore committed
609
610
611
612
613
614
615
616
	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
617
618
	if (multiplier > 1)
	{
Sam Moore's avatar
Sam Moore committed
619
620
		attacker->maxRank = Piece::SCOUT;
		attacker->minRank = Piece::SCOUT;
Sam Moore's avatar
Sam Moore committed
621
622
623
624
625
	}




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

Sam Moore's avatar
Sam Moore committed
628

Sam Moore's avatar
Sam Moore committed
629
	//The move was uneventful (attacker moved into empty square)
Sam Moore's avatar
Sam Moore committed
630
631
632
	if (result == "OK")
	{
		if (defender != NULL)
Sam Moore's avatar
Sam Moore committed
633
634
635
			return UNEXPECTED_DEFENDER;

		//Update board and piece
Sam Moore's avatar
Sam Moore committed
636
637
638
639
640
		board->Set(x2, y2, attacker);
		board->Set(x, y, NULL);
		attacker->x = x2;
		attacker->y = y2;
	}
Sam Moore's avatar
Sam Moore committed
641
	else if (result == "KILLS") //The attacking piece killed the defending piece
Sam Moore's avatar
Sam Moore committed
642
643
	{
		if (defender == NULL || defender->colour == attacker->colour)
Sam Moore's avatar
Sam Moore committed
644
			return COLOUR_MISMATCH;
Sam Moore's avatar
Sam Moore committed
645
646
647
648
649
650
651
652
653


		

		board->Set(x2, y2, attacker);
		board->Set(x, y, NULL);
		attacker->x = x2;
		attacker->y = y2;

Sam Moore's avatar
Sam Moore committed
654
		remainingUnits[(int)(defender->colour)][(int)(defenderRank)]--;
Sam Moore's avatar
Sam Moore committed
655
656
657
		

		if (!board->ForgetPiece(defender))
Sam Moore's avatar
Sam Moore committed
658
			return NO_DEFENDER;
Sam Moore's avatar
Sam Moore committed
659
660
661
		delete defender;

	}
Sam Moore's avatar
Sam Moore committed
662
	else if (result == "DIES") //The attacking piece was killed by the defending piece
Sam Moore's avatar
Sam Moore committed
663
664
665
	{
		
		if (defender == NULL || defender->colour == attacker->colour)
Sam Moore's avatar
Sam Moore committed
666
667
668
669
			return COLOUR_MISMATCH;

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

Sam Moore's avatar
Sam Moore committed
670
		if (!board->ForgetPiece(attacker))
Sam Moore's avatar
Sam Moore committed
671
			return NO_ATTACKER;
Sam Moore's avatar
Sam Moore committed
672
673
674
675
		delete attacker;

		board->Set(x, y, NULL);
	}
Sam Moore's avatar
Sam Moore committed
676
	else if (result == "BOTHDIE") //Both attacking and defending pieces died
Sam Moore's avatar
Sam Moore committed
677
678
	{
		if (defender == NULL || defender->colour == attacker->colour)
Sam Moore's avatar
Sam Moore committed
679
680
681
682
683
			return COLOUR_MISMATCH;

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

Sam Moore's avatar
Sam Moore committed
684
		if (board->ForgetPiece(attacker) == false)
Sam Moore's avatar
Sam Moore committed
685
			return NO_ATTACKER;
Sam Moore's avatar
Sam Moore committed
686
		if (board->ForgetPiece(defender) == false)
Sam Moore's avatar
Sam Moore committed
687
			return NO_DEFENDER;
Sam Moore's avatar
Sam Moore committed
688
689
690
691
692
		delete attacker;
		delete defender;
		board->Set(x2, y2, NULL);
		board->Set(x, y, NULL);
	}
Sam Moore's avatar
Sam Moore committed
693
	else if (result == "VICTORY") //The attacking piece captured a flag
Sam Moore's avatar
Sam Moore committed
694
	{
Sam Moore's avatar
Sam Moore committed
695
696
		return VICTORY; 
		
Sam Moore's avatar
Sam Moore committed
697
	}
Sam Moore's avatar
Sam Moore committed
698
	return OK;
Sam Moore's avatar
Sam Moore committed
699
700
701
}

/**
Sam Moore's avatar
Sam Moore committed
702
703
704
 * 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
705
706
 *
 */
Sam Moore's avatar
Sam Moore committed
707
Forfax::Status Forfax::MakeFirstMove()
Sam Moore's avatar
Sam Moore committed
708
709
710
711
712
713
{
	if (colour == Piece::RED)
	{
		string derp;
		cin >> derp;
		if (derp != "START")
Sam Moore's avatar
Sam Moore committed
714
			return INVALID_QUERY;
Sam Moore's avatar
Sam Moore committed
715
		if (cin.get() != '\n')
Sam Moore's avatar
Sam Moore committed
716
			return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
717
718
719
720
721
722
723
724
725
726
727
728
729
730
	}
	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
731
				case '.': //Empty square
Sam Moore's avatar
Sam Moore committed
732
					break;
Sam Moore's avatar
Sam Moore committed
733
734
				case '+': //Boulder/Obstacle
					board->Set(x, y, new Piece(x, y, Piece::NONE, Piece::BOULDER));
Sam Moore's avatar
Sam Moore committed
735
					break;
Sam Moore's avatar
Sam Moore committed
736
				case '#': //Enemy piece occupies square
Sam Moore's avatar
Sam Moore committed
737
738
739
740
741
742
743
				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
744
				default: //Allied piece occupies square
Sam Moore's avatar
Sam Moore committed
745
746
				{
					Piece::Type type = Piece::GetType(c);
Sam Moore's avatar
Sam Moore committed
747
					Piece * toAdd = new Piece(x, y, colour, type);
Sam Moore's avatar
Sam Moore committed
748
749
750
751
752
753
754
					board->Set(x, y, toAdd);
					board->GetPieces(toAdd->colour).push_back(toAdd);
					break;
				}
			}
		}
		if (cin.get() != '\n')
Sam Moore's avatar
Sam Moore committed
755
			return NO_NEWLINE;
Sam Moore's avatar
Sam Moore committed
756
757
	}
	
Sam Moore's avatar
Sam Moore committed
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
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
	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
{
	if (defender->minRank == defender->maxRank)
	{
		if (defender->minRank == Piece::FLAG)
			return 1;
		else if (defender->minRank == Piece::BOMB)
			return 0.9;
	}
	return max<double>(((defender->maxRank / Piece::BOMB) + (defender->minRank / Piece::BOMB))/2, 0.6);
}

/**
 * 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
{
	if (attacker->minRank == Piece::SPY)
		return 0.05;

	if (defender->minRank == defender->maxRank)
	{
		if (defender->minRank == Piece::BOMB)
			return 1 - (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
		else
			return 0.5;
	}

	double possibleRanks = 0; double totalRanks = 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 (totalRanks > 0)
		return (possibleRanks/totalRanks) - (double)((double)(attacker->minRank) / (double)(Piece::BOMB));
	return 0;
}		

/**
 * 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
887
888
889
890
}

//EOF