Friday, November 10, 2006

Lines of Action

Title: Lines of Action
Author: Benjamin Guihaire
License: Freeware

As a young lad, I happened upon a copy Sid Sackson's Gamut of Games in a used book store, a great find. It contains a wonderful collection of rules for abstract strategy games, many described for the first time. One of my favorites from this book is Lines of Action, a simple but deep game invented by Claude Soucie. I subjected my siblings to many games of Lines of Action way back when. I recently remembered the game and went searching for a good computer opponent.

Lines of Action is played on a checker board with twelve pieces a side. The complete rules are available at the Lines of Action Homepage. The goal is to connect all of your pieces. Each turn, one piece is moved horizontally, vertically, or diagonally. The main rule is that the number of spaces a piece can move is equal to the number pieces, friendly and unfriendly, in the row, column, or diagonal of motion. You cannot move over an opponent, but you can land on opponent removing it from the board.

What has always fascinated me about Lines of Action is the lack of an easy heuristic to evaluate positions. Games like chess and checkers have simple material heuristics. One thing you will quickly learn about Lines of Action is that a material advantage is not a good indicator of who is winning. With fewer pieces it is easier to connect them. Some rough guidelines I have learned from playing over the years are that you want to connect your pieces, try to isolate one or more of your opponent's pieces, and keep your piece mobility high. This is all easy to say, but I still do not know how I would go about writing a subroutine to evaluate Lines of Action positions.

It turns out that there are many Lines of Action programs out there. I like Benjamin Guihaire's program the best. It has a simple interface and plays a reasonable game. There are ten skill levels. The easiest level can be beaten without much thought. The middle levels kick my butt, but I do not claim to be a good player. One fun thing about his program is that it includes several alternative starting configurations.

I do have two minor issues with Guihaire's program. First, when the computer wins, I brings up a "black has won" dialogue box before displaying the winning move. Second, clicking on help sends your web browser off to a site which does not exist any more.

Guihaire's program is considered weak compared with some of the best ones out there. Here are a couple of others. Mark Winands' MIA program is one of the strongest in the world and free. I find its interface confusing though. Mark wrote a Master's Thesis on Lines of Action which is worth a read. There are two others offered up by The University of Alberta GAMES Group: Mona and YL. They have a JAVA Applet which proports to allow you play against them online, but always get "Error: Could Not Connect To Server(" after my first move.


Post a Comment

<< Home