Ryan Goldsmith

For Decision Theory we were tasked to create a chess ai which would make the best possible moves and prevent blundering. For example the AI must recognise that taking pieces may not be the best move if it costs them more valuable pieces.
The MiniMax algorithm has been utilised however throughout the project I researched into other algorithms and attempted to implement them For example the NegaMax algorithm is more suitable in a chess ai as it cuts the codebase down a considerable amount.
To also increase the performance of the algorithm and reduce the overall speed it takes to come to a decision

int ChessPlayer::AlphaBeta(Board* board, int depth, bool maximisingPlayer, int alpha, int beta)
{
	if (depth == 0)
	{
		//cout << "+++++++++++++++++++++" << endl;
		//PrintBoard(board);
		return EvaluateBoard(board, m_colour);
	}

	if (maximisingPlayer)
	{
		int maxEval = -100000000;
		vecPieces vPieces;
		unsigned int piecesAvailable = getAllLivePiecesOnTeamOnBoard(vPieces, m_colour, board);
		// For every valid move
		for (int currentPiece = 0; currentPiece < vPieces.size(); currentPiece++)
		{
			alpha = -100000000;
			beta = 100000000;
			vector> avaliableMoves = getValidMovesForPiece(board, vPieces[currentPiece]);

			for (int currentMove = 0; currentMove < avaliableMoves.size(); currentMove++)
			{
				// Apply move
				int rowStart = avaliableMoves[currentMove].get()->getOriginPosition().first;
				int colStart = avaliableMoves[currentMove].get()->getOriginPosition().second;
				int rowFin = avaliableMoves[currentMove].get()->getDestinationPosition().first;
				int colFin = avaliableMoves[currentMove].get()->getDestinationPosition().second;

				std::shared_ptr removedPiece;
				if (board->getSquare(rowFin, colFin)->occupiedState())
				{
					removedPiece = board->getSquare(rowFin, colFin)->getOccupyingPiece();
					board->getSquare(rowFin, colFin)->removeOccupyingPiece();
				}
				board->getSquare(rowStart, colStart)->removeOccupyingPiece();
				board->getSquare(rowFin, colFin)->occupySquare(vPieces[currentPiece].piece);
				
				int currentEval = AlphaBeta(board, depth - 1, false, alpha, beta);
				
				// Revert move
				board->getSquare(rowStart, colStart)->occupySquare(vPieces[currentPiece].piece);
				board->getSquare(rowFin, colFin)->removeOccupyingPiece();
				if (removedPiece != nullptr)
				{
					board->getSquare(rowFin, colFin)->occupySquare(removedPiece);
				}
				
				//cout << "Piece: " << currentPiece << " Move: " << currentMove << " Score: " << currentEval << endl;

				if (currentEval > maxEval)
				{
					//cout << "Piece: " << currentPiece << " Move: " << currentMove << endl;
					maxEval = currentEval;
					m_bestMove.move = avaliableMoves[currentMove];
					m_bestMoves.clear();
					m_bestMoves.push_back(avaliableMoves[currentMove]);
				}

				if (currentEval == maxEval)
				{
					m_bestMoves.push_back(avaliableMoves[currentMove]);
				}

				alpha = max(alpha, maxEval);
				
				if (maxEval > beta)
				{
					//cout << "Pruned" << endl;
					break;
				}
			}
		}
		return maxEval;
	}
	else
	{
		int minEval = 100000000;
		vecPieces vPieces;
		unsigned int piecesAvailable = getAllLivePiecesOnTeamOnBoard(vPieces, m_opposingColour, board);
		// For every valid move
		for (int currentPiece = 0; currentPiece < vPieces.size(); currentPiece++)
		{
			//cout << "Next piece" << endl;
			vector> avaliableMoves = getValidMovesForPiece(board, vPieces[currentPiece]);

			for (int currentMove = 0; currentMove < avaliableMoves.size(); currentMove++)
			{
				// Apply move
				int rowStart = avaliableMoves[currentMove].get()->getOriginPosition().first;
				int colStart = avaliableMoves[currentMove].get()->getOriginPosition().second;
				int rowFin = avaliableMoves[currentMove].get()->getDestinationPosition().first;
				int colFin = avaliableMoves[currentMove].get()->getDestinationPosition().second;

				std::shared_ptr removedPiece;
				if (board->getSquare(rowFin, colFin)->occupiedState())
				{
					removedPiece = board->getSquare(rowFin, colFin)->getOccupyingPiece();
					board->getSquare(rowFin, colFin)->removeOccupyingPiece();
				}
				board->getSquare(rowStart, colStart)->removeOccupyingPiece();
				board->getSquare(rowFin, colFin)->occupySquare(vPieces[currentPiece].piece);

				int currentEval = AlphaBeta(board, depth - 1, false, alpha, beta);
				
				// Revert move
				board->getSquare(rowStart, colStart)->occupySquare(vPieces[currentPiece].piece);
				board->getSquare(rowFin, colFin)->removeOccupyingPiece();
				if (removedPiece != nullptr)
				{
					board->getSquare(rowFin, colFin)->occupySquare(removedPiece);
				}

				if (currentEval < minEval)
				{
					//cout << "Piece: " << currentPiece << " Move: " << currentMove << endl;
					minEval = currentEval;
					//m_bestMove.move = avaliableMoves[currentMove];
				}

				beta = min(beta, minEval);

				if (minEval < alpha)
				{
					//cout << "Pruned" << endl;
					break;
				}
			}
		}
		return minEval;
	}
}
					

