Posts Tagged ‘game AI’


October 23, 2007


I’ve been enjoying playing the game Connect6 with my son Adam. The game was invented and introduced by Professor I-Chen Wu, from National Chiao Tung University in Taiwan. Connect6 is played with a Go board and stones. The object is to place six stones in a row, diagonally, horizontally, or vertically. On the first turn, Black places a single stone; after that each player places two stones per turn. Because each player will always have placed one more stone than his or her opponent after each turn, the game appears to be balanced.

One potential concern about this notion of balance is that perhaps the second player should place his or her stones far from the first stone, to get a two-stone advantage somewhere else on the board, and possibly forcing the first player to follow in that part of the board. Fortunately, Wu and a colleague demonstrated that this initial break-away strategy is unlikely to be good for White in this paper.

Anyways, it’s not clear whether with perfect play the game should be a win for the first player, a win for the second player, or a draw (with neither player ever able to achieve six-in-a-row.) If I had to guess, I would venture a draw, even on an infinite board, but on the other hand my actual games have all ended in victory for somebody.

The game is very similar to Gomoku (also known as Connect 5), where one tries to get five stones in a row, but each player only places one stone at a time. Of course, that game favors the first player, and in fact it has apparently been demonstrated that the first player wins with perfect play.

Renju is an older and much less elegant approach to balancing Gomoku. In Renju, the first player is restricted from making moves which make certain types of threats. Looking at all the complications in the Renju rules, I find it surprising that it took so long for Connect6 to be introduced.

In fact, aside from the issues of fairness and elegance of rules, I also find that Connect6 has a more dynamic feel than Gomoku or Renju; I definitely prefer it.

Because of the large number of possible moves each side can make each turn, and the difficulty of evaluating a position, it’s not easy to program a computer to play Connect6 well; I don’t think any programs exist yet that play as well as humans. You can play Connect6 against some relatively weak bots and other humans at Vying Games, which also features other interesting turn-based strategy games (currently Checkers, Pente, Keryo-Pente, Phutball, Breakthrough, Othello, Kalah, Oware, and Footsteps).

Zillions of Games

August 2, 2007

Visit Zillions of Games

If you like abstract games, especially chess variants, you should enjoy Zillions of Games. It’s quite an amazing piece of software; a piece of AI technology that I actually would have not thought possible.

Games are defined using a rules file (written in a Lisp-like language), and then a generalized alpha-beta search engine is unleashed. Basically, it works best for Chess and its many variants, but it plays a really surprising number of games very well. It comes with over 350 games and puzzles, and you can download thousands more.

It’s not that hard to modify existing rules files to define new games; my son was interested in having an opponent for a game he invented and we were able to modify an existing rules file to play his game in less than an hour–and it played very well.

Naturally, it doesn’t play all games as well as humans, but it plays so many games so well (with adjustable levels to make a fair fight if it’s too good) that one can’t complain. Unfortunately, it’s only available for Windows computers.