Zenix 

Copyright (c) 2000 Jürgen Heel

Each player has 12 stones. The game is played on the following board.

 
  • GOAL - Wins the player with the longest chain of his own stones.
  • MOVE - On each turn, each player can: 
    • Remove one empty cell - each player can only do this six times.
    • Drop a stone into an empty cell
    • The two cells below the chosen cell (either to remove or drop a stone) must not be empty (i.e., were removed or already have stones).
 
An example

In this game, Black has won, since Black's longest chain has 7 stones, and White's has only 4 stones.

David Glaude has a website with more information about Zenix:

Complexity of the game. As for every game I am interested to know if it is easy to play the game for a computer. I also want to check what is or could be the theoretical value of the game. And if the game seems to be a win or not to difficult to prove.

The most interesting problem with Zenix is to determine who is the winner. It might be obvious for a human, but for a computer it is not so easy. Let say that finding the winner is equivalent to finding the longest path in a graph. And finding the longest path in a graph is a complex problem with no good algorithm to find the solution. So a silly algorithm like a recursive search with back-tracking might be the best one we have. Now given the size of the board, it is not too long to compute, but however exponential in time.

Now for a computer to play the game, we might want to have an evaluation function that can evaluate the longest chain possible for each player or the current longest one. Even if the length of the game is rather short (only 36 moves) and the number of possible legal move is small too (16 for the first move then dropping to 14 and below)... The cost to find who is winning might be the biggest challenge for proving of evaluating the game.

If finding the longest path for a player is difficult. But we can find an upper bound for the longest path is easy. At the maximum we have 12 because that's the number of pieces available for each. Then the maximum is also the number of adjacent piece (+ all the piece remaining) this mean if a few pieces are isolated from the rest, they don't count as part of the maximum.

There is a ZRF to play Zenix.