Lines of Action

Home * Games * Lines of Action

Starting position, Black to move ¹

Lines of Action, (LoA)
a two-player zero-sum and perfect information abstract strategy board game, a connection game played on a standard chessboard, with two times six pieces or checkers per side, White and Black. The goal is to connect all of one's pieces into a single group. Checkers alternately (starting with Black) move horizontally, vertically, or diagonally like a queen in chess, but exactly as many spaces as there are own and opponent checkers on the line. Opponent checkers may be captured, but not own ones, checkers may jump over friendly but not over opponent ones.

A Gamut of Games

Lines of Action was invented by Claude Soucie around 1960, ¹ , described 1969 by Sid Sackson in A Gamut of Games, and published in 1988 by Hexagames. Since 1997, human players annually compete at the world championship as part of the Mind Sports Olympiad, Lines of Action programs regularly at the Computer Olympiad, organized by the ICGA.

Complexity

In his thesis, Mark Winands lists a state-space complexity of about 1.3 x 1024 positions, an average branching factor of 30, and a game-tree complexity of 1056 positions ².

Computer Olympiads

• 5th Computer Olympiad, London 2000
• 6th Computer Olympiad, Maastricht 2001
• 7th Computer Olympiad, Maastricht 2002
• 8th Computer Olympiad, Graz 2003
• 9th Computer Olympiad, Ramat Gan 2004
• 11th Computer Olympiad, Turin 2006
• 14th Computer Olympiad, Pamplona 2009
• 17th Computer Olympiad, Yokohama 2013
• 18th Computer Olympiad, Leiden 2015
• 20th Computer Olympiad, Leiden 2017

Photos

London 2000, first medals in LoA: Mark Winands (B), Yngvi Björnsson (G), Darse Billings (S) ³ LOA winners of the 8th Computer Olympiad: Bernard Helmstetter, Mark Winands and Jun Nagashima ⁴

Selected Publications

2000 ...

• Mark Winands (2000). Analysis and Implementation of Lines of Action. M.Sc. thesis. Universiteit Maastricht, pdf
• Mark Winands, Jos Uiterwijk (2000). Analysis and Implementation of Lines of Action. 5th Computer Olympiad Workshop, pdf
• Yngvi Björnsson (2000). YL wins Lines of Action Tournament. ICGA Journal, Vol. 23, No. 3 » 5th Computer Olympiad
• Mark Winands, Jos Uiterwijk, Jaap van den Herik (2001). The Quad heuristic in Lines of Action, ICGA Journal, Vol. 24, No. 1, pdf

2001

• Yngvi Björnsson, Mark Winands (2001). YL wins Lines of Action tournament. ICGA Journal, Vol. 24, No. 3 » 6th Computer Olympiad
• Mark Winands, Jos Uiterwijk (2001). PN, PN2 and PN* in Lines of Action. 6th Computer Olympiad Workshop, pdf » Proof-Number Search

2002

• Yngvi Björnsson, Mark Winands (2002). YL wins Lines of Action tournament. ICGA Journal, Vol. 25, No. 3 » 7th Computer Olympiad
• Mark Winands, Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2002). Learning in Lines of Action. 7th Computer Olympiad Workshop ⁵
• Jun Nagashima (2002). Realization-Probability Search: Its application to Shogi and LOA. 7th Computer Olympiad Workshop
• Mark Winands, Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2002). Temporal difference learning and the Neural MoveMap heuristic in the game of Lines of Action. GAME-ON 2002, pdf
• Mark Winands, Jos Uiterwijk, Jaap van den Herik (2002). PDS-PN: A new proofnumber search algorithm: Application to Lines of Action. CG 2002 » Proof-Number Search
• Makoto Sakuta, Tsuyoshi Hashimoto, Jun Nagashima, Hiroyuki Iida (2002). Endgame-search techniques developed in shogi: application to Lines of Action. JCIS 2002
• Makoto Sakuta, Tsuyoshi Hashimoto, Jun Nagashima, Jos Uiterwijk, Hiroyuki Iida (2002). Application of the killer-tree heuristic and the lambda-search method to lines of action.

2003

• Mark Winands (2003). MIA IV wins Lines of Action tournament. ICGA Journal, Vol. 26, No. 4 » 8th Computer Olympiad
• Darse Billings, Yngvi Björnsson (2003). Search and Knowledge in Lines of Action. Advances in Computer Games 10, pdf

2004

• Mark Winands (2004). MIA 4++ wins Lines of Action tournament. ICGA Journal, Vol. 27, No. 3 » 9th Computer Olympiad

2005 ...

• Mark Winands (2006). MIA 4.5 wins Lines of Action tournament. ICGA Journal, Vol. 29, No. 3 » 11th Computer Olympiad
• Mark Winands (2009). MIA wins Lines of Action tournament. ICGA Journal, Vol. 32, No. 2 » 14th Computer Olympiad

2010 ...

• Mark Winands, Yngvi Björnsson, Jahn-Takeshi Saito (2010). Monte Carlo Tree Search in Lines of Action.IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 4
• Marc Lanctot (2013). LOA Wins Lines of Action Tournament. ICGA Journal, Vol. 36, No. 4 » 17th Computer Olympiad

External Links

• Lines of Action from Wikipedia
• igGameCenter :: Lines of Action
• Lines of Action (ICGA Tournaments)
• ICGA: Lines of Action by Mark Winands, ICGA
• Mark's LOA Homepage by Mark Winands, Maastricht University
• Mona and YL's Lines of Action Page by Darse Billings and Yngvi Björnsson, University of Alberta

References