My bot for the chain reaction game.

chain_reaction_bot.cpp

/*
	Chain reaction bot for Create 202
	Author: Siddhant Kushwaha
*/


#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <time.h>

using namespace std;

int turn = 1;

int m = 0, n = 0;
vector<vector<pair<int, int>>>* board = nullptr;

int maxSinkCapacity = 0;

#define val(i, j) board->at(i).at(j).first
#define typ(i, j) board->at(i).at(j).second

void printBoard()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << val(i, j) << "(" << typ(i, j) << ") ";
		}
		cout << "\n";
	}
}

inline int getCellType(int i, int j)
{
	int type = 0;
	if (i == 0 && j == 0)									// top left
		type = 1;
	else if (i == 0 && j == n - 1)							// top right
		type = 1;
	else if (i == m - 1 && j == 0)							// bottom left
		type = 1;
	else if (i == m - 1 && j == n - 1)						// bottom right
		type = 1;
	else if (i == 0 || i == m - 1 || j == 0 || j == n - 1)  // edge
		type = 2;

	return type;
}

inline int getCriticalMass(int i, int j)
{
	int criticalMass = 4;
	switch (getCellType(i, j))
	{
	case 0:
		criticalMass = 4;
		break;
	case 1:
		criticalMass = 2;
		break;
	case 2:
		criticalMass = 3;
		break;
	default:
		break;
	}
	return criticalMass;
}

inline bool isUnstable(int i, int j)
{
	return abs(val(i, j)) >= getCriticalMass(i, j);
}

inline bool inBounds(int i, int j)
{
	return i > -1 && j > -1 && i < m && j < n;
}

void updateCell(int srcI, int srcJ, int i, int j, int color)
{
	if (!inBounds(i, j))
		return;

	if (typ(i, j) == 0)
	{
		val(i, j) = color * (abs(val(i, j)) + 1);
	}
	// matching sink cell
	else if (typ(i, j) == color)
	{
		if (abs(val(i, j)) < maxSinkCapacity)
		{
			val(i, j) += color;
		}
		else
		{
			val(srcI, srcJ) += color;
		}
	}
	// non-matching sink cell
	else
	{
		if (abs(val(i, j)) < maxSinkCapacity)
		{
			// abosorbs but does not increase counter for opponent
		}
		else
		{
			val(srcI, srcJ) += color;
		}
	}
}

vector<pair<int, int>> getValidNeighbors(int i, int j)
{
	vector<pair<int, int>> list;
	if (inBounds(i - 1, j))
		list.push_back(make_pair(i - 1, j)); // N
	if (inBounds(i, j + 1))
		list.push_back(make_pair(i, j + 1)); // E
	if (inBounds(i + 1, j))
		list.push_back(make_pair(i + 1, j)); // S
	if (inBounds(i, j - 1))
		list.push_back(make_pair(i, j - 1)); // W
	return list;
}

void explode(int i, int j)
{
	// this shouldn't happen but for safety
	if (val(i, j) == 0)
		return;

	// 1 -> me, -1 -> opponent
	int color = val(i, j) / abs(val(i, j));
	val(i, j) = color * (abs(val(i, j)) - getCriticalMass(i, j));

	for (auto p : getValidNeighbors(i, j))
		updateCell(i, j, p.first, p.second, color);
}

int processBoardOnce()
{
	int rc = 0;

	vector<pair<int, int>> unstableCells;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (typ(i, j) == 0 && isUnstable(i, j))
			{
				unstableCells.push_back(make_pair(i, j));
			}
		}
	}

	for (auto p : unstableCells)
	{
		explode(p.first, p.second);
		rc = 1;
	}

	//printBoard();
	//cout << "-----------------------------\n\n";

	return rc;
}

inline void processBoard()
{
	int count = 0;
	while (processBoardOnce())
	{
		if (count > 10000)
		{
			cout << "Infinite loop detected.\n";
			exit(1);
		}
		count++;
	}
}

void computeScoreForBlocks(int& score)
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (val(i, j) > 0)
			{
				if (typ(i, j) == 0)
				{
					if (abs(val(i, j)) >= getCriticalMass(i, j) - 1)
					{
						int l = 0;

						stack<pair<int, int>> visit;
						visit.push(make_pair(i, j));

						int count = 0;

						while (!visit.empty())
						{
							if (count > 10000)
							{
								cout << "Infinite loop detected in chain detection.\n";
								exit(1);
							}

							auto p = visit.top();
							visit.pop();

							val(p.first, p.second) = 0;

							l++;

							for (auto n : getValidNeighbors(p.first, p.second))
							{
								//cout << n.first << " " << n.second << "\n";

								if (val(n.first, n.second) > 0)
								{
									if (typ(n.first, n.second) == 0)
									{
										if (abs(val(n.first, n.second)) >= getCriticalMass(n.first, n.second) - 1)
										{
											visit.push(n);
										}
									}
									else
									{
										// sink cell
										if(val(n.first, n.second) < maxSinkCapacity)
											score += 2;
									}
								}
							}

							count++;
						}

						if (l > 1)
							score += l * 3;
					}
				}
			}
		}
	}
}