For the Evolutionary Algorithms project our task was to implement a genetic algorithm into the application to achieve a score of 190+ in the game.
The Genetic Algorithms initial population is created through random values and then run, each different solution will have its own fitness and this is what is used to determine which solutions are chosen within the generation of the next population.
To add some variation to the algorithm to prevent the algorithm converging too quickly I implemented mutation. The mutation is a small chance and it mutates some of the genes of the chromosome. To show how the genetic algorithm is layed out within my code I created a diagram. One gene is a tower and the information a tower holds, and a chromosome is a list of these genes to create a final solution

void Population::GenerateNextPopulation()
{
	// Firstly lets order the chromosomes based on their performance and give them a rank
	SortChromosomes();
	
	m_lastGenerationBest = m_Chromosomes.back();

	// Now we should give these chromosomes their ranks
	// We are giving them ranks as Ranked selection gives stronger chromosomes than roulettwheel
	for (int i = 0; i < m_Chromosomes.size(); i++)
	{
		m_Chromosomes[i]->SetRank(i + 1);
	}

	vector nextPopulation;
	// Elitism - allows for a stronger next generation
	Chromosome* bestChromosome = m_Chromosomes.back();
	bestChromosome->SetCurrentGene(0);
	bestChromosome->Print();

	nextPopulation.push_back(bestChromosome);

	// Now we've given them ranks lets do reproduction to create the next population
	for (int i = 0; i < m_Chromosomes.size()-1; i += 2)
	{
		Chromosome* parent1 = RouletteWheelSelection();
		Chromosome* parent2 = RouletteWheelSelection();

		while (parent1 == parent2)
		{
			parent2 = RouletteWheelSelection();
		}

		Chromosome* offspring1 = Reproduce(parent1, parent2);
		Chromosome* offspring2 = Reproduce(parent2, parent1);

		// now that we have some children lets add some mutation
		int mutationRoll1 = AIController::GenerateRandomNum(0, 100);
		if (mutationRoll1 <= m_iMutationChance)
		{
			offspring1 = Mutate(offspring1);
		}
		nextPopulation.push_back(offspring1);

		int mutationRoll2 = AIController::GenerateRandomNum(0, 100);
		if (mutationRoll2 <= m_iMutationChance)
		{
			offspring2 = Mutate(offspring2);
		}
		if (1 != m_Chromosomes.size() -1)
		{
			nextPopulation.push_back(offspring2);
		}
	}

	//Swap the populations over
	m_Chromosomes.clear();
	cout << nextPopulation.size() << endl;
	for (int i = 0; i < nextPopulation.size(); i++)
	{
		m_Chromosomes.push_back(nextPopulation[i]);
	}
	m_iGenerationCount++;
}

