Lines of Action Information

Edited by Mark Winands

Introduction

Lines of Action (LOA) is played on an 8x8 board by two sides, Black and White. Each side has twelve pieces at its disposal. It is a two-person zero-sum game with perfect information. LOA is a connection game, albeit non-typical. Claude Soucie invented it around 1960. Sid Sackson (1969) described it in his first edition of A Gamut of Games.

Rules

At the sixth Computer Olympiad the LOA rules were made immutable for this tournament. They are as stated below in point 1 to 10.

Warning: in some books, magazines or websites rules 2, 8, 9, and 10 can be different from what is specified here! The Olympiad organisation is using the rules, which were used at the MSO World Championship of 2000.

  1. The black pieces are placed in two rows along the top and bottom of the board, while the white pieces are placed in two files at the left and right side of the board. (see Diagram 1).

    Diagram 1: Board set-up.

    Diagram 2: A terminal position.

  2. The players alternately move, starting with Black.

  3. A player to move must move one of its pieces. A move takes place in a straight line (along files, ranks, or diagonals), exactly as many squares as there are pieces of either colour anywhere along the line of movement.

  4. A player may jump over its own pieces, but not land on them.

  5. A player may not jump over the opponent's pieces, but can capture them by landing on them.

  6. The goal of a player is to form one connected group with all of its pieces. The first player to do so is the winner. Connected pieces are on squares that are adjacent, either orthogonally or diagonally. (see Diagram 2).

  7. A single piece is a connected group.

  8. If a move simultaneously creates a single connected unit for both players, it is a draw.

  9. If a player cannot move, this player has to pass.

  10. If a position with the same player to move occurs for the third time, the game is drawn.

In the second edition of A Gamut of Games (1982) simultaneous connection (rule 8) is described as a win for the moving player, but the draw variant is still in force in the main tournaments, such as the Mind Sports Olympiad 2000, and on Richard's PBeM server (e-mail championship). It is recommended that both rules are implemented, because both are widely used.

Events

Past Computer LOA Tournaments

  • 11th Computer Olympiad: A computer LOA tournament was played at this event (Turin, Italy, May 24th-June 1st 2006).
  • 9th Computer Olympiad: A computer LOA tournament was played at this event (Bar-Ilan University, Ramat-Gan, Israel, July 4th-8th 2004).
  • 8th Computer Olympiad: A computer LOA tournament was played at this event (November 23-27, 2003, Graz, Austria).
  • 7th Computer Olympiad: The computer LOA tournament was played at this event (July 5-11, 2002, Maastricht, The Netherlands).
  • 6th CMG Computer Olympiad: The computer LOA tournament was played at this event (August 18-23, 2001, Maastricht, The Netherlands).
  • 5th Computer Olympiad: The computer LOA tournament was played at this event (August 21-25, 2000, London, UK).

Future Computer LOA Tournaments

Services and Sources of Information

Game-playing Servers

Newsgroups

Key People and Programs

Tournament Programs

  • Don Beal is a veteran computer-game programmer. At the sixth Computer Olympiad his program Apprentice won the bronze medal.

  • Darse Billings wrote in 2000 the well-known program Mona. It won the Fifth Annual E-mail Tournament with a perfect 14-0 record, including wins over most of the top players in the world. At the 5th Computer Olympiad it won the silver medal. It has not competed lately in tournaments. Darse has done many post-mortem analysis of games Mona and YL have played against great human LOA players and computer programs. At his site you play against his program.

  • Yngvi Björnsson is the author of the very strong program YL. It won three times the gold medal (2000, 2001,and 2002), one silver medal in 2006, and one bronze medal in 2004 . Yngvi has successfully applied the multi-cut idea in his program. Results can be found in his Ph.D. thesis: Selective Depth-First Game-Tree Search. At his site you play against his program.

  • Rémi Coulom's program Lola participated at the 9th Computer Olympiad.

  • Bernard Helmstetter's program Bing won convincingly the silver medal at the 8th and 9th Computer Olympiad. It is using neural networks in the evaluation function. Bing is based on Gnu Chess.

  • Jun Nagashima has written the program (T-T), pronounced Uruuru, at Hiroyuki Iida's games laboratory. It won the bronze medal at the 7th and 8th Computer Olympiad. The program uses realization-probability search.

  • Inge Wallin has competed with his program Pete at the last Computer Olympiad. One of his other interest is Computer Go (he is co-author of GnuGo).

  • Mark Winands wrote a LOA program for his M.Sc. thesis. The program, called MIA, is the current Computer Olympiad Champion. It won one bronze (2000), two silver (2001 and 2002) and three gold medals (2003, 2004, 2006) at the Computer Olympiad. The program uses proof-number search in the endgame. At his website you can find the rules, discussion, his M.Sc. thesis, LOA endgame positions, a downloadable version of MIA, and a Java Applet (MIA) playing LOA. More information can be found in his Ph.D. thesis: Informed Search in Complex Games.

Other programs

  • Alcon, Rosnagle and Kenny's LOA page Some insight is given in implementing a LOA program.

  • Benjamin Guihaire wrote the program LOA3D. This program has a nice user interface.

  • Christian Weninger and Thoms Törring's LOA page At this webpage you can download their LOA program. They have written programs for Windows, Linux/Unix and the Agenda PDA.

  • LoAdstone Claude Chaunier wrote the LOA program LoAdstone. At this webpage you can download his LOA program.

  • Dave Dyer's LOA page Dave is an authority in the field. He has created what most people see as the ultimate LOA site. Much information about LOA (rules, history, variants, programs, programming topics, LOA puzzles, tournaments). You can also play against Dyer's program, Loaw.

  • Unite  Shareware LOA program for the Mac written by Kevin Gong.

