Tic-tac-toe and the minimax algorithm: playing imperfect players

I saw an interesting here's-how-it-works post about the minimax algorithm in the context of Tic Tac Toe. I wrote a tic-tac-toe player myself a few years ago, for a HackerRank puzzle, and of course back in the Dark Ages when I was doing my MS in Computer Science.  But in this particular post, Jason Fox makes an interesting point: a perfect tic-tac-toe strategy is fatalistic.

While testing his player, he noticed that once the bot saw it couldn't win, it didn't seem to care how long it took to lose. He modified his algorithm to prefer longer fights, just to make it seem like it was putting up a fight.

Why would this behavior occur? And why does it bother us? Turns out it's simple: a perfect strategy assumes that its opponent is playing a perfect strategy as well, because that's easier to code. In other words, when scoring the different options, the perfect minimax strategy assigns its values by playing the other side perfectly as well. Mathematically, it doesn't matter whether we lose perfectly earlier or lose perfectly later, does it?

But that glosses over a fundamental truth out here in the world, and it's why it rankles to see this algorithm playing so oddly - when playing actual games, it's not at all uncommon for our opponent to screw up. And the longer we draw out the game, the more likely it is that they will. So intuitively, we want to fight a delaying action, because our own internal algorithms tell us that the longer we're in the game, the better off we are in terms of an eventual surprise win.

To reflect that, the tic-tac-toe minimax algorithm should really be modified to reflect the probability of error on the part of the opponent. Even a small change in that score should serve to weight longer fights a little higher, and that's enough for the algorithm to choose that path.

It would be instructive to write that up as a real article, but man, I've got stuff to do that's higher priority than that.

OpenWorm

OpenWorm is a project to build a full model of a nematode.

Minizinc

Minizinc is a language specifically for constraint programming problems.  It's showcased a little in this article using it on a recent xkcd [oops, not so recent: 287].

Listed under AI unless I get a bee in my bonnet about constraint programming, which seems unlikely.

GAWK as an AI language?

Here's a fascinating little post from the 90's about how programming students doing AI do a better job with GAWK, which permits (forces!) them to take a high-level view of the process and let Unix utilities do the detail work.

Neat!

simpleai - Python AI library

Basic implementations of the algorithms in Russell and Norvig, in Python.

Ontology

Hey, look: a free huge ontology at ontologyportal.org!

Command and Conquer in JS

This is apparently a complete implementation of an existing RTS game Command & Conquer in HTML5/Javascript.  Which is really pretty amazing.

Catch the cat

Here's a cute little Flash game that is both surprisingly solvable and surprisingly challenging.  Very bare-bones - you have a grid of circles and click them to keep a cat from escaping the grid.

It would be a good AI target, actually.  I think this may be a case where it would be interesting to explore simple semantic structures of some kind (grouping areas into some kind of cage element or something). I'm not sure.  But it would be interesting to explore.

AI Sandbox

The dudes at Guerilla Games (no, I never heard of them, either) have released AI Sandbox, a neat platform for writing in-game AI, with a contest to write a Capture the Flag captain.

That is the very definition of cool.

I may find the time - somehow - to wedge that into my day this month.

One of the prizes is a free ticket to the Vienna Game/AI conference in 2013, a September event I really wish I'd known about in September!  If we're still here in Budapest next September, I may well go on over and check it out.

Gray code and Kohonen maps

A Gray code is a binary encoding of numbers where neighboring numbers differ by only one bit.  I actually independently invented this in the summer of ... must have been 1995, I guess, reasoning backwards from life events.  I implemented it in Visual Basic as an experimental memory based on Kohonen maps, then lost the code.  Every now and then I try to reconstruct it, but get lost in the Gray code concept - and today I learned it has a name!

Ah, the Internet.  Life is so much better with it.

I really need to reconstruct that research thread.  It was a good one.  The idea was to use a Kohonen map as the index for a semantic space, with semantic units encoded as vectors of keys into the map.  Thus each key self-organizes into a self-describing semantic unit that can be expanded into its components in an organic way in working memory.  Or something.  I really need to reconstruct that.

core.logic

Relational programming and constraint logic programming for Clojure.  Good links to follow, should I ever get the time to look at this stuff again.

Z3: an efficient theorem prover

Z3 is a theorem prover being developed at Microsoft Research that has been published under a quasi-open source license this week.  Interesting.

Neural networks in JavaScript

brain, a JavaScript library for neural networks.

ZYpp and SAT solvers

Here's an interesting thing: the new package manager for PHP is apparently based on ZYpp, which includes a full-power SAT solver.

Another robot competition

Scribd has a fun little competition up for robot programming.  Nice Javascript tutorial space!

Kohonen maps in Perl

Just so I don't forget it, there's a Kohonen map implementation on CPAN.

I once wrote a rather nifty implementation of Kohonen maps in Visual Basic (it was another country, and besides, the wench is dead), but lost it years ago. Nice graphical demo, too. Always a shame when software gets lost.

Google AI challenge

This year's Google AI Challenge is a robot-army kind of tournament. Looks fun! But is that AI?

XSB Prolog

XSB is an open-source, tabled (i.e. memoized) Prolog. It has a Perl binding. It would be interesting to pursue. Very interesting, actually.

HNN: what data structure does the brain use?

I didn't expect much from this thread, but it ended up chock full of interesting things to follow up.

Final flurry of Stanford-related links

Here is a fantastic compendium of "nature-inspired" AI algorithms, each described with pseudocode and Ruby. It's this kind of thorough survey work that really makes my world go round.