Here are requirements: Concurrent Tic-Tac-Toe is an exercise where two concurrent threads represent players and try to edit same 3x3 table setting X and O.
Note that game table itself (interface concurrenttictactoe.TicTacToe) is not very aware of the game rules. The only thing it must restrict is setting a value in a cell, that has value already. The game table must not restrict setting several same values in a row. The game table must not restrict setting a value after one of players has won. Refer to methods Javadoc for details.
Implement concurrenttictactoe.TicTacToe buildGame method to present your implementation.
concurrenttictactoe.Player is an interface representing player routine. It extends Runnable interface to make it possible to submit it to a thread for concurrent execution. Implement com.epam.rd.autocode.concurrenttictactoe.Player createPlayer method to supply your implementation of a Player.
Each player gets a game table to play, a mark (note, X player always goes first), and a strategy to compute a next move. Players are aware of the game rules and will stop execution, when some of them has won. Players respect each other and do their turns one after another. The game routine is as follows: An empty board is created. Two players gets marks(X and O), created board to play, and strategies to compute another move. Both players start execution in separate threads. Players stop execution when the gameis over. The expected table state is compared to the actual one. Note, each game may not last more than 2 seconds.
I implement necessary classes:
package concurrenttictactoe;
public class PlayerImpl implements Player {
private TicTacToe game;
private char mark;
private PlayerStrategy strategy;
private static final long MAX_GAME_DURATION = 2000;
public PlayerImpl(TicTacToe game, char mark, PlayerStrategy strategy) {
this.game = game;
this.mark = mark;
this.strategy = strategy;
}
@Override
public void run() {
Object lock = game.getLock();
while (true) {
synchronized (lock) {
if (game.isGameOver()) break;
while (!game.isGameOver() && ((mark == 'O' && game.lastMark() != 'X') || (mark == 'X' && game.lastMark() == 'X'))) {
try {
lock.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
}
if (game.isGameOver() || !isGameRunning(game)) {
lock.notifyAll();
break;
}
Move move = strategy.computeMove(mark, game);
if (move == null) {
throw new UnsupportedOperationException("move is null");
}
game.setMark(move.row, move.column, mark);
lock.notifyAll();
}
}
}
private boolean isGameRunning(TicTacToe game) {
char[][] table = game.table();
/**
* Check
*/
for (int i = 0; i < 3; i++) {
/** CASE 1 - 'Horizontal win case'
* 0 1 2
* 0 -> {'X', 'X', 'X'}
* 1 -> {' ' ' ', ' '}
* 2 -> {' ' ' ', ' '}
* */
if (table[i][0] != ' ' && table[i][0] == table[i][1]
&& table[i][1] == table[i][2])
return false;
/** CASE 2 - 'Vertical win case'
* 0 1 2
* 0 -> {'X', ' ', ' '}
* 1 -> {'X' ' ', ' '}
* 2 -> {'X' ' ', ' '}
* */
if (table[0][i] != ' ' && table[0][i] == table[1][i]
&& table[1][i] == table[2][i])
return false;
}
/** CASE 3 - 'Diagonal win case'
* 0 1 2
* 0 -> {'X', ' ', 'X'}
* 1 -> {' ' 'X', ' '}
* 2 -> {'X' ' ', 'X'}
* */
if (table[0][0] != ' ' && table[0][0] == table[1][1]
&& table[1][1] == table[2][2])
return false;
if (table[0][2] != ' ' && table[0][2] == table[1][1]
&& table[1][1] == table[2][0])
return false;
/**
* Check if there's still empty cell to move when neither side has won
*/
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (table[i][j] == ' ') {
return true;
}
}
}
return false;
}
}
package concurrenttictactoe;
public class TicTacToeImpl implements TicTacToe{
private final Object lock = new Object();
private final long startTime = System.currentTimeMillis();
private volatile boolean gameOver = false;
private char[][] table = new char[][]{
{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '}
};
private char lastMark = ' ';
@Override
public void setMark(int x, int y, char mark) {
synchronized (lock) {
if (table[x][y] != ' ') {
throw new IllegalArgumentException("This cell already has a value");
}
if (lastMark == mark) {
throw new IllegalArgumentException("This mark already made a move");
}
table[x][y] = mark;
lastMark = mark;
/*//Just for testing!!//TODO: remove following lines after testing
System.out.println("Table state: ");
for (char[] chars : table) {
System.out.println("" + chars[0] + chars[1] + chars[2]);
}
System.out.println("Move ended! last move: " + lastMark + "\n");
/// /////////////////////////////////////*/
lock.notifyAll();
}
}
@Override
public char[][] table() {
char[][] result = new char[3][3];
for (int i = 0; i < result.length; i++) {
result[i][0] = table[i][0];
result[i][1] = table[i][1];
result[i][2] = table[i][2];
}
return result;
}
@Override
public char lastMark() {
return lastMark;
}
public Object getLock(){
return lock;
}
public long getStartTime(){
return startTime;
}
@Override
public boolean isGameOver() {
return gameOver;
}
public void stopGame() {
synchronized (lock) {
gameOver = true;
lock.notifyAll();
}
}
}
package concurrenttictactoe;
public interface Player extends Runnable{
static Player createPlayer(final TicTacToe ticTacToe, final char mark, PlayerStrategy strategy) {
return new PlayerImpl(ticTacToe, mark, strategy);
}
}
package concurrenttictactoe;
public class Move {
final int row;
final int column;
public Move(final int row, final int column) {
this.row = row;
this.column = column;
}
}
package concurrenttictactoe;
public interface PlayerStrategy {
/**
* Computes a new Move.
* @param mark - mark to set in move.
* @param ticTacToe - board to make a move.
* @return a move - combination of x and y coordinates.
*/
Move computeMove(char mark, TicTacToe ticTacToe);
}
But every time I run tests, they are exiting with timeoutException after 2 seconds. How can I do this? I have an access to test cases but it might be too much. What is failing and how can I make it exit in 2 seconds?
Answer
Is your method stopGame ever called? I don't think so.
Right now, your PlayerImpl only checks for win with isGameRunning() but does not signal that the game is over when a win is detected.
if (game.isGameOver()) break;
This will never be true, so the thread keeps running. As you said:
Two players gets marks(X and O), created board to play, and strategies to compute another move. Both players start execution in separate threads. Players stop execution when the game is over. The expected table state is compared to the actual one. Note, each game may not last more than 2 seconds.
So it's never over, as no player exits correctly.... And the timeout occurs.
tldr;
This piece of code:
if (game.isGameOver() || !isGameRunning(game)) {
lock.notifyAll();
break;
}
Should be this instead:
if (!isGameRunning(game)) {
game.stopGame(); // <-- !!!!
lock.notifyAll();
break;
}
if (game.isGameOver()) {
lock.notifyAll();
break;
}
Now the first player to detect a win calls stopGame(), notifying the other thread to exit promptly, ensuring the game ends within 2 seconds.