Chromosome* Population::Reproduce(Chromosome* parent1, Chromosome* parent2)
{
	// time to create a offspring from 2 parents

	Chromosome* offspring = new Chromosome();

	for (int i = 0; i < parent1->GetGeneCount(); i += 2)
	{
		offspring->AddGene(parent1->GetGeneAt(i));
		// Only add the gene if we have space
		if (i != parent1->GetGeneCount() - 1)
		{
			offspring->AddGene(parent2->GetGeneAt(i+1));
		}
	}

	return offspring;
}

Chromosome* Population::Mutate(Chromosome* c)
{
	Chromosome* returnChromosome = new Chromosome();
	for (int i = 0; i < c->GetGeneCount(); i++)
	{
		returnChromosome->AddGene(c->GetGeneAt(i));
	}

	int mutationTypeRoll = AIController::GenerateRandomNum(1, 5);

	if (mutationTypeRoll == 1)
	{
		cout << "Swap Mutation" << endl;
		// Swap mutation
		int randomIndex1 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		int randomIndex2 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);

		// make sure indexs are different
		while (randomIndex1 == randomIndex2)
		{
			randomIndex2 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		}

		cout << randomIndex1 << " " << randomIndex2 << endl;
		Gene temp;
		temp = returnChromosome->GetGeneAt(randomIndex1);
		returnChromosome->SetGeneAt(randomIndex1, returnChromosome->GetGeneAt(randomIndex2));
		returnChromosome->SetGeneAt(randomIndex2, temp);

		return returnChromosome;
	}
	else if (mutationTypeRoll == 2)
	{
		cout << "Reverse Mutation" << endl;
		// Reverse Mutation
		int randomIndex1 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		int randomIndex2 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		
		// make sure indexs are different
		while (randomIndex1 == randomIndex2)
		{
			randomIndex2 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		}

		// make sure random number 1 is smaller
		if (randomIndex2 < randomIndex1)
		{
			int temp = randomIndex1;
			randomIndex1 = randomIndex2;
			randomIndex2 = temp;
		}

		// Get section to flip
		vector selectedGenes;
		for (int i = randomIndex1; i < randomIndex2; i++)
		{
			selectedGenes.push_back(returnChromosome->GetGeneAt(i));
		}

		// Perform flip
		int n = selectedGenes.size() - 1;
		for (int i = randomIndex1; i < randomIndex2; i++)
		{
			returnChromosome->SetGeneAt(i, selectedGenes[n]);
			n--;
		}

		return returnChromosome;
	}
	else
	{
		cout << "Reverse Random" << endl;
		// Random Mutation
		int randomIndex1 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		int randomIndex2 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		cout << randomIndex1 << endl;
		cout << randomIndex2 << endl;

		// make sure indexs are different
		while (randomIndex1 == randomIndex2)
		{
			randomIndex2 = AIController::GenerateRandomNum(0, c->GetGeneCount() - 1);
		}

		Gene tp;
		tp.x = AIController::GenerateRandomNum(0, 25);
		tp.y = AIController::GenerateRandomNum(0, 17);
		tp.towerType = (TowerType)(AIController::GenerateRandomNum(1, 3));

		// Add the gene to the Chromosome
		returnChromosome->SetGeneAt(randomIndex1, tp);

		tp.x = AIController::GenerateRandomNum(0, 25);
		tp.y = AIController::GenerateRandomNum(0, 17);
		tp.towerType = (TowerType)(AIController::GenerateRandomNum(1, 3));
		returnChromosome->SetGeneAt(randomIndex2, tp);
		
		return returnChromosome;
	}
}

Chromosome* Population::RankSelection()
{
	Chromosome* selectedChromosome = new Chromosome();
	int maxWheelSize = 0;
	for (int i = 0; i < m_Chromosomes.size(); i++)
	{
		maxWheelSize += m_Chromosomes[i]->GetRank();
	}

	int selectedNum = AIController::GenerateRandomNum(1, maxWheelSize-1);
	int wheelTotal = 0;
	for (int i = 0; i < m_Chromosomes.size(); i++)
	{
		wheelTotal += m_Chromosomes[i]->GetRank();

		if (wheelTotal > selectedNum)
		{
			selectedChromosome = m_Chromosomes[i];
			break;
		}
	}

	return selectedChromosome;
}