Ultimatoe — 2. The model

Question

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 UltimatoeBoards 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.

Answer 1

Spacing

Your code could use lots of both vertical and horizontal spacing.

You should use vertical spacing to group related lines of code together. It is much easier to read.

Horizontal spacing will also add readability at least if done where you assign or compare variables.

@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();
}  

is much more readable like so

@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();
}  

I guess you know my habit to place braces {} arround everything, so I did in this sample.

---

Constructor

The constructor should be used to construct the object with the minimum needed stuff. IMHO you are doing too much inside the constructor which should be extracted to a separate method.

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;
}  

Let us create a method computePossibilities() to assign to the class variable possibilites like so

private int computePossibilities() {

    int possibilities = 0;

    if (!winner.isDummy()) { return possibilities; }

    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;
        }
    }

    return possibilities;
}  

You may have noticed that I have inverted the condition of the first if condition, because this is horizontal space which should be avoided.

Now your constructor looks like so

private UltimatoeBoard(List<UltimatoePlayer> fields, Map<List<UltimatoePlayer>, UltimatoeBoard> repository) {
    checkArgument(fields.size() == AREA);

    this.fields = fields;
    this.winner = computeWinner();
    this.possibilities = computePossibilities();
}   

I am not that sure about the name computePossibilities but I have nevertheless named it like this.

---

Ultimatoe

The constructor could get a little faster by storing calculated results which you calculate often

    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();
    }  

