Programming Tic-Tac-Toe in Java

<<Previous | ToC | Next >>

AI Plays to Win

This module assumes you have written and got running the TTT scoring program in Java, or else you have written and got running the same program in the English computer (see also "English" notes all through the design phase up to here). This segment adds the logic for the computer to play a credible "O" game using "Good Old-Fashion AI" ("GOFAI" pronouncerd "Go-fye") techniques, which for applications like this plays better, is both faster and easier to program, and is far more understandable and credibly explainable, than a Neural Nets program is likely to achieve.

Each time I do TTT on a new platform, I rethink and rewrite it from scratch. Sometimes it comes out better, sometimes not so good. I think this must be the third or fourth time I've done it in Java, just in the last couple years. Basically we want to iterate over the whole board, looking for blank squares that we might want to play in. For each of those squares, we want to consider every run of three that goes through that square (there are eight), and then count the X's and O's in that run. Something like this:

Let doing = 0
repeat 9
  add 1 to doing
  if {board[doing] is played} then again
  let all8 = "123,456,789,147,258,369,159,357"
  repeat 8
    let run = {first run in all8}
    {delete first run from all8}
    {if doing is not in run then again}
    let psum = 0
    repeat 3
      let sqr = {first character in run}
      {delete first character from run}
      if {board[sqr]} = who then add 1 to psum
    {add to score for this square, according to sums}
  {save best score and its square#}
{play the best square}
if {its score is} >90 then let won = true
Of course this vague description won't run on any computer, but I wrapped braces around those parts that need clarification. Some of those you already know how to do, maybe with a hint or two. Knowing if a board position has already been played I think you already did. Copy it to here, or make a subroutine to do it both places.

Picking a run out of the list of eight possible runs, you can use the Substring command. You can either delete it (using another Substring command) so the next run is first, or else increment the offset to get the next run.

Knowing if the run you are looking at contains the blank square under consideration is somewhat more awkward. You can add some special code to take out each of the three squares in that run and compare them, but I see that I am already looking at each square to see if it is equal to variable who, so I decided to insert another test to see if that square number =doing, and if so, set another variable ok = true (initialized false). After that inner Repeat, when evaluating the psum for that run, I can ignore it unless ok=true.

My original thought was to make the inner loop be its own subroutine, so I named it "CountMarks". Later I realized I need counts of both the X's and the O's, and it makes more sense to add up both sums in the same iteration, because everything else is already there. But Java only returns a single number from a subroutine, so why not make that the whole goodness score for each blank square. But I kept the "CountMarks" name for no good reason.

I did not include the outer loop through the nine squares in the same subroutine, because I also realized that this could replace the ThreeInaRow subroutine for knowing if the current player won, and that only needs to evaluate a single doing, where that player played their X or O..

My vague description only adds up the number of O's (assuming the computer plays "O"), but you need to add up both X's and O's in separate sums. I think you can add that.


Let's think about that goodness score we want to develop for each blank square.

Obviously we want a maximum score for choosing a winning play, and a high (but not as high as a win) score for block an opponent's win. Less than that, we want to decide on a strategy for playing in runs that have only one or no other marks already there. It only makes ssense to consider a run with both X and O when playing out a cat's game, so that would add nothing to the goodness score. We need to initialize a best so far score negative, and the square it was evaluated (initially not a valid square, =0), then for every time through CountMarks, compare the returned goodness factor to the best so far, and if better (the first will always be) save that goodness as best, and the square as where we will play after the iteration completes.

So a run with one X and one O adds zero to the goodness.

A run that is completely blank might be a good play, or only so-so, depending on your strategy. You might score a run with a single X more if you favor blocking, and a run with a single O more if you favor aggression. I allowed three values (1,2,3) to be distributed variously for those three kinds of runs, your choice. Experiment after you get it running, maybe it makes a difference, maybe not (I don't know).

When you are evaluating the goodness factor for the center square, there will be four runs to add up; if every run neither win nor block, but otherwise the best you can do (3 points), then the maximum for square 5 would be 12. To know any other square is a block, it must be greater than 12 (I chose 15, but it mostly doesn't matter). If every run through the middle is a block (that's impossible, but just to be safe) the maximum block score is 60, so the minimum win goodness score would need to be greater than that, perhaps 61 or 70 or 99. Again a goodness score of win in all four directions is impossible, so you cannot get more than 400 (or 244 or whatever). But your decision to play is based on the maximum actual goodness.

So we start with the existing English program we used as the basis for the TTT scoring program in Java (and English). We will change one line in that program to insert a call to our new PlayO subroutine which replaces the human input for that half of the game. The added code is shown in red (nothing is deleted) Everything else is unchanged:

  print "input for " who
  if who="O" PlayO
  otherwise Repeat
    Input play -1
    Round play
Then of course we need to write the PlayO subroutine, which is basically the outer loop of my vague description above. We can do it first in English (optionally tested in English), then if you are so inclined, you can convert it to Java to play either on the console with ASCII graphics, or else in the GameEngine (the same Java PlayO subroutine would work in either).

If you wanted, you could have the same subroutine play both X and O, in which case the game would be a rather predictable Cat's every time, which is not very interesting. So I assumed this is a PlayO subroutine.

Most of the work will be done in a goodness scoring subroutine CountMarks which is everything else (the inner two repeats) in the vage description at the top of the page.

Your mission, "should you choose to accept it," is to write the English version of the PlayO and CountMarks subroutines (or if it's too hard, not), and then turn the page.

<<Previous | ToC | Next >>

Revised: 2021 September 18