Tuesday, July 31, 2012

Science grows on heuristic failures

As I wrote before, the simplest strategy that seems to make sense while being very general and easy to follow on many games consists in aiming straight at your goal while fully ignoring your opponent -- both

  • as the past or present owner of anything on the board,
  • and as an active agent having any potential present or future influence on the board.

It does look dumb! Let's call it Strategy 0. Still, you'll often beat total beginners with it on many games! Provided you couple it with well-known basic short-term tactics deep enough to obfuscate your opponent's vision of what is going on.

I mean, consider Strategy 0 as instructions to evaluate how far you seem to be from your goal. Let's call such an evaluation function Heuristic 0. For example suppose you play ikabegam√° as Light and your goal is the pattern

as before. On any of the three board states below,
Heuristic 0 would say you seem to be 6 moves away from your goal -- since you are ignoring the Dark stones and any future influence of the Dark player. Now don't really ignore your opponent. Evaluate instead how far she too seems to be from her goal according to Heuristic 0. On the three board states above, that would be infinitely far, 1 move away and 1 move away respectively. Admittedly with many more ways to win for her on the 2nd board state than on the 3rd in 2 moves -- we'll refine heuristics later on with such considerations.

Then consider something like the difference between what the heuristic says about you and what it says about your opponent, so that you get a feeling of which player seems to be winning and by how much -- we'll refine that difference computation later on. As Light you would then favor the first board state among the three above, because Dark seems infinitely farther from winning there than on the two other boards.

Then explore the close future of all possible interactions between the two players and minimax, which means chose the move that would look best to you according to the difference above, after your opponent would choose an answering move to your move that would look best to her according to the difference from her point of view, after you would answer to her answer and she would answer to your answer to her answer -- stopping at some predefined depth.

Try it with ikabegam√° or some other games you love. You should make it your first step when building up any game engine or the theory of any game. It's quite exciting already. But don't play too long either with those deep short-term tactics equiped with such a simple strategy, although they certainly feel like on the verge of showing you some hidden knowledge. You should soon try instead to jump beyond and transcend them.

The three board states above are extreme cases showing you how Heuristics 0 can get wrong, since you are indeed infinitely far from your goal on the 2nd board state -- you can't move -- and you are indeed only 1 move away from your goal on the 3rd -- you only have to jump into the middle of Black's formation to win immediately.

By finding where Heuristic 0 can get really wrong with the game, exploring what difference it makes to apply or not apply one of its over-simplifying assumptions, you'll understand something highly rewarding, something transcending most ill-equiped tactical obfuscation. You'll surf through games at a higher level.

As a human, don't feel that much superior to machines either, because you may as well equip your game engines with the same understanding. That's the beauty of an improving sequence of well-defined heuristics, well-defined enough to enter a computer program.