int getScore()
{
	int scoreVulnerability = 5;
	int scoreCloseToSink = 10;
	int scoreIsSafeInCorner = 3;
	int scoreIsSafeOnEdge = 2;
	int scoreIsUnstable = 2;

	int totalOrbs = 0, opponentOrbs = 0;

	int totalScore = 0;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (val(i, j) > 0)
			{
				if (typ(i, j) == 0)
				{
					totalOrbs += val(i, j);

					bool isSafe = true;

					for (auto p : getValidNeighbors(i, j))
					{
						if (val(p.first, p.second) < 0) // opponent cell
						{
							if (typ(p.first, p.second) == 0)
							{
								// at critical or one more orb for critical
								if (abs(val(p.first, p.second)) >= getCriticalMass(p.first, p.second) - 1)
								{
									// ?? critical mass of i,j or p ??
									totalScore -= scoreVulnerability - getCriticalMass(p.first, p.second);

									isSafe = false;
								}
							}
							else
							{
								// opponent's sink cell

								// eats our orbs, might not be good for us
								// if (val(p.first, p.second) >= maxSinkCapacity)
									// totalScore -= 5;

								// reflects our balls, is it benefetial to us ?
							}
						}
						else // it's us
						{
							if (typ(p.first, p.second) == 0)
							{
								// normal cells
							}
							else
							{
								// if they can absorb, it's probably a good thing
								if (val(p.first, p.second) < maxSinkCapacity)
									totalScore += scoreCloseToSink;
							}
						}
					}

					if (isSafe)
					{
						// edges and corner heuristic
						switch (getCellType(i, j))
						{
						case 1: // corner
							totalScore += scoreIsSafeInCorner;
							break;
						case 2: //edge
							totalScore += scoreIsSafeOnEdge;
							break;
						default:
							break;
						}

						// unstability
						if (abs(val(i, j)) >= getCriticalMass(i, j) - 1)
							totalScore += scoreIsUnstable;
					}
				}
				else
				{
					// sink cell scoring
					totalOrbs += val(i, j);
				}
			}
			else
			{
				if (typ(i, j) == 0)
				{
					opponentOrbs += abs(val(i, j));
				}
				else
				{
					// sink cell scoring
					opponentOrbs += abs(val(i, j));
				}
			}
		}
	}

	totalScore += totalOrbs;

	if (opponentOrbs == 0 && totalOrbs > 0)
		return 99999999;
	else if (totalOrbs == 0 && opponentOrbs > 0)
		return -99999999;

	// contiguous block heuristic
	computeScoreForBlocks(totalScore);
	
	return totalScore;
}

void reverseBoard()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			val(i, j) = -1 * val(i, j);
			typ(i, j) = -1 * typ(i, j);
		}
	}
}

pair<int, int> makeMoveByScore(int level, int& score)
{
	vector<pair<int, int>> possibleMoves;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (typ(i, j) == 0 && val(i, j) >= 0)
			{
				possibleMoves.push_back(make_pair(i, j));
			}
		}
	}

	auto bestMove = make_pair(0, 0);

	if (possibleMoves.size() == 0)
		return bestMove;

	auto originalBoard = board;

	int maxScore = -99999999;

	for (auto move : possibleMoves)
	{
		board = new vector<vector<pair<int, int>>>(m, vector<pair<int, int>>(n, make_pair(0, 0)));

		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				board->at(i).at(j) = originalBoard->at(i).at(j);

		val(move.first, move.second)++;
		processBoard();

		int boardScore = getScore();

		
		if (level == 0)
		{
			reverseBoard();

			int score2 = 0;
			makeMoveByScore(1, score2);

			boardScore = boardScore - score2;
		}
		else if (level == 1)
		{
			// nothing to be done here
		}

		if (boardScore > maxScore) 
		{
			maxScore = boardScore;
			bestMove = move;
		}

		delete board;
	}

	score = maxScore;

	board = originalBoard;

	return bestMove;
}

pair<int, int> makeMove()
{
	// return makeRandomMove();

	int sc = 0;
	return makeMoveByScore(0, sc);
}

int main()
{
	while (true)
	{
		string command;
		cin >> command;

		if (command == "BOARD_INIT")
		{
			cin >> m >> n;
			board = new vector<vector<pair<int, int>>>(m, vector<pair<int, int>>(n, make_pair(0, 0)));

			cout << 0 << "\n";
		}
		else if (command == "YOUR_SINK")
		{
			int x, y;
			cin >> x >> y;

			typ(x, y) = 1;

			cout << 0 << "\n";
		}
		else if (command == "OPPONENT_SINK")
		{
			int x, y;
			cin >> x >> y;

			typ(x, y) = -1;

			cout << 0 << "\n";
		}
		else if (command == "MAX_CAPACITY")
		{
			cin >> maxSinkCapacity;

			cout << 0 << "\n";
		}
		else if (command == "MAKE_MOVE")
		{
			// make a move
			auto move = makeMove();
			val(move.first, move.second)++;

			processBoard();

			cout << move.first << " " << move.second << "\n";
		}
		else if (command == "OPPONENT_MOVE")
		{
			int i, j;
			cin >> i >> j;

			val(i, j)--;
			processBoard();

			auto move = makeMove();
			val(move.first, move.second)++;
			processBoard();

			cout << move.first << " " << move.second << "\n";
		}
		else if (command == "VALIDATE_BOARD")
		{
			vector<vector<int>> validBoard(m, vector<int>(n, 0));

			int color = 1;
			cin >> color;

			int rc = 0;

			for (int i = 0; i < m; i++)
			{
				for (int j = 0; j < n; j++)
				{
					cin >> validBoard[i][j];
					validBoard[i][j] *= color;
					if (validBoard[i][j] != val(i, j))
						rc = 1;
				}
			}

			cout << rc << "\n";
		}
		else
		{
			// command not recognized
		}

		//printBoard();
	}
}