The game model (Ultimatoe
) consists of 9 instances of Tic-Tac-Toe (UltimatoeBoard
) and some auxiliary information. As the number of all reachable boards is bound by \$3^9 = 19683\$, they all are pre-generated, which allows fast move evaluation.
Before reviewing, please read the short text of the predecessor question and the README. It's just a few lines.
Since the predecessor question, the code has slightly changed, but the interfaces given there have not. So all the needed stuff is available on this site and additional information on github.
UltimatoeBoard
/**
* Representation of a 3x3 board of {@link Ultimatoe}.
*
* <p>As there are just a few thousands reachable states, they all get pre-created with all necessary data
* in order to make moves as fast as possible.
*/
@Immutable final class UltimatoeBoard {
/**
* Create a new board described by the given fields and also recursively create
* all its ancestors unless found in the repository.
*
* @param fields the effectivelly immutable list containing state of the nine fields
* @param repository a map filled with already created boards
*/
private UltimatoeBoard(List<UltimatoePlayer> fields, Map<List<UltimatoePlayer>, UltimatoeBoard> repository) {
checkArgument(fields.size() == AREA);
this.fields = fields;
winner = computeWinner();
int possibilities = 0;
if (winner.isDummy()) {
for (final GamePlayer<Ultimatoe> player : UltimatoeUtils.PLAYERS) {
if (player.isDummy()) continue;
for (int i=0; i<AREA; ++i) {
if (!getPlayerOnField(i).isDummy()) continue;
children[childIndex(i, player)] = getOrCreateChild(i, (UltimatoePlayer) player, repository);
possibilities |= 1 << i;
}
}
}
this.possibilities = possibilities;
}
/** Get or create a child by executing a move of the given player on a field given by the index. */
private UltimatoeBoard getOrCreateChild(
int index, UltimatoePlayer player, Map<List<UltimatoePlayer>, UltimatoeBoard> repository) {
final List<UltimatoePlayer> childFields = Lists.newArrayList(this.fields);
childFields.set(index, player);
UltimatoeBoard result = repository.get(childFields);
if (result!=null) return result;
result = new UltimatoeBoard(childFields, repository);
repository.put(childFields, result);
return result;
}
/** Create the empty board. Must be called just once. */
private static UltimatoeBoard createEmptyBoard() {
final List<UltimatoePlayer> emptyFields = Lists.newArrayList();
for (int i=0; i<AREA; ++i) emptyFields.add(UltimatoePlayer.NOBODY);
final Map<List<UltimatoePlayer>, UltimatoeBoard> repository = Maps.newHashMap();
return new UltimatoeBoard(emptyFields, repository);
}
private UltimatoePlayer computeWinner() {
for (final int[] winningSet : UltimatoeUtils.WINNING_SETS) {
final UltimatoePlayer player = getPlayerOnField(winningSet[0]);
if (player.isDummy()) continue;
if (player != getPlayerOnField(winningSet[1])) continue;
if (player != getPlayerOnField(winningSet[2])) continue;
return player;
}
return UltimatoePlayer.NOBODY;
}
@Override public String toString() {
final StringBuilder result = new StringBuilder();
for (int i=0; i<AREA; ++i) {
if (i%WIDTH == 0) result.append("\n");
result.append(getPlayerOnField(i).toChar());
}
return result.substring(1);
}
/** Return a child corresponding to executing a move of the given player on a field given by the index. */
@Nullable UltimatoeBoard play(int index, GamePlayer<Ultimatoe> player) {
return children[childIndex(index, player)];
}
UltimatoePlayer getPlayerOnField(int index) {
return fields.get(index);
}
/**
* Return true if iy's possible to play at field with the given index,
* i.e., if the field is empty and the board hasn't been decided yet.
*/
boolean isPlayable(int index) {
return (possibilities & (1<<index)) != 0;
}
/** Return true if this board has been finished. */
boolean isFinished() {
return possibilities == 0;
}
private int childIndex(int index, GamePlayer<Ultimatoe> player) {
return 2*index + player.ordinal();
}
private static final int WIDTH = 3;
private static final int HEIGHT = 3;
private static final int AREA = WIDTH * HEIGHT;
static final UltimatoeBoard EMPTY_BOARD = createEmptyBoard();
/** The 9 fields of the board, from left to right, then top to bottom. Effectively immutable. */
private final List<UltimatoePlayer> fields;
/** The player who has won, otherwise {@link UltimatoePlayer#NOBODY}. */
@Getter @NonNull private final UltimatoePlayer winner;
/**
* A bitmask determining which moves are allowed, i.e.,<ul>
* <li>which fields are empty, if the board hasn't been decided yet.
* <li>zero, otherwise.
*
* <p>For details, see the code of {@link UltimatoeBoard#isPlayable(int)}.
*/
@Getter private final int possibilities;
/**
* An array of all child boards, i.e., boards resulting from one player placing one piece on an empty field.
*
* <p>For details, see the code of {@link UltimatoeBoard#childIndex(int, GamePlayer)}.
* A 1D arrays gets used for maximum speed (better memory locality).
* This may or mey not be a premature optimization.
*/
private final UltimatoeBoard[] children = new UltimatoeBoard[2*AREA];
}
Ultimatoe
/**
* An immutable representation of (the state of)
* <a href="http://mathwithbaddrawings.com/2013/06/16/ultimate-tic-tac-toe">Ultimate Tic-Tac-Toe</a>.
*/
@RequiredArgsConstructor(access=AccessLevel.PRIVATE) @EqualsAndHashCode @Immutable
public final class Ultimatoe implements Game<Ultimatoe> {
private static final class ToStringHelper {
ToStringHelper(Ultimatoe game) {
final char[][] result = new char[11][11];
for (int i=0; i<11; ++i) Arrays.fill(result[i], UltimatoeUtils.BORDER);
for (int y1=0; y1<3; ++y1) {
for (int x1=0; x1<3; ++x1) {
final int majorIndex = x1 + 3*y1;
final UltimatoeBoard board = game.boards[majorIndex];
for (int y0=0; y0<3; ++y0) {
for (int x0=0; x0<3; ++x0) {
final UltimatoePlayer player = board.getPlayerOnField(x0 + 3*y0);
final char c = computeChar(game, majorIndex, player);
result[4*y1 + y0][4*x1 + x0] = c;
}
}
}
}
final StringBuilder sb = new StringBuilder();
for (int i=0; i<11; ++i) {
if (i>0) sb.append("\n");
sb.append(result[i]);
}
toString = sb.toString();
}
private char computeChar(Ultimatoe game, int majorIndex, UltimatoePlayer player) {
if (!player.isDummy()) return player.toChar();
return game.isPlayable(majorIndex) ? UltimatoeUtils.PLAYABLE : UltimatoeUtils.NON_PLAYABLE;
}
private final String toString;
}
@Override public String toString() {
return asString();
}
@Override public String asString() {
return new ToStringHelper(this).toString;
}
@Override public ImmutableList<GamePlayer<Ultimatoe>> players() {
return UltimatoeUtils.PLAYERS;
}
@Override public double score() {
switch (winner) {
case NOBODY: return 0;
case PLAYER_X: return +1;
case PLAYER_O: return -1;
}
throw new RuntimeException("impossible");
}
@Override public ImmutableBiMap<Ultimatoe, String> children() {
final ImmutableBiMap.Builder<Ultimatoe, String> result = ImmutableBiMap.builder();
for (int i=0; i<N_BOARDS; ++i) {
if (!isPlayable(i)) continue;
final UltimatoeBoard b = boards[i];
for (int j=0; j<N_FIELDS_PER_BOARD; ++j) {
if (!b.isPlayable(j)) continue;
result.put(play(i, j), UltimatoeUtils.indexesToMoveString(i, j));
}
}
return result.build();
}
@Override public Ultimatoe play(String move) {
checkNotNull(move);
final int majorIndex = UltimatoeUtils.stringToMajorIndex(move);
final int minorIndex = UltimatoeUtils.stringToMinorIndex(move);
return play(majorIndex, minorIndex);
}
@Override public Ultimatoe play(Random random) {
checkNotNull(random);
if (Integer.bitCount(possibilities) == 1) {
final int i = Integer.numberOfTrailingZeros(possibilities);
return play(i, random);
}
int countdown = childrenCount();
for (int i=0; i<N_BOARDS; ++i) {
if (!isPlayable(i)) continue;
countdown -= Integer.bitCount(boards[i].possibilities());
if (countdown<=0) return play(i, random);
}
throw new RuntimeException("impossible");
}
/** Return the game state resulting from applying a random move on the board given by the argument. */
private Ultimatoe play(int majorIndex, Random random) {
final int possibilities = boards[majorIndex].possibilities();
while (true) {
final int j = random.nextInt(N_FIELDS_PER_BOARD);
if ((possibilities & (1<<j)) == 0) continue;
return checkNotNull(play(majorIndex, j));
}
}
private int childrenCount() {
int result = 0;
for (final UltimatoeBoard b : boards) result += Integer.bitCount(b.possibilities());
return result;
}
/**
* Return the game state resulting from playing on the position given by the arguments.
*
* @param majorIndex the index of the board, must be between 0 and 8
* @param minorIndex the index of field of the board, must be between 0 and 8
*/
private Ultimatoe play(int majorIndex, int minorIndex) {
final UltimatoeBoard oldBoard = boards[majorIndex];
final UltimatoeBoard newBoard = oldBoard.play(minorIndex, playerOnTurn());
checkNotNull(newBoard);
final UltimatoeBoard[] newBoards = boards.clone();
newBoards[majorIndex] = newBoard;
final boolean sameWinner = oldBoard.winner() == newBoard.winner();
final UltimatoePlayer newWinner = sameWinner ? UltimatoePlayer.NOBODY : computeWinner(newBoards);
final int newMovesBitmask = computeMovesBitmask(minorIndex, newBoards, newWinner);
return new Ultimatoe(turn+1, newMovesBitmask, newWinner, newBoards);
}
private static int computeMovesBitmask(int lastMinorIndex, UltimatoeBoard[] boards, UltimatoePlayer winner) {
if (!winner.isDummy()) return 0;
if (!boards[lastMinorIndex].isFinished()) return 1 << lastMinorIndex;
int result = 0;
for (int i=0; i<N_BOARDS; ++i) {
if (!boards[i].isFinished()) result |= 1 << i;
}
return result;
}
private static final UltimatoePlayer computeWinner(UltimatoeBoard[] boards) {
for (final int[] winningSet : UltimatoeUtils.WINNING_SETS) {
final UltimatoePlayer player = boards[winningSet[0]].winner();
if (player.isDummy()) continue;
if (player != boards[winningSet[1]].winner()) continue;
if (player != boards[winningSet[2]].winner()) continue;
return player;
}
return UltimatoePlayer.NOBODY;
}
@Override public boolean isFinished() {
return possibilities == 0;
}
@Override public GamePlayer<Ultimatoe> playerOnTurn() {
return UltimatoeUtils.PLAYERS.get(turn & 1);
}
/** Return true if the player on turn can play on the board given by the argument. */
private boolean isPlayable(int majorIndex) {
return ((possibilities>>majorIndex) & 1) != 0;
}
private static final int N_BOARDS = 9;
private static final int N_FIELDS_PER_BOARD = 9;
public static final Ultimatoe INITIAL_GAME = new Ultimatoe(
0, (1<<N_BOARDS) - 1, UltimatoePlayer.NOBODY, new UltimatoeBoard[] {
UltimatoeBoard.EMPTY_BOARD, UltimatoeBoard.EMPTY_BOARD, UltimatoeBoard.EMPTY_BOARD,
UltimatoeBoard.EMPTY_BOARD, UltimatoeBoard.EMPTY_BOARD, UltimatoeBoard.EMPTY_BOARD,
UltimatoeBoard.EMPTY_BOARD, UltimatoeBoard.EMPTY_BOARD, UltimatoeBoard.EMPTY_BOARD,
});
@Getter private final int turn;
/** Contains one bit per board. See {@link #isPlayable(int)}*/
private final int possibilities;
@Getter @NonNull private final UltimatoePlayer winner;
/** The 9 boards of the game, from left to right, then top to bottom. */
private final UltimatoeBoard[] boards;
}
I'm mostly interested in speed improvements (just note that UltimatoeBoard
s speed doesn't matter as it's just initialization).
In the meantime, I came to the idea I could implement plain stupid Tic-Tac-Toe by simply renaming UltimatoeBoard
and letting it implement Game
. This worked nicely, the only ugly part was the GUI, which I copied.