fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <climits>
  6. #define INF 37
  7. using namespace std;
  8.  
  9. int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
  10. int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
  11.  
  12. int countFlipPieces(const string& gameboard, int player_color, string grid, int direction) {
  13. 	int count = 0;
  14. 	int x = grid[0] - 'A', y = grid[1] - 'a';
  15. 	int next_x = x + dx[direction], next_y = y + dy[direction];
  16. 	char opponent_color = (player_color == 1) ? 'O' : 'X';
  17.  
  18. 	while (next_x >= 0 && next_x < 6 && next_y >= 0 && next_y < 6 && gameboard[next_x * 6 + next_y] == opponent_color) {
  19. 		count++;
  20. 		next_x += dx[direction];
  21. 		next_y += dy[direction];
  22. 	}
  23.  
  24. 	if (next_x >= 0 && next_x < 6 && next_y >= 0 && next_y < 6 && gameboard[next_x * 6 + next_y] == (player_color == 1 ? 'X' : 'O')) {
  25. 		return count;
  26. 	}
  27.  
  28. 	return 0;
  29. }
  30.  
  31. int heuristicScore(const string& gameboard, int player_color) {
  32. 	int player_pieces = 0, opponent_pieces = 0;
  33. 	for (char c : gameboard) {
  34. 		if (c == (player_color == 1 ? 'X' : 'O')) {
  35. 			player_pieces++;
  36. 		}
  37. 		else if (c == (player_color == 1 ? 'O' : 'X')) {
  38. 			opponent_pieces++;
  39. 		}
  40. 	}
  41. 	return player_pieces - opponent_pieces;
  42. }
  43.  
  44. string flipPieces(string boardState, int currentPlayer, string position) {
  45. 	int row = position[0] - 'A', col = position[1] - 'a', piecesFlipped = 0;
  46. 	int rowOffset[8] = { -1, -1, 0, 1, 1, 1, 0, -1 }, colOffset[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
  47. 	char playerPiece = (currentPlayer == 1 ? 'X' : 'O');
  48.  
  49. 	for (int direction = 0; direction < 8; direction++) {
  50. 		int originalRow = row, originalCol = col;
  51. 		int piecesToFlip = countFlipPieces(boardState, currentPlayer, position, direction);
  52.  
  53. 		for (int i = 0; i < piecesToFlip; i++) {
  54. 			piecesFlipped = 1;
  55. 			row += rowOffset[direction], col += colOffset[direction];
  56. 			boardState[6 * row + col] = playerPiece;
  57. 		}
  58.  
  59. 		row = originalRow, col = originalCol;
  60. 	}
  61.  
  62. 	if (piecesFlipped) boardState[6 * row + col] = playerPiece;
  63. 	return boardState;
  64. }
  65.  
  66. int minimaxSearch(string boardState, int currentPlayer, int maxDepth, int depth = 0, int noPlayCount = 0, int alpha = -INF, int beta = INF) {
  67. 	string rows[6] = { "A", "B", "C", "D", "E", "F" }, cols[6] = { "a", "b", "c", "d", "e", "f" };
  68. 	int maxScore = -INF, minScore = INF, bestMove = 0, moveMade = 0;
  69.  
  70. 	if (depth == maxDepth) {
  71. 		return depth % 2 ? heuristicScore(boardState, ((currentPlayer - 1) ^ 1) + 1) : heuristicScore(boardState, currentPlayer);
  72. 	}
  73.  
  74. 	for (int i = 0; i < 36; i++) {
  75. 		if (boardState[i] != '+') continue;
  76. 		if (alpha >= beta) {
  77. 			return depth % 2 ? minScore : maxScore;
  78. 		}
  79.  
  80. 		int row = i / 6, col = i % 6;
  81. 		string newBoardState = flipPieces(boardState, currentPlayer, rows[row] + cols[col]);
  82. 		if (newBoardState == boardState) continue;
  83. 		moveMade = 1;
  84. 		noPlayCount = 0;
  85.  
  86. 		if (depth % 2) {
  87. 			int score = minimaxSearch(newBoardState, ((currentPlayer - 1) ^ 1) + 1, maxDepth, depth + 1, noPlayCount, alpha, beta);
  88. 			if (minScore > score) {
  89. 				beta = score;
  90. 				bestMove = i;
  91. 				minScore = score;
  92. 			}
  93. 		}
  94. 		else {
  95. 			int score = minimaxSearch(newBoardState, ((currentPlayer - 1) ^ 1) + 1, maxDepth, depth + 1, noPlayCount, alpha, beta);
  96. 			if (maxScore < score) {
  97. 				alpha = score;
  98. 				bestMove = i;
  99. 				maxScore = score;
  100. 			}
  101. 		}
  102. 	}
  103.  
  104. 	if (!moveMade) {
  105. 		if (noPlayCount == 1) {
  106. 			return depth % 2 ? heuristicScore(boardState, ((currentPlayer - 1) ^ 1) + 1) : heuristicScore(boardState, currentPlayer);
  107. 		}
  108. 		noPlayCount++;
  109. 		return minimaxSearch(boardState, ((currentPlayer - 1) ^ 1) + 1, maxDepth, depth + 1, noPlayCount, alpha, beta);
  110. 	}
  111.  
  112. 	if (depth == 0) {
  113. 		return bestMove;
  114. 	}
  115.  
  116. 	return depth % 2 ? minScore : maxScore;
  117. }
  118. string numToLetter(int num) {
  119. 	string letters = "ABCDEF";
  120. 	string nums = "abcdef";
  121. 	string letterCoords = "";
  122. 	letterCoords += letters[num / 6];
  123. 	letterCoords += nums[num % 6];
  124. 	return letterCoords;
  125. }
  126.  
  127. int main() {
  128. 	int num, dep, no_play, alpha = -INF, beta = INF;
  129. 	cin >> num;
  130. 	while (num--) {
  131. 		string state;
  132. 		int player, depth;
  133. 		cin >> state >> player >> depth;
  134. 		int a = minimaxSearch(state, player, depth, dep, no_play, alpha, beta);
  135. 		cout << numToLetter(a) << endl;
  136. 	}
  137. }
Success #stdin #stdout 0.05s 5304KB
comments (?)
stdin
copy 
6
OO++++XOOXXX+XOXX++OXXOO+XXOX++XXXX+
2
4
OO++++XOOXXX+XOXX++OXXOO+XXOX++XXXX+
2
6
OO++++XOOXXX+XOXX++OXXOO+XXOX++XXXX+
2
8
++++XOX+X+X+OOOOX+XOOOXOXOOOOXXO++++
1
4
++++XOX+X+X+OOOOX+XOOOXOXOOOOXXO++++
1
6
++++XOX+X+X+OOOOX+XOOOXOXOOOOXXO++++
1
8
stdout
copy 
Ad
Ff
Ca
Fc
Cf
Bd
https://ideone.com/sHM5q5
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!