$ ./lines
Lines of Action V1.2
(c) 1984-1987 by Stephen A. Ness.
Type 'h' followed by <return> if you need help.
X moves first.
+---+---+---+---+---+---+---+---+
|   | X | X | X | X | X | X |   | 10
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 20
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 30
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 40
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 50
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 60
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 70
+---+---+---+---+---+---+---+---+
|   | X | X | X | X | X | X |   | 80
+---+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7   8
? h
Commands:
        d3      Set tree search depth to 3.
        e       Evaluate current position.
        h       Print help information.
        i       Initialize new board.
        l       List game on console.
        lfile   List game to file.
        m       Generate next move.
        m1234   Move from 12 to 34, then generate reply.
        M1234   Move from 12 to 34, do not generate reply.
        p       Print the board.
        q       Quit.
        r       Print rules.
        u       Undo most recent move.
        v       Print move generation information.
        w25     Set tree search width to 25.
        xfile   Execute moves from list file.
        !cmd    Pass cmd to system for execution
                (COHERENT, MSDOS only).
A command must be followed by a <return>.
Player X moves next.
? v
? d5
Old search depth is 3.
New search depth is 5.
? w50
Old search width is 25.
New search width is 50.
? m1234
+---+---+---+---+---+---+---+---+
|   |   | X | X | X | X | X |   | 10
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 20
+---+---+---+---+---+---+---+---+
| O |   |   | X |   |   |   | O | 30
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 40
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 50
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 60
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 70
+---+---+---+---+---+---+---+---+
|   | X | X | X | X | X | X |   | 80
+---+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7   8
Generated 1930637 moves from 53093 positions.
Evaluated 860011 positions.
Maximum width 47.
O moves 38-35.
+---+---+---+---+---+---+---+---+
|   |   | X | X | X | X | X |   | 10
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 20
+---+---+---+---+---+---+---+---+
| O |   |   | X | O |   |   |   | 30
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 40
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 50
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 60
+---+---+---+---+---+---+---+---+
| O |   |   |   |   |   |   | O | 70
+---+---+---+---+---+---+---+---+
|   | X | X | X | X | X | X |   | 80
+---+---+---+---+---+---+---+---+
  1   2   3   4   5   6   7   8
?q
$				

Lines of Action

Sid Sackson's book A Gamut of Games (Random House, 1969) describes the two player board game Lines of Action (cf. pp. 34-39), invented by Claude Soucie. It is played on a standard checkerboard with simple rules:

Object: get all of player's pieces into one connected group. Horizontally, vertically or diagonally adjacent pieces are connected.

Movement: A piece may move horizontally, vertically or diagonally, but it must move exactly the number of squares given by the total number of pieces (friendly and enemy) in the row, column or diagonal of movement. A piece may jump over friendly pieces, but it may not jump over enemy pieces. A piece may land on an enemy piece, removing it from the game, but it may not land on a friendly piece.

Each player starts with 12 pieces; the first player has six in the top row of the board and six in the bottom row, the second has six in the left column and six in the right column. Unlike most board games, capturing an opponent's piece is not necessarily a good thing, as it makes connecting the remaining pieces easier.

When I was a computer science graduate student at the Stanford in the early 1970s, I occasionally played Lines of Action with my friend Dave Poole at the Stanford Artificial Intelligence Project. Other students at AI were working on chess and checkers programs, so I decided to write a program to play it. My program could record a game between two human players, or a human could play against the computer. I have files recording three games I played with Poole on 10/12/72, including one time-stamped 1972-10-12 03:58 POOLE3.LOA [MTC,SAN] 640. We were playing at 4 am; we burned a lot of midnight oil at the AI Project.

I wrote my program in SAIL (as a local wag said, "Suitable Acronym Isn't Locatable"), an ALGOL-like language developed at Stanford AI. It ran on the AI Lab's PDP-10. My SAIL source file loa.sai dates from 10/12/72. This is my earliest computer program to survive as a computer file, though I have paper copies of earlier programs. At the time, it was one of the more complicated programs I had written.

The program played against a human using a standard alpha-beta pruning technique, evaluating each board position by computing weighted distances between groups of pieces. By default, it looked only three half-moves ahead and looked only at the 15 best moves at each level; you could change these parameters interactively, but you couldn't make them much larger without burning a lot of computer cycles (thus irritating your colleagues). With this limited lookahead, I could usually beat the program quite easily.

A decade later, in the early 1980s, I rewrote my program in C. The C version lines.c was last edited on 4/02/87, with a comment suggesting I first wrote it in 1984. It ran under the Mark Williams COHERENT operating system and under MS-DOS, optionally using special characters from the IBM PC character set to draw a fairly decent looking board; the COHERENT manual page for lines is here. The program is in K&R C, predating the ANSI/ISO C Standard, so it uses old-style function declarations (no prototypes). But it still compiles successfully under current gcc and runs. A quarter century later, all the register declarations amuse me; they helped C compilers of that era produce much more efficient code.

An old MS-DOS executable lines.exe from 6/18/92 still runs on a Windows PC as of 1/10. (Invoke it from a command line shell, then type h for help.) The depth and width parameters are 3 and 25 by default, but computers are so much faster now you can painlessly increase them; at depth 5 and width 50, a 2.6 GHz Windows PC typically makes a move in four or five seconds, and it almost always beats me.

dwp

This page is in memory of David Poole and many great 3am meals we shared in Chinatown after sailing.

loa.sai SAIL source 10/12/72
lines.c C source 4/02/87
lines.exe MS-DOS executable 6/18/92
lines_osx OSX executable 6/13/12