Home * Games * Lines of Action

		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. Lines of Action was invented by Claude Soucie around 1960, ^[1] , 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. 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 ^[2].
Starting position, Black to move ^[3]

Computer Olympiads

Photos



London 2000, first medals in LoA: Mark Winands (B), Yngvi Björnsson (G), Darse Billings (S) ^[4]

LOA winners of the 8th Computer Olympiad: Bernard Helmstetter, Mark Winands and Jun Nagashima ^[5]

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

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 ^[6]
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

2004

Up one Level