FX My Life XIV: Artificial “Intelligence”

Let’s wrap up the “backend” of our tic-tac-toe game by putting in tie-games and making some “artificial intelligence”. Or as I have it in the title, Artificial “Intelligence”. Or maybe it should be “Artificial “Intelligence”” because we’re not doing anything like what’s formally recognized as AI, and “intelligence” is a stretch even by AI terms.

We’ll create some computer players that will play tic-tac-toe against a human player or each other. But before we do that, we’ll need to introduce the game that ends with a tie, because otherwise our artificially intelligent players will keep playing the same game forever.

We could get sophisticated and call a game a tie when there can’t be a winner, but we won’t. We’ll say the game is a tie when the board is full. There’s nothing like the feeling of futility of having to play out a game when the draw is foregone. (If tie-games were a problem, you never should have started to play tic-tac-toe in the first place.)

We’ll create a coordinate class:

package fxgames;

public class Coord {
int x;
int y;

Coord(int aX, int aY) {
x = aX;
y = aY;
}
}

I didn’t really want to do this — you may recall me having avoided it in the past — but I don’t know of any better way in Java to get a list of coordinates without making a class for the coordinates.

This feels very cliché — how many times have people designed a coordinate class for Java? — and Java does have similar classes like the Abstract Window Toolkit’s Point class, but…seems like overkill to use a graphic coordinate from a graphic toolkit we’re not using.

Anyway, now we can get our empties:

public List<Coord> empties() {
var l = new ArrayList<Coord>();
for (var y = 0; y < 3; y++) {
for (var x = 0; x < 3; x++) {
if (state[y][x] == null) {
l.add(new Coord(x, y));
}
}
}
return l;
}

And we can have our checkGameState code call a tie:

public void checkGameState() {
checkVictoryCondition();
if (!winner.equals("")) {
if (winner.equals("X") && playerOneIsX) {
playerOneWins++;
} else if (winner.equals("O")) {
playerTwoWins++;
}
} else if (empties().size() == 0) {
winner = "-";
ties++;
}
}

I’m using “-” for a tie, ’cause why not? Now we’ve got to short-cut our code for drawling a slash (so that it doesn’t try to draw a slash when it’s a tie):