here in the most inner loop you are calculating 4*y1, 4*x1 and 3*y0 for each iteration. You should store the result in some variables and use them in the most inner loop.

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) {

        final int outerIndexY = 4 * y1;
        final int majorIndexY = 3 * y1;

        for (int x1 = 0; x1 < 3; ++x1) {

            final int outerIndexX = 4 * x1;
            final int majorIndex = x1 + majorIndexY;
            final UltimatoeBoard board = game.boards[majorIndex];

            for (int y0 = 0; y0 < 3; ++y0) {

                final int innerIndexY = 3 * y0;

                for (int x0 = 0; x0 < 3; ++x0) {

                    final UltimatoePlayer player = board.getPlayerOnField(x0 + innerIndexY);
                    final char c = computeChar(game, majorIndex, player);
                    result[outerIndexY + y0][outerIndexX + 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();
}

now about the StringBuilder part. If you don't initialize a StringBuilder object with a capacity it will have a default value of 16 and each time the length of the StringBuilder exceeds the capacity to 2 * capacity +2.

Here you already know the maximum capacity (11 * 11 + 10) the StringBuilder can reach so you should use this knowledge.

If you append result[0] before the loop and let the loop start at 1 you can omit the if in the loop.

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) {

        final int outerIndexY = 4 * y1;
        final int majorIndexY = 3 * y1;

        for (int x1 = 0; x1 < 3; ++x1) {

            final int outerIndexX = 4 * x1;
            final int majorIndex = x1 + majorIndexY;
            final UltimatoeBoard board = game.boards[majorIndex];

            for (int y0 = 0; y0 < 3; ++y0) {

                final int innerIndexY = 3 * y0;

                for (int x0 = 0; x0 < 3; ++x0) {

                    final UltimatoePlayer player = board.getPlayerOnField(x0 + innerIndexY);
                    final char c = computeChar(game, majorIndex, player);
                    result[outerIndexY + y0][outerIndexX + x0] = c;

                }
            }
        }
    }

    final int maxCapacity = 131;
    final StringBuilder sb = new StringBuilder(maxCapacity);

    sb.append(result[0]);

    for (int i = 1; i < 11; ++i) {
        sb.append("\n")  
          .append(result[i]);
    }

    toString = sb.toString();
}

Answer 2

General notes

* <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.

Are you sure that this gets more efficient? Personally I believe that your way of pre-creating the boards has a bigger cost than it has value. It requires quite a bit of code to accomplish that, which reduces the code readability. I would like to know how fast the code would be if you had done things differently, by either keeping the immutability of the game and creating boards whenever you would need them, or by having mutable state and update as you need it.

And is it true that the states are all pre-created? Or are they created on demand and then stored for the future?

---

I'm mostly interested in speed improvements (just note that UltimatoeBoards speed doesn't matter as it's just initialization).

Does initialization really not matter? What if initialization would take an hour? Or six hours? (I know, I'm using extreme values here, but I hope you understand the point)

---

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.

Tic-Tac-Toe can be generalized into M,n,k-games. There are a lot of games that can be made from this. I made some of them here (note that Reversi is of course not a M,n,k-game, I just made that as a bonus). You may also want to see my Tic-Tac-Toe Ultimate Code Review question.

Code specific notes

for (final GamePlayer<Ultimatoe> player : UltimatoeUtils.PLAYERS) {
    if (player.isDummy()) continue;

I imagine it would be better if you would have a separate list that would have excluded the dummy-player from the start.

---

private UltimatoeBoard(List<UltimatoePlayer> fields, Map<List<UltimatoePlayer>, UltimatoeBoard> repository) {

This repository of yours is a bit unclear how it works. I would recommend, if you want to keep it, to make it a class with something like:

public class UltimatoeRepository {
    private final Map<List<UltimatoePlayer>, UltimatoeBoard> boards;

    public UltimatoeBoard getOrCreateBoard(List<UltimatoePlayer> playedPositions) {
         ...
    }

}

This may not look like a big improvement, but it provides some encapsulation (it prevents any code that has the Map reference to clear the map or do anything it shouldn't), and gives an opportunity to provide clearer method names and parameter names, and makes it a bit easier to understand what it does instead of seeing the Map<List<UltimatoePlayer>, UltimatoeBoard> scattered across your code.

---

/** Create the empty board. Must be called just once. */
private static UltimatoeBoard createEmptyBoard() {

What exactly happens if it is called more than once? only needs to be called just once perhaps, but I don't see any immediate harm of calling this method more than once (sorry, I'm being Javadoc-nitpicky now, moving on...)

Oh, by the way, as that actually is a Javadoc (/** instead of just /*), it is missing a @return note.

---

Your computeWinner method is was slightly confusing to me. (I just realized what is going on).

You might want to extract a method that checks whether or not the int[] winningSet contains a winner or not, and what player it contains. Or you might want to extract a WinningSet / WinningCondition class that can contain this logic (if you look up TTWinCondition in my code, you see that I added a bunch of methods to it that I found useful).

Additionally, and this is common for Tic-Tac-Toe Ultimate implementations, there is code duplication for checking winner. This method exists in both UltimatoeBoard and Ultimatoe. (Can't blame you much, it isn't easy to make UTTT duplication-free).

---

for (int y1=0; y1<3; ++y1) {
    for (int x1=0; x1<3; ++x1) {
        (...)
        for (int y0=0; y0<3; ++y0) {
            for (int x0=0; x0<3; ++x0) {

May I suggest using variable names like outerX, outerY and innerX, innerY? or use local / board / game prefixes. The current names are a bit unclear which one is for the board-in-game and which one is for tile-in-board.

---

result[4*y1 + y0][4*x1 + x0] = c;

I assume the 4 is because of your usage of a border around the fields, but does that border have to be a part of your game model? It'd be more clear to see a 3 here, or even better: Extract a constant.

---

@Override public String asString() {
    return new ToStringHelper(this).toString;
}

Why do you have a class and instantiate that class only to access a single String result? Your ToStringHelper could very well instead be just a method in the class itself, or contain a static method that would return the string you want. Instantiating a ToStringHelper object for this is overkill.

---

I know my way around bitfields normally, and I like bitfields generally, but your Ultimatoe play(Random random) method seems like magic to me.

I totally understand this part:

if (Integer.bitCount(possibilities) == 1) {
    final int i = Integer.numberOfTrailingZeros(possibilities);
    return play(i, random);
}

(Even though I feel it might be a bit unnecessary)

This however, I don't quite get:

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);
}

Additionally, to make the bitmasking even worse, there's this:

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));
    }
}

and this:

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;
}

This leaves me asking: Is the bitfields really worth it? And have you considered using BitSet?

Personally, I'm not a big fan of this bitfield manipulation, and I wonder if it comes with that much of a performance gain in your gains (if it is even a gain at all?). But besides the possible performance effects, I can say that it makes it more complicated to understand what is going on. I feel that a List<UltimatoeBoard> or UltimatoeBoard[] would do the job just as efficiently, and much more clearer.

Typos

* Return true if iy's possible to play at field with the given index,

* This may or mey not be a premature optimization.