References

Journals and Magazines

...not exclusively focused on this game.

Books and Papers

  • Billings, D. and Björnsson, Y. (2003). Search and Knowledge in Lines of Action. Advances in Computer Games 10.  (eds. H.J. van den Herik, H. Iida and E. Heinz), pp. 231-248. Kluwer Academic Publishers/Boston.

  • Björnsson, Y. (2000). YL wins Lines of Action Tournament, ICGA Journal, Vol. 23, No. 3, pp.178-179.

  • Björnsson, Y. and Winands, M. (2001). YL wins Lines of Action Tournament, ICGA Journal, Vol. 24, No 3, pp.180-181.

  • Björnsson, Y. and Winands, M. (2002). YL wins Lines of Action Tournament, ICGA Journal, Vol. 25, No 3, pp. 185-186.

  • Björnsson, Y. (2002). Selective Depth-First Game-Tree Search, Ph.D. thesis. University of Alberta.

  • Chaunier, C. and Handscomb, K. (2001). Lines of Action Strategic Ideas - Part 4. Abstract Games, Vol. 2, No. 1, pp. 12-14.

  • Handscomb, K. (2000a). Lines of Action Strategic Ideas - Part 1. Abstract Games, Vol. 1, No. 1, pp. 9-11.

  • Handscomb, K. (2000b). Lines of Action Strategic Ideas - Part 2. Abstract Games, Vol. 1, No. 2, pp. 18-19.

  • Handscomb, K. (2000c). Lines of Action Strategic Ideas - Part 3. Abstract Games, Vol. 1, No. 3, pp. 18-19.

  • Helmstetter, B. and Cazenave, T. (2006). Architecture d'un Programme de Lines of Action. Intelligence Artificielle et Jeux (ed. T. Cazenave), pp. 117-126. Hermes Science. In French.

  • Sackson, S. (1969). A Gamut of Games. Random House, New York, NY, USA. A second edition (1982) has been republished in 1992 by Dover Publications, New York, NY, USA. ISBN 0-486-27347-4.

  • Sakuta, M., Hashimoto, T., Nagashima, J., Uiterwijk, J.W.H.M, and Iida, H. (2003). Application of the Killer-Tree Heuristic and the Lambda-Search Method to Lines of Action. Information Sciences. Vol. 154, No. 3-4, 141-155.

  • Winands, M.H.M. (2000). Analysis and Implementation of Lines of Action. M.Sc. thesis. Universiteit Maastricht, Maastricht, The Netherlands.

  • Winands, M.H.M, Uiterwijk, J.W.H.M., and Herik, H.J. van den (2001). The Quad Heuristic in Lines of Action. ICGA Journal, Vol. 24, No. 1, pp 3-15.

  • Winands, M.H.M, Kocsis, L., Uiterwijk, J.W.H.M., and Herik, H.J. van den (2002). Temporal Difference Learning and the Neural MoveMap Heuristic in the Game of Lines of Action. GAME-ON 2002 3rd International Conference on Intelligent Games and Simulation (eds. Quasim Mehdi, Norman Gough and Marc Cavazza), pp. 99-103. SCS Europe Bvba. ISBN 90-77039-10-4.

  • Winands, M.H.M, Uiterwijk, J.W.H.M., and Herik, H.J. van den (2002). PDS-PN: A New Proof-Number Search Algorithm: Application to Lines of Action. Computers and Games (CG 2002), Lecture Notes in Computer Science (LNCS 2883) (eds. J. Schaeffer, M. Müller and Y. Björnsson), pp. 61-74. Springer-Verlag Berlin Heidelberg 2003.

  • Winands, M.H.M.,  Herik, H.J. van den, and Uiterwijk, J.W.H.M. (2003). An Evaluation Function for Lines of Action. Advances in Computer Games 10.  (eds. H.J. van den Herik, H. Iida and E. Heinz), pp. 249-260. Kluwer Academic Publishers/Boston.

  • Winands, M.H.M. (2004). Informed Search in Complex Games. Ph.D. thesis. Universiteit Maastricht, Maastricht, The Netherlands. ISBN 90-5278-429-9.

  • Winands, M.H.M. and Björnsson, Y. (2008). Enhanced Realization Probability Search. New Mathematics and Natural Computation,  Vol. 4, No. 3, pp. 329-342.

  • Winands, M.H.M., Björnsson, Y., and Saito, J-T. (2008). Monte-Carlo Tree Search Solver. Computers and Games (CG 2008), Lecture Notes in Computer Science (LNCS 5131), pp. 25-36. Springer, Berlin Heidelberg.

Websites

  • Dave Dyer's LOA page The ultimate LOA site. Much information about LOA (rules, history, variants, programs, programming topics, LOA puzzles, tournaments).

  • Hartmut Thordsen's pages  Hartmut is one the better LOA players. This side describes not only the rules, he reviews also some LOA programs. You can download LoaTool, which converts PBMserv mails and Loaw V1.0 / LOA V3.4 game files to Loaviewer. In German.
--> Please report broken links, or suggestions for LOA-related links to: