Basic Information:
- Language: Java(100%)
- Project type: individual
- Made with: Eclipse.
Pentago is an abstract, advanced version of tic-tac-toe where you must get five pieces in a row. The Pentago game is divided into four blocks, each with nine possible places to move your piece. After placing the piece, you are able to rotate any of the four blocks either left or right, to sabotauge your opponent's play. In this version, you are playing against an AI. You pick to play with either the black or the white pieces and choose whether to go first or second, the AI will get what you don't choose.
Options:
Gameplay:
After choosing your initial options, you will see the empty block, empty spaces are marked with an asterik (*). Choose your block (1,2,3,4) by typing into the console, choose your spot (1,2,3,4,5,6,7,8,9), choose which block to rotate (1,2,3,4) and which direction to rotate it (L-left, R-right). You will also see utility printed to the screen followed by a numeric value. You can think of this as the game calculating your odds to win versus the AI's.
AI:
After every turn, the AI will take their turn. You will see the board after the AI makes their first move, and again after the AI makes their second move; rotating the board. The game will continue until either you or the AI wins by getting either 5 white tokens or 5 black tokens in a row (horizontally or vertically).
More:
- Note: top left is block 1, top right is block 2, bottom left is block 3, bottom right is block 4.
- Tip: if you see the AI putting too many pieces in a row, rotate their block to prevent them from winning.
- Note: the placements (1-9) in each block, go as follows
1 2 3
4 5 6
7 8 9 - Tip: The AI uses the utility value to make the best decisions on where to place a tile.
Code:
I have included snippets of my code below, featuring several implementations including my min-max algorithm, min-max algorithm with alpha beta pruning, and my utility calculations.
Min-Max
/**
* Method that utilizes min max algorithm
* @param board - current state of the board
* @param depth - current depth of tree (starts at 0)
* @param bCheck - controls flow in the four if statements
*/
private int miniMax(GameBoard board, int depth, int bCheck) {
nodeCount++;
winConditions getValue = new winConditions();
getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4());
//stop when we hit the max depth we hard coded
if (depth == maxDepth) {
return getValue.getUtility();
}
//max player, looking for tile placements
if (bCheck == 1) {
//calls getBoards method which has all available AI tile placement options
List placements = getBoards(board);
int currentBest = Integer.MIN_VALUE;
for (int i = 0; i < placements.size(); i++) {
//check if current board is winning board. if yes then return value of board
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
//recursive call
else {
int check = miniMax(placements.get(i), depth + 1, 2);
if (check > currentBest) {
currentBest = check;
if (depth == 0) {
boardMove = placements.get(i);
}
}
}
}
return currentBest;
}
//max player, looking for board rotation options
if (bCheck == 2) {
//calls getRotations method which determines grid rotations for all 4 grids (left and right turns)
List rotations = getRotations(board);
int currentBest = Integer.MIN_VALUE;
GameBoard temp = new GameBoard();
for (int i = 0; i < rotations.size(); i++) {
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
else{
//recursive call
int check = miniMax(rotations.get(i), depth + 1, 3);
if (check > currentBest) {
currentBest = check;
if (depth == 1) {
temp = rotations.get(i);
}
}
}
}
if (depth == 1) {
gameBoards.add(temp);
board.setIndex(gameBoards.size() - 1);
}
return currentBest;
}
//min player, looking for tile placements options
if (bCheck == 3) {
//calls getBoards method to find all possible tile placement options
List placements = getBoards(board);
int currentBest = Integer.MAX_VALUE;
for (int i = 0; i < placements.size(); i++) {
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
//recursive call
else {
int check = miniMax(placements.get(i), depth + 1, 4);
if (check < currentBest) {
currentBest = check;
if (depth == 0) {
boardMove = placements.get(i);
}
}
}
}
return currentBest;
}
//max player, looking for board rotation options
if (bCheck == 4) {
//calls getRotations method which determines grid rotations for all 4 grids (left and right turns)
List rotations = getRotations(board);
int currentBest = Integer.MAX_VALUE;
GameBoard temp = new GameBoard();
for (int i = 0; i < rotations.size(); i++) {
//recursive call
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
else {
int check = miniMax(rotations.get(i), depth + 1, 1);
if (check < currentBest) {
currentBest = check;
if (depth == 1) {
temp = rotations.get(i);
}
}
}
}
if (depth == 1) {
gameBoards.add(temp);
board.setIndex(gameBoards.size() - 1);
}
return currentBest;
}
//should never reach this state
return 0;
}
Min-Max with alpha beta pruning
/**
* Method that utilizes min max algorithm and alpha beta pruning
* @param board - current state of the board
* @param depth - current depth of tree (starts at 0)
* @param bCheck - controls flow in the four if statements
* @param newAlpha - for max player this is minimum num in Java
* @param newBeta - for min player this is max num in Java
*/
private int miniMaxAB(GameBoard board, int depth, int bCheck,int newAlpha,int newBeta) {
nodeCount++;
int alpha = newAlpha;
int beta = newBeta;
winConditions getValue = new winConditions();
getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4());
//stop when we hit the max depth we hard coded
if (depth == maxDepth) {
return getValue.getUtility();
}
//max player, looking for tile placements
if (bCheck == 1) {
//calls getBoards method which has all available AI tile placement options
List placements = getBoards(board);
int currentBest = Integer.MIN_VALUE;
for (int i = 0; i < placements.size(); i++) {
int check = CHECK;
//check if current board is winning board. if yes then return value of board
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
//recursive call
else if(beta > alpha){
check = miniMaxAB(placements.get(i), depth + 1, 2, alpha, beta);
}
if(check > alpha && check != CHECK){
alpha = check;
}
if (check > currentBest && check != CHECK) {
currentBest = check;
if (depth == 0) {
boardMove = placements.get(i);
}
}
}
return currentBest;
}
//max player, looking for board rotation options
if (bCheck == 2) {
//calls getRotations method which determines grid rotations for all 4 grids (left and right turns)
List rotations = getRotations(board);
int currentBest = Integer.MIN_VALUE;
GameBoard temp = new GameBoard();
for (int i = 0; i < rotations.size(); i++) {
int check = CHECK;
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
else if(beta > alpha){
//recursive call
check = miniMaxAB(rotations.get(i), depth + 1, 3, alpha, beta);
}
if(check > alpha && check != CHECK) {
alpha = check;
}
if (check > currentBest && check != CHECK) {
currentBest = check;
if (depth == 1) {
temp = rotations.get(i);
}
}
}
if (depth == 1) {
gameBoards.add(temp);
board.setIndex(gameBoards.size() - 1);
}
return currentBest;
}
//min player, looking for tile placements
if (bCheck == 3) {
//calls getBoards method which has all available AI tile placement options
List placements = getBoards(board);
int currentBest = Integer.MAX_VALUE;
for (int i = 0; i < placements.size(); i++) {
int check = CHECK;
//check if current board is winning board. if yes then return value of board
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
//recursive call
else if(beta > alpha){
check = miniMaxAB(placements.get(i), depth + 1, 4, alpha, beta);
}
if(check < beta && check != CHECK){
beta = check;
}
if (check < currentBest && check != CHECK) {
currentBest = check;
if (depth == 0) {
boardMove = placements.get(i);
}
}
}
return currentBest;
}
//min player, looking for board rotation options
if (bCheck == 4) {
//calls getRotations method which determines grid rotations for all 4 grids (left and right turns)
List rotations = getRotations(board);
int currentBest = Integer.MAX_VALUE;
GameBoard temp = new GameBoard();
for (int i = 0; i < rotations.size(); i++) {
int check = CHECK;
if (getValue.isWin(board.getGrid1(), board.getGrid2(), board.getGrid3(), board.getGrid4()) == true) {
return getValue.getUtility();
}
else if(beta > alpha){
//recursive call
check = miniMaxAB(rotations.get(i), depth + 1, 1, alpha, beta);
}
if(check < beta && check != CHECK) {
beta = check;
}
if (check < currentBest && check != CHECK) {
currentBest = check;
if (depth == 1) {
temp = rotations.get(i);
}
}
}
if (depth == 1) {
gameBoards.add(temp);
board.setIndex(gameBoards.size() - 1);
}
return currentBest;
}
//should never reach this.
return 0;
}
Utility
/**
* Method that calculates the utility of the current game board state. The AI uses this information to make the
* best decisions on where to play a tile.
*/
private void calculateValue() {
utility = 0;
//to go through all 32 possible win states
for (int i = 0; i < 32; i++) {
int temp = 0;
int wWin = 0;
int bWin = 0;
if ((wins[i][0] == 'w' || wins[i][0] == '*') && (wins[i][1] == 'w' || wins[i][1] == '*') && (wins[i][2] == 'w' || wins[i][2] == '*')
&& (wins[i][3] == 'w' || wins[i][3] == '*') && (wins[i][4] == 'w' || wins[i][4] == '*')) {
for (int j = 0; j < 5; j++) {
//how many w tokens in win arrays
if (wins[i][j] == 'w') {
wWin++;
}
}
} else if ((wins[i][0] == 'b' || wins[i][0] == '*') && (wins[i][1] == 'b' || wins[i][1] == '*') && (wins[i][2] == 'b' || wins[i][2] == '*')
&& (wins[i][3] == 'b' || wins[i][3] == '*') && (wins[i][4] == 'b' || wins[i][4] == '*')) {
for (int j = 0; j < 5; j++) {
//how many b tokens in win arrays
if (wins[i][j] == 'b') {
bWin++;
}
}
}
//if the board is better overall for w player
if (wWin > bWin) {
temp = (int) Math.pow(2, wWin); // 2^n where n is from 0 to 5
//if the board is better overall for b player
} else if (bWin > wWin) {
temp = -((int) Math.pow(2, bWin)); // 2^n where n is from 0 to 5
}
//if n was 5 (see above) then 2^n or 2^5 = 32 which means there was a winner
//w player wins
if (temp == 32) {
wWinner = true;
utility += 10000;
//System.out.println("Player 1 (player w) has won the game");
}
//b player wins
if (temp == -32) {
bWinner = true;
utility -= 10000;
//System.out.println("Player 2 (player b) has won the game");
}
utility += temp;
}
}
/** returns utility value of board*/
public int getUtility() {
return utility;
}
}