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 Dark'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.

Monday, March 19, 2012

Assuming passive opponents - Beginners meet Pólya and Pearl

When you are playing a game you've never played before or when you are designing a new playing engine, a good, universal and natural starting point is to try to get as close as possible to your winning goal as if there wasn't going to be any other player acting on the game.

It makes your first strategical concepts easier to design, because it is often about finding shortest paths or solving a solitaire puzzle.

I think most children do that when learning a game. I do. I would like to see it applied as well in any basic discussion about understanding a game.

More generally, you might look at the game rules and ignore some part. First the part that tells "there is another player" as I said. Then some other part if needed, such as "there is some other player's stones on the board" or some spatial dimension, flattening the board. It's like Generalization or Constraint Relaxation suggested by Geoge Pólya in Mathematical Research or by Judea Pearl in Computer Search.

In Chess for instance, it makes you focus on quickly threatening your opponent's King while cutting its escape routes and other anti-check answers in one move. It's infinitely much better than playing randomly.

The next step is then to add some concern about your opponent's distance to her own goal. How is she close to her goal? How can you slow her down? How can you keep getting closer to your own goal at the same time? How can you prevent her from slowing you down? How can she prevent you from preventing her... ?

Thursday, January 19, 2012

ikabegamá 2

Here is a new game with seemingly more interesting rules.

No tiles are distinguished from any others. The players agree on some starting setup consisting of some of their stones already on the board. For example:
The players also agree on some goal pattern or patterns which make them win as soon as some or all are achieved on the board. For example Light might win as soon as the following pattern of Light stones shows up locally anywhere on the board:
and Dark migh win as soon as the same pattern with dark stones shows up locally anywhere on the board:
The other rules are otherwise left unchanged from the first game ikabegamá in this blog. Let's call this game ikabegamá as well, adding 2 to the name only when the distinction is needed.

Here is a sample game with the starting setup and goal patterns as above. The two players are naively building up their own pattern apart from each other until Dark realises Light is going to win and it is too late to change that - except to postpone it one turn. The pictures show the board position after every move. The moves are shown by transparent reduced previous versions of every tiles that has just changed.

012345678910111213


(game over, Light wins on move 13)