Programming Tic-Tac-Toe in Java

Other Data Representations

This whole page is optional, only necessary for programming excellence. Most real-world programs don't need this skill. The history part here at the front is optional to the optional, it won't hurt if you skip down to the tech stuff.

Some of the links in this page are not accessible from the NWAPW website, they are on my own website, which is blocked by some firewalls, but generally accessible from home, anywhere outside institutions where they worry about that kind of stuff.

Personal History

I always wanted my own computer. When I was in high school I collected surplus electronic parts, and somewhere I picked upsome 200 dual-triode vacuum tubes (you can make a single gate or flip-flop from one of them) along with filament transformers and sockets to mount and power them: I was going to build my own computer. I didn't have a clue. I later worked with engineers who knew more about the hardware than I did, and eventually learned enough to actually design a working computer. By then I was much more into software, so I wrote a hardware gate simulator in software, and built my design entirely in simulation (see "GateSim" for the simulator). Maybe some day I'll convert that code to be Java.

I eventually got my own computer by trading some software for it, but it was the very first (publicly available) microprocessor, with a tiny 4-bit 4004 CPU and only 320 bytes of main memory. I designed and built a disk operating system (including the hardware, one of the first 8" floppy disk drives) so I could load and run programs off the disk drive. I think the first game I wrote for it was Tic-TacToe. That became sort of a benchmark for a new computer language.

Bigger computers became available, and everybody wanted Basic, but Bill Gates wanted $150 for his Altair BASIC, which everybody thought was highway robbery on a computer that barely cost three times that, so somebody who knew a lot more about how these things work than I did wrote an article "Build Your Own Basic" in what became Dr.Dobbs Journal, and I understood it well enough to make "TinyBasic" run on the home computers then available. I wasn't the first, and more people used some other version than mine, but I charged $5 for my TinyBasic (everybody else gave theirs away free) and I guess that made it memorable, so everybody fondly remembers running my TB on their Altair (nevermind that I never wrote anything that ran on an Altair). One of the first programs I wrote to run in TB was TTT (see "Tic-Tac-Toe in Tiny Basic" now part of my TinyBasic archives). TB had no arrays, but it had raw memory PEEK and POKE functions that could be used that way. It barely fit in the amount of memory most people started out with.

Some time later I did another TTT version -- or maybe it was the 4004 version, I no longer remember -- for a programming language with no arrays but it had logical operators AND and OR that worked on integer bits. So I did it that way.

Why Bits

Basically, the bits of a binary number can be understood as an array of boolean (true/false values), and the bitwise operators in Java (and C) give immediate and fast access to individual bits. Computer hardware always had these operations (it's the basic building block of digital logic), but people think in decimal where these operations don't make much sense. C is a very low-level language, designed to expose the hardware of the DEC PDP-11 to programmers who understood only Fortran, but Fortran was too big to compile on the PDP-11, so we have three generations of programmers who learned C in college and program as if for the PDP-11 -- nevermind that modern computers have a very different in architecture, so modern C compilers must undo all the "optimizations" the C programmers wrote into their code and restructure it for the actual hardware, with the result that hand-written C code often ran slower than other (high-level) languages which didn't do all those skanky things, even though some of those other languages compiled to the same C that the hand-written code was written in. Yes, that really happened, (I think) at the University of Tasmania. They did a formal study: the C programmers made six times more errors, many of them not even possible in the alternative.

When microprocessors became big enough to support small compilers like C we got a whole new generation of programmers forced to think in binary. Microprocessors are now bigger (both logical size and memory) and faster -- the smart phone in your pocket is thousands of times more compute power than the PDP-11 that C was designed for -- so programmers no longer try to "optimize" their C code (if they use C at all) with the result that nobody thinks in binary any more, we are all back to thinking in decimal, and using our limited cognitive resources for solving bigger problems instead of trying to force small problems into smaller computers.

Me, I petulantly refused to write a single line of C code for some 20-odd years -- until I had to teach it -- but by then I was already teaching Java, so I taught it as "Think in Java, code in C." I still think in binary because my first microprocessor programs were coded in machine language. But I don't recommend it. Except when I thought of doing TTT in Java, my first thought was to implement the arrays as bits strings in integers. Silly me, nobody thinks in binary!

But if you want to be a super-programmer, you probably should know how to think in binary. And Java supports it. So a top-notch Java programmer knows how to use those bit operators. To get started, be sure you have read and understand the (optional) "Bitwise Operators" page. If it's too heavy, not to worry, you can be a fine programmer just thinking in decimal, just skip to the bottom of this page and maybe come back some other time.

Using Bit Arrays in TTT

The Tic-Tac-Toe game board has nine squares, each with a minimum of two bits of data (X, O, or neither). This can be implemented with bit arrays in one or two single integers, but there's no advantage to packing it into one.

The numbered bits, starting at the least significant bit as bit 0 (value 2⁰ and accessible as 1<<0) and generally bit n is accessed by shifting 1 left n places to form a single bit mask that can be applied by the AND (&) and OR (|) operators, and has a numerical value 2ⁿ.

What we in English wrote as

let tmp = board[n]

we would do in a Java bit array with the & operator as

tmp = ((board&(1<<n)) !=0);

where tmp has been declared boolean, or

tmp = ((board>>n)&1);

where tmp has been declared int (but its value would be either 0 or 1).

Putting a single bit aBit in uses the | operator, like this:

board = board|(1<<n);

To get two bits, we can let one of the bits be where X has played, and the other where O has played, so our subroutine "Update board" looks like this:

if (who == 'X') Xboard = Xboard|(1<<play);
else if (who == 'O') Oboard = Oboard|(1<<play);

Since we are no longer storing the square numbers in the board, we use the square number itself (step in our English code for subroutine "Show current board") to display an empty square, like this:

if ((Xboard&(1<<step)) !=0) square = 'X';
else if ((Oboard&(1<<step)) !=0) square = 'O';
else square = (char)(step+48); // 48 = '0'

More important, you can test for 3 in a row all at once in one line:

if ((Xboard&0x00E)==0x00E) won = true; // bits 1,2,3 = 0x2+0x4+0x8
if ((Xboard&0x070)==0x070) won = true; // bits 4,5,6 = 0x10+0x20+0x40
if ((Xboard&0x380)==0x380) won = true; // bits 7,8,9 = 0x80+0x100+0x200
if ((Xboard&0x092)==0x092) won = true; // bits 1,4,7 = 0x2+0x10+0x80
if ((Xboard&0x124)==0x124) won = true; // bits 2,5,8 = 0x4+0x20+0x100
if ((Xboard&0x248)==0x248) won = true; // bits 3,6,9 = 0x8+0x40+0x200
if ((Xboard&0x222)==0x222) won = true; // bits 1,5,9 = 0x2+0x20+0x200
if ((Xboard&0x0A8)==0x0A8) won = true; // bits 3,5,7 = 0x8+0x20+0x80

You can iterate this in one line with a table lookup for the eight bit masks:

for (int nx=0; nx<8; nx++) if ((Xboard&masks[nx])==masks[nx]) won = true;

Testing for one or two in a single row, you can (temporarily) play the candidate position, then see if it's 3 in a row. Another, faster but more obscure, way depends on some little-known facts about single bits in integers (see "Get Next Bit" in the "Extras" page), namely that(num&-num)==numwhenevernumis a single bit (or zero). It takes a few simple steps, where the first can be a table fetch if you want to iterate the process:

int tmp = Xboard&masks[nx]; // bits from the three squares being tested
int one = tmp&-tmp; // !=0 is the low bit of the three
Xsum = 0;
tmp = tmp-one; // what is left, after deleting the low non-zero bit
if (one==0) {} // this row has no X
else if (tmp==0) Xsum++; // this row has exactly one X
else if ((tmp&-tmp)==tmp) Xsum = 2; // this row has two Xs
else won = true; // this row has three Xs

It's very obscure, but if you pencil-and-paper it (or step through in the debugger) for different board values, you can see how it works. And once you understand how to do this kind of thing, it's good for bragging rights among experienced programmers.

Do you think you can convert your TTT game to use bit arrays?

After you have it working, you are finished with TTT. Then (or otherwise) perhaps you might want to browse some of the other chapters you nave not yet read.

<<Previous | ToC | Next >>

Revised: 2021 October 2