HackerEarth: Battle Of Bots 6: Draughts

Problem:

Sample Game

Draughts is a two player board game which is played on a 8X8 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Red ( First Player ) or White ( Second Player ) being conventional. Players take turns involving diagonal moves of uniform game pieces in the forward direction only and mandatory captures by jumping over opponent pieces.

Rules:

  • Player can only move diagonally to the adjacent cell and in forward direction, if the diagonally adjacent cell is vacant.
  • A player may not move an opponent’s piece.
  • If the diagonally adjacent cell contains an opponent’s piece, and the cell immediately beyond it is vacant, the opponent’s piece may be captured (and removed from the game) by jumping over it in the forward direction only.
  • If a player made a jump, then its mandatory to keep on jumping as long as the jump is possible.
  • Player cannot move to the diagonally adjacent cell once the player made a jump.

The game will end when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 8X8 grid. The top left of the grid is [0,0] and the bottom right is [7,7].

Input:
The input will be a 8X8 matrix consisting only of 0o2. Then another line will follow which will contain a number –  1 or 2 which is your player id. In the given matrix, top-left is [0,0] and bottom-right is [7,7]. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Red in color. The cell marked 2 means it contains second player’s stone which is white in color.

Output:
In the first line print the coordinates of the cell separated by space, the piece he / she wants to move.
In second line print an integer N, number of steps or jumps the piece will make in one move.
In the next N lines print the coordinates of the cells in which the piece will make jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if [1,1] in diagonal to the piece in which is going to jump, but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

Starting state
The starting state of the game is the state of the board before the game starts.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0

First Input
This is the input give to the first player at the start of the game.

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 2 0 2 0 2 0 2
2 0 2 0 2 0 2 0
1
SAMPLE INPUT
0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0
0 0 0 2 0 0 0 2
2 0 2 0 2 0 2 0
1
SAMPLE OUTPUT
2 5
2
4 3
6 1

Explanation

This is player 1’s turn, and the player will move the piece at [2,5] and will make two jumps. First jump will be at [4,3and second jump will be at [6,1]

After his/her move the state of game becomes:

0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 2 0 2 0 2
2 0 2 0 2 0 2 0

This state will be fed as input to program of player 2.

Other valid move for the first player is

2 5
1
3 6

But the following are invalid moves.
Case 1:

2 5
1
4 3

Because after making a jump its possible to jump again and its mandatory to jump as long as its possible to jump.

Case 2:

2 5
2
4 3
5 4

Because after making a jump its invalid to move to diagonally adjacent cell.

Here is the code of the Random Bot.

Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

Solution

This is the solution submitted by me

Two player game program – e.g. TIC TAC TOE…

This is an abstract State class
public abstract class State {

// This method is abstract, the extending class has to give the implementation
// It will return a list of all the possible children from the current state.
public abstract List getChildren();
public abstract String getTurn();
public abstract void setTurn(String turn);

// Find out who is the winner from the current state.
public abstract String getWinner();

// Check if the game has been finished or not.
public abstract boolean isGameOver();

// I have given the implementation specifically for TIC-TAC-TOE.
// You can override this functionality in the extending class according to your game requirements.
//
// This function will give the score of the current state.
// Then you can compare it with its siblings to check which state will be better to move to..
//
public int minimax()
{

if(!getWinner().equals(""))
{
if("X".equalsIgnoreCase(getWinner()))
{
return 1;
}
if("O".equalsIgnoreCase(getWinner()))
{
return -1;
}
if("draw".equalsIgnoreCase(getWinner()))
{
return 0;
}
}
List children = getChildren();
if(getTurn().equals("X"))
{
int maxScore = -100;
for(State child : children)
{
int childScore = child.minimax();
if(childScore > maxScore)
{
maxScore = childScore;
}
}
return maxScore;
}
else
{
int minScore = 100;
for(State child : children)
{
int childScore = child.minimax();
if(childScore < minScore)
{
minScore = childScore;
}
}
return minScore;
}

}
}

Extend the above State class and give some implementations…as follows:
Lets assume the class to be TttState…
We’ll override the abstract methods of the parent class State..

Give a member variable that’ll hold the current state of your game…In my case, I have taken it as array..

// This variable is going to hold the current state of your game.
// It can be any depending on your game requirements...
private String state[][] = null ;

Give a copy constructor

public TttState(State x)
{
TttState tState = (TttState)x;
state = new String[3][3];
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
this.state[i][j]=tState.state[i][j];
}
}
this.turn = x.getTurn();
}

Give a default constructor