if (!game.winner.equals("")) {
if (game.winner.equals("-")) {
message.setText("Game over! " + "It's a tie! Again!");
return;
}
message.setText("Game over! " + game.winner + " wins!");
var bw = board.getWidth();
. . .

We should clean up a few things. Like we never actually connected a change in the Player Name edit fields to the game’s player names:

public void nameChange(KeyEvent e) {
String t = (((TextField) e.getTarget()).getText());
if (e.getTarget() == player1) {
p1label.setText(t);
game.playerOneName = t;
} else {
p2Label.setText(t);
game.playerTwoName = t;
}
}

OK, now we can actually write code to automatically place pieces! In the controller, we‘ll:

  1. Return immediately if there’s a winner (or a tie).
  2. Get the name of whoever’s turn it is.
  3. If that person is named “Rando” we’ll pick a random square to add a piece:
public void automove() throws Exception {
if (!winner.equals("")) return;
String p = ((playerOneIsX && turn.equals("X")) || ((!playerOneIsX && turn.equals("O")))) ? playerOneName : playerTwoName;

if (p.equals("Rando")) {
var l = empties();
var c = l.get((new Random()).nextInt(l.size()));
addPiece(turn, c.x, c.y);
}
}

Note that our choice to throw an exception on addPiece has come back to haunt us: We know we can’t raise the exception but Java doesn’t, so we have to have this method throw an exception.

Nonetheless, ridiculously easy dealing with just plain-old code than with the vagaries of user-interfaces, but it won’t last. Where do we call automove? Well, we should call it whenever a piece has been played, since the next move may be the computer’s:

public void addPiece(String piece, int x, int y) throws Exception {
if (state[y][x] != null || !turn.equals(piece)) {
throw new Exception("Attempt to add piece illegally!");
}
state[y][x] = piece;
checkGameState();
if (turn.equals("X")) {
turn = "O";
} else {
turn = "X";
}
automove();
}

But we should also check on the UI-side whenever a name has been changed. We can’t really check in NameChange since that gets called every single letter that’s typed. And if someone is typing “Randolph”, they might not care to have their game stolen by an over-eager, if profoundly dumb, UI.

We should check when the user exits the input field, indicating that he is done selected a name for the player. Here things get a little weird, or at least a little different: If you look at SceneBuilder, you won’t see an onExit or onLostFocus or anything that you can hook to a method to fire when the input loses focus.

Focus is handled using an Observable interface called ChangeListener, which looks like:

package javafx.beans.value;

@FunctionalInterface
public interface ChangeListener<T> {
void changed(ObservableValue<? extends T> var1, T var2, T var3);
}

So we need to attach one of these to the focusedProperty of our text inputs. First, we have to create an appropriate ChangeListener:

private ChangeListener<Boolean> nameChangeListener = new ChangeListener<Boolean>() {
@Override
public void changed(ObservableValue<? extends Boolean> observable, Boolean oldValue, Boolean newValue) {
try {
game.automove();
draw();
} catch (Exception e) {
e.printStackTrace();
}
}
};

Note that we have to wrap our automove call in a try-catch because of our decision to have addPiece throw an exception. It’s far-reaching, isn’t it?

Basically, though, we’re just calling automove and re-drawing the board. (It’d be nice to have the interface know it should draw when the game’s state changes. Let’s look at that next time, on the last (?) installment.

Now, in initialize, we have to attach that listener to our input fields:

@FXML
public void initialize() {

player1.focusedProperty().addListener(nameChangeListener);
player2.focusedProperty().addListener(nameChangeListener);

But we also need to call automove when we start a new game, because Rando could be first:

case "new":
game.newGame();
try {
game.automove();
} catch (Exception exception) {
exception.printStackTrace();
}
draw();
break;

Note again that we have to add the freaking try…catch.

But that’s basically it! We can now have Rando play Rando!

Thrilling!

Whoops! We forgot to attach the “Draws” label to the game ties. No biggie: Just add an injectable field to the controller:

@FXML
public Label tieScore;

Then in the draw field update it like we do the others:

p1Score.setText(String.valueOf(game.playerOneWins));
p2Score.setText(String.valueOf(game.playerTwoWins));
tieScore.setText(String.valueOf(game.ties));

Now, if we run through a lot of games, we’ll get:

Mathematically, that looks about right when the players are random.

Less Stupid

The canonical approach to “solving AI” for tic-tac-toe is a thing called MinMax, which is an algorithm you can use in any turns-taking-game with a relatively small number of finite states. Tic-Tac-Toe has about 255K possibilities, which is relatively small.

The idea, as I (poorly) understand it, goes like this: You make a tree of possibilities for each state. The top level is all the moves for the current player, which are calculated by determining whether the move would win the game for the player. If it would, that gets some arbitrary maximum value (we’ll use 10).

If it wouldn’t win the game, you call the function with the board in that state (i.e., containing the move that didn’t win the game) for the other player, and look for moves that would win for that player. The moves it finds that would win the game for that player are given arbitrary minimum values (we’ll use -10).

A maximum value on either side should end the search, basically. If you find a move that wins, you play that, and if you find a move that allows the other player to win next to term, you avoid that. When those don’t pan out you recursively continue your search at the next level.

Just to add a little depth, we also conceive of a fast win better than a slow win, and a slow lose better than a fast lose, so each level mitigates the end condition.

Quite apart from my solution not being quite right, I’m not happy with the code:

public Coord minMax() {
List<Coord> e = empties();
HashMap<Coord, Integer> m = new HashMap<Coord, Integer>();
for (Coord coord : e) {
m.put(coord, scoreForMove(coord, true, 0));
}
int bestValue = -1000000;
Coord bestCoord = new Coord(-1, -1);
for (Map.Entry<Coord, Integer> entry : m.entrySet()) {
if (entry.getValue() > bestValue) {
bestValue = entry.getValue();
bestCoord = entry.getKey();
}
}
return bestCoord;
}

Basically, we get the empties (all the legal moves remaining), and then we go through each empty and figure out what the score for the move (as described above) is. Then we look through our map of moves to find the best one.

That’s fine, but the scoreForMove is very similar to minMax, in parts.

public int scoreForMove(Coord move, boolean maximize, int level) {
var g = new TicTacToe(this);
g.addPiece(turn, move.x, move.y);
if (!g.winner.equals("")) {
if (maximize) return 10 - level;
else return -11 + level;
} else {
List<Coord> e = g.empties();
HashMap<Coord, Integer> m = new HashMap<Coord, Integer>();
for (Coord coord : e) {
m.put(coord, g.scoreForMove(coord, !maximize, level + 1));
}
int bestValue = maximize ? 1000000 : -1000000;
for (Map.Entry<Coord, Integer> entry : m.entrySet()) {
if ((!maximize && entry.getValue() > bestValue) || (maximize && entry.getValue() < bestValue)) {
bestValue = entry.getValue();
}
}
return bestValue;
}
}

In order to score a new game, we create a new TicTacToe game that copies the current one (by creating a new constructor):

public TicTacToe(TicTacToe game) {
for (var y = 0; y < 3; y++) {
for (var x = 0; x < 3; x++) {
if (game.state[y][x] != null) {
this.state[y][x] = game.state[y][x];
}
}
}
this.turn = game.turn;
this.winner = game.winner;
playerOneIsX = game.playerOneIsX;
playerOneName = "";
playerTwoName = "";
}

We cop the game state and turn, the winner and who’s X but since we’re using the player names to trigger our automoves, we do NOT copy the names over. These tic-tac-toe “games” are just theoretical and shouldn’t be played.

Anyway, with the new board, we move the piece to the suggested coordinate, and if it produces a winner, we assign a score.

var g = new TicTacToe(this);
g.addPiece(turn, move.x, move.y);
if (!g.winner.equals("")) {
if (maximize) return 10 - level;
else return -11 + level;
} else {

If not, we have to go through each empty — this is the part that’s so much like minMax, it makes me squirm:

{
List<Coord> e = g.empties();
HashMap<Coord, Integer> m = new HashMap<Coord, Integer>();
for (Coord coord : e) {
m.put(coord, g.scoreForMove(coord, !maximize, level + 1));
}

We then go through the created HashMap:

int bestValue = maximize ? 1000000 : -1000000;
for (Map.Entry<Coord, Integer> entry : m.entrySet()) {
if ((!maximize && entry.getValue() > bestValue) || (maximize && entry.getValue() < bestValue)) {
bestValue = entry.getValue();
}
}
return bestValue;

And the “bestValue” is either the min or the max, as is appropriate. This is probably where the code goes south.

Oh, and we’re calling the code like we did our Rando code:

public void automove() {
if (!winner.equals("")) return;

String p = ((playerOneIsX && turn.equals("X")) || ((!playerOneIsX && turn.equals("O")))) ? playerOneName : playerTwoName;

if (p.equals("Rando")) {
var l = empties();
var c = l.get((new Random()).nextInt(l.size()));
addPiece(turn, c.x, c.y);
} else if (p.equals("MinMax")) {
var coord = minMax();
addPiece(turn, coord.x, coord.y);
}
}

Weirdly enough, the code doesn’t ever seem to lose as “X”. But if I put in MinMax in both, “X” beats “O” pretty handily about 42% of the time. Better than the 70% losses random “O” has, but it should be perfect. More end up as draws but really all should end up as draws.

This is the point in a book where the author says, “This is left as an exercise for the reader”.

I was thinking of putting up some more effects but the whole tic-tac-toe thing has gotten way boring, so I think the next step will be to put this code up on Github and move on to part II, which will be a puzzle game.

I am a poor, wayfaring stranger, traveling through this world of woe.