Thursday, December 29, 2011

The time to be spent as a measure of optimal play

The rules in my previous post seem to lack substance when they are played out. If the players have decided to set up the two opposing nests close enough to each others, the first player always win with the strategy to simply rush forward. Otherwise, if the nests are set up far enough, the two players have time to first secure their nest by surrounding them with two layers of their stones. I don't see any way then for them to reach their respective winning goal. We'd better forget about those rules.

More generally, avoid rules or positions where one player may force the game to last endlessly.

Even more generally, try to win in as few moves as possible, or else lose in as many moves as possible. Renown researchers in Game Theory and developers of games engines such as Jonathan Schaeffer and his colleagues at The University of Alberta GAMES Group are well aware that time is part of optimal play.

I don't know however how to justify it. Is it an axiom we can hardly legitimate? Or can it be derived from some other principle that would be more widely accepted?

What I know is, it doesn't show up in most discussions about developing basic ai and game engines.


Most chess-playing engines start evaluating positions with a materialistic account of the pieces on the board, adding 1 for every White Pawn, subtracting 1 for every Black Pawn, adding about 3 for every White Knight, subtracting the same amount for every Black Knight, and so on ... Positional and dynamic advantages and weaknesses are also carefully weighted and added or subtracted, yielding a final score in the form of a real number. The closer the score is to some positive big number, the closer White is to win easily. Symmetrically, the closer the score is to some negative big number, the closer Black is to win easily.

In go, the basic unit of measure might be the stone and its equivalent territory point, all the more as they directly contribute to the winning condition. In Arimaa, it might be the Rabbit or the Elephant or anything else -- there is no consensus yet. And so on.

While this heterogenous approach has made it fairly easy for every engine to compare positions within the same game, there are general flaws with it :
  • You can't easily compare any Chess position with any Go position.
  • You can't easily compare what two different Arimaa engines think of the same position.
  • You must invent specific formulae to combine the score of a leaf and its depth in the tree search
  • Winning easily is not an explicit and well-defined part of the score definition.
A better approach would be to measure the number of moves you expect the players to need before winning, or even better, the time you expect they'll spend.

We'll keep that in mind while exploring future games.

    Wednesday, January 19, 2011

    ikabegam√° - a game to explore

    Here is a game I would like to explore. Let's call it Ikabegam√°, which means "nesting over the other" in Kotava, because it is about swarming into the other player's nest:
    • The features listed in my previous post apply.
    • There are two players. Let's call them Light and Dark and color their respective tokens accordingly.
    • Before the game really starts, the players agree on some board tile to be called the Light nest and another to be called the Dark nest. I'll picture them with an hexagonal ring with their owner's color, for example:
      The farther the two nests lie from each other, the longer the game is going to last.
    • The game starts with only two tokens on the board -- a Light token in the Ligth nest and a Dark token in the Dark nest. All the other tiles start empty. For example:
    • The goal for each player is to get a token of his or her own into the other player's nest.
    • The game is turn-based, the players alternating moves on the board. Light starts the game with a valid move of his choice, changing the board accordingly, then Dark follows with a valid move of her choice, changing the board accordingly, then Light follows and so on.
    • The rules for valid moves are the same as for the game of Hexxagon. In other words, a valid move for Light is
      • either a growth -- Light fills in some empty tile of his choice with a new Light token, provided at least one of the 6 adjacent tiles is already occupied by a Light token. For example the following position
        yields 3 valid growths for Light, which I'll picture with small Light tokens hovering above the empty tiles:
        Light is allowed to choose only one of them during a single turn.
      • or a jump -- Light moves some Light token of his choice on the board two tiles away from the tile it currently occupies, provided the destination is empty. (Two tiles away means adjacent to an adjacent tile, but not immediately adjacent nor the same tile. There can be from none to twelve possible destinations). Except for the source and destination, it doesn't matter whether any other tiles are empty or not. For example the position above yields 12 valid jumps for Light, which I'll picture with small Light tokens hovering above the empty destination tiles and a small empty tile hovering above the jumping token:
        Light is allowed to choose only one of them during a single turn.
    • After Light has either grown up or jumped and changed the board accordingly, some automatic flipping occurs : any Dark token adjacent to the newly occupied tile is turned into a Light token, thus changing owner and color from Dark to Light. I'll picture them with small light tokens hovering above them. For example if Light chooses to grow onto the left, two Dark tokens are replaced by Light tokens. Here is the position, the chosen move, the resulting flipping and the resulting position :
    • It is then Dark's turn and the same rule applies to Dark, with Dark tokens instead of Light tokens and Light tokens instead of Dark tokens. For example on the last position above, Dark may now choose to jump downwards, thus turning two Light tokens into Dark tokens :
    • The players must always choose a valid move as above if they can -- either a growth or a jump, not both, and only one. If they can't because they don't have any token left on the board or their tokens are completely surrounded by opposing tokens at distance 1 and 2, they pass and it is the other player's turn.
    • The game is over as soon as
      • either some Light token occupies Dark's nest, in which case Light has won the game,
      • or some Dark token occupies Light's nest, in which case Dark has won the game.
      It doesn't matter whether the nest is newly occupied from growing, jumping or automatic flipping.