public TttState() {
state = new String[3][3];
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
this.state[i][j]="";
}
}
this.turn = "X";
}

Give a toString implementation, so that you can print the current state

public String toString()
{
StringBuilder sb = new StringBuilder("");
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
if(state[i][j].equals(""))
{
sb.append("-");
}
else
{
sb.append(state[i][j]);
}
sb.append("t");
}
sb.append("n");
}
return sb.toString();
}

Override the method getWinner() as follows

public String getWinner()
{
// ROW CHECK BEGINS
if(state[0][0].equalsIgnoreCase("X") && state[0][1].equalsIgnoreCase("X") && state[0][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][0].equalsIgnoreCase("O") && state[0][1].equalsIgnoreCase("O") && state[0][2].equalsIgnoreCase("O"))
{
return "O";
}
if(state[1][0].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[1][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[1][0].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[1][2].equalsIgnoreCase("O"))
{
return "O";
}
if(state[2][0].equalsIgnoreCase("X") && state[2][1].equalsIgnoreCase("X") && state[2][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[2][0].equalsIgnoreCase("O") && state[2][1].equalsIgnoreCase("O") && state[2][2].equalsIgnoreCase("O"))
{
return "O";
}

// COLUMN CHECK BEGINS
if(state[0][0].equalsIgnoreCase("X") && state[1][0].equalsIgnoreCase("X") && state[2][0].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][0].equalsIgnoreCase("O") && state[1][0].equalsIgnoreCase("O") && state[2][0].equalsIgnoreCase("O"))
{
return "O";
}
if(state[0][1].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[2][1].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][1].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[2][1].equalsIgnoreCase("O"))
{
return "O";
}
if(state[0][2].equalsIgnoreCase("X") && state[1][2].equalsIgnoreCase("X") && state[2][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][2].equalsIgnoreCase("O") && state[1][2].equalsIgnoreCase("O") && state[2][2].equalsIgnoreCase("O"))
{
return "O";
}
// DIAGNONAL CHECKS
if(state[0][0].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[2][2].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][0].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[2][2].equalsIgnoreCase("O"))
{
return "O";
}

if(state[0][2].equalsIgnoreCase("X") && state[1][1].equalsIgnoreCase("X") && state[2][0].equalsIgnoreCase("X"))
{
return "X";
}
if(state[0][2].equalsIgnoreCase("O") && state[1][1].equalsIgnoreCase("O") && state[2][0].equalsIgnoreCase("O"))
{
return "O";
}
int nonBlank = 0;
for(int i=0;i<=2;i++)
{
for(int j=0;j<=2;j++)
{
if(!state[i][j].equals(""))
{
nonBlank++;
}
}
}
if(nonBlank==9)
{
return "draw";
}

return "";
}

Override the method isGameOver()

public boolean isGameOver()
{
if(!getWinner().equals("") && !getWinner().equals("draw"))
{
return true;
}
else
{
return false;
}
}

Override the method getChildren()

@Override
public List getChildren() {
List children = new ArrayList();
if(turn.equals("X"))
{
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
if(state[i][j].equals(""))
{
TttState child = new TttState(this);
child.state[i][j]="X";
String newTurn = "O";
child.setTurn(newTurn);
children.add(child);
}
}
}
}
else
{
for(int i=0;i<=2; i++)
{
for(int j=0; j<=2;j++)
{
if(state[i][j].equals(""))
{
TttState child = new TttState(this);
child.state[i][j]="O";
String newTurn = "X";
child.setTurn(newTurn);
children.add(child);
}
}
}
}
return children;
}

Override getTurn and setTurn

public String getTurn() {
return turn;
}

public void setTurn(String turn) {
this.turn = turn;
}

Your main program will look something like this:

public static void main(String args[])
{
TttState x = new TttState();
System.out.println("WINNER : " + x.getWinner());
x.setTurn("X");
Scanner sc = new Scanner(System.in);
while(!x.isGameOver())
{
String xIndex = sc.nextLine();
String yIndex = sc.nextLine();
int xint = Integer.parseInt(xIndex);
int yint = Integer.parseInt(yIndex);
x.getState()[xint][yint]="X";
x.setTurn("O");
int minScore = 100;
List children = x.getChildren();
TttState bestMove = new TttState(x);
for(State child : children)
{
int childScore = child.minimax();
// We are using < because we are always evaluating
// the best move from the options that O player has....
if(childScore < minScore)
{
minScore = childScore;
bestMove = (TttState)child;
bestMove.setTurn("X");
}
}
System.out.print(bestMove);
x = bestMove;
}
System.out.println("GAME OVER...");

}