In my second year of my computer science degree there was an introductory AI course as part of syllabus. Widely touted as the closest to sexy (or indeed socially acceptable) aspect of computer science, AI may sound like it's brimming with robots learning to walk, fictional enemy soldiers drilling you full of bullets, and computers making idle conversation of a cup of tea and a biscuit. In fact, AI is an intriguing mix of good ideas and monotonous theory. Fortunately, I hadn't been expecting any car chases or explosions, and I found it to be one of the better courses of the year.

The reason I tell you this is that one of the good ideas driven by a lot of theory is the minimax algorithm (with a dollop of alpha-beta pruning for good measure). Although it's fairly old-hat now, the basic idea is that you can make computer play a game by getting it to find all the possible moves it can make and then assess what would happen if it took them. And in assessing, it looks at every move it opponent might make. And every move it may then make in response. Etc etc etc, until it ends up with a game state where someone has won. From this big tree, and then can decide which is the best path to take, and make its move accordingly. Doing that takes a lot of processing power, though, so unless the game is trivial, it's best to just make it look a certain number of moves ahead, and then make a guess from there, using some heuristic. Alpha-beta pruning offers further savings by allowing the computer to bail out of certain branches when it's clear they're pointless. Wikipedia has good articles on both minimax and alpha-beta pruning.

In order that all those in the lecture theatre really understood the concept, the lecturer suggested we all try to write a 4x4x4 noughts-and-crosses minimax AI. Obviously, I quickly dismissed the proposal as a waste of time which could otherwise be spent playing pool. It wasn't until the summer holidays, after I had attempted questions on minimax in the exams with a relatively partial understand, that I thought I'd see if it was as easy as he had suggested.

So, here is the result. OsaXs. I pronounce it 'OSS-acks', but I don't really care what your take on it is; it was just a quick abbriviation of 'noughts-and-crosses' I used and has since stuck. OsaXs was originally written in plain old Java, but when I bolted the pretty 3D bits on top I thought I would use processing as an alternative to the painful process of learning how to do pretty 3D in real Java.

Thanks to Java (and processing), you should be able to play OsaXs on your Windows, Linux or Mac computer. Just select the relevant file to download. Installation should be as simple as extracting and running the executable on Windows and Linux (i.e. just double clicking osaxs.exe, in Windows). For Mac, I have no idea. I have just zipped up the contents of the folder processing provides me when I compile. Hopefully that should be enough. If anyone has more of a clue, feel free to let me in the secret.

The controls are explained when it first loads, but as there's currently no way to bring that up mid-game, I'll run over them here. To move the lit up box (i.e. the cursor) around, use the w/a/s/d/p/l keys. To rotate the cube, drag with the left mouse button. To zoom, drag with the right mouse button. To view only the layer with the cursor in, hold down the shift, ctrl or alt keys. To take your go where the cursor is, press space or enter. Pressing 'o' toggles the option screen. Options are navigated with the arrow keys and cycled through with space or enter.

If the cursor is green, it's your go. If it's red, it's the AI's go. If it's purple, somebody has won, and there should be a big message saying who across the screen. If it's sticking on red for ages each go, try turning down the difficulty in the options, as it will make it think less.

Finally, be aware that it is entirely deterministic, so if you keep playing the same moves, it will keep responding in the same way. So no hope that it 'might not notice this time', and equally, if you find a way to beat it, you'll be able to beat it like that every time. And you definitely can beat it - I've managed 'Impossible' in 45 moves, and I suspect brighter and/or more determined people can do better.



Downloads: - Windows distribution - Linux distribution - Mac distribution