25,161
edits
Changes
Created page with "'''Home * Games * Lines of Action''' FILE:Lines of Action.svg|border|right|thumb|Starting position, Black to move <ref>The starting position of a game of..."
'''[[Main Page|Home]] * [[Games]] * Lines of Action'''
[[FILE:Lines of Action.svg|border|right|thumb|Starting position, Black to move <ref>The starting position of a game of Lines of Action, by [https://en.wikipedia.org/wiki/User:Elembis Elembis], [https://en.wikipedia.org/wiki/Lines_of_Action Lines of Action from Wikipedia]</ref> ]]
'''Lines of Action''', (LoA)<br/>
a [https://en.wikipedia.org/wiki/Two-player_game two-player] [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] and [https://en.wikipedia.org/wiki/Perfect_information perfect information] [https://en.wikipedia.org/wiki/Abstract_strategy abstract strategy] [https://en.wikipedia.org/wiki/Board_game board game], a [https://en.wikipedia.org/wiki/Connection_game connection game] played on a standard [[Chessboard|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|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 [http://fr.wikipedia.org/wiki/Claude_Soucie Claude Soucie] around 1960, <ref>[http://ilk.uvt.nl/icga/games/Loa/ ICGA: Lines of Action] by [[Mark Winands]], [[ICGA]]</ref> , described 1969 by [https://en.wikipedia.org/wiki/Sid_Sackson Sid Sackson] in [https://en.wikipedia.org/wiki/A_Gamut_of_Games A Gamut of Games], and published in 1988 by [http://de.wikipedia.org/wiki/Hexagames Hexagames]. Since 1997, human players annually compete at the [https://en.wikipedia.org/wiki/Lines_of_Action#Champions world championship] as part of the [https://en.wikipedia.org/wiki/Mind_Sports_Olympiad Mind Sports Olympiad], Lines of Action programs regularly at the [[Computer Olympiad]], organized by the [[ICGA]].
=Complexity=
In his thesis, [[Mark Winands]] lists a [https://en.wikipedia.org/wiki/Game_complexity#State-space_complexity state-space complexity] of about 1.3 x 10<span style="font-size: 70%; vertical-align: super;">24</span> positions, an [[Branching Factor|average branching factor]] of 30, and a [https://en.wikipedia.org/wiki/Game_complexity#Game-tree_complexity game-tree complexity] of 10<span style="font-size: 70%; vertical-align: super;">56</span> positions <ref>[[Mark Winands]] ('''2000'''). ''Analysis and Implementation of Lines of Action''. M.Sc. thesis. [[Maastricht University|Universiteit Maastricht]], [http://ilk.uvt.nl/icga/games/Loa/documents/Analysis%20and%20Implementation.pdf pdf]</ref>.
=[[Computer Olympiad|Computer Olympiads]]=
* [[5th Computer Olympiad#LOA|5th Computer Olympiad, London 2000]]
* [[6th Computer Olympiad#LOA|6th Computer Olympiad, Maastricht 2001]]
* [[7th Computer Olympiad#LOA|7th Computer Olympiad, Maastricht 2002]]
* [[8th Computer Olympiad#LOA|8th Computer Olympiad, Graz 2003]]
* [[9th Computer Olympiad#LOA|9th Computer Olympiad, Ramat Gan 2004]]
* [[11th Computer Olympiad#LOA|11th Computer Olympiad, Turin 2006]]
* [[14th Computer Olympiad#LOA|14th Computer Olympiad, Pamplona 2009]]
* [[17th Computer Olympiad#LOA|17th Computer Olympiad, Yokohama 2013]]
* [[18th Computer Olympiad#LOA|18th Computer Olympiad, Leiden 2015]]
* [[20th Computer Olympiad#LOA|20th Computer Olympiad, Leiden 2017]]
=Photos=
[[FILE:olympiad2000loa.jpg|none|border|text-bottom|640px|link=http://spaz.ca/aaron/gallery/england2000/games.html]]
[[5th Computer Olympiad#LOA|London 2000]], first medals in LoA: [[Mark Winands]] (B), [[Yngvi Björnsson]] (G), [[Darse Billings]] (S) <ref>[http://spaz.ca/aaron/gallery/england2000/games.html Mind Sports Olympiad, England, August 2000] by [[Aaron Davidson]]</ref>
[[FILE:LOAGraz2003.jpg|none|border|text-bottom|640px|link=http://www.yss-aya.com/photo/graz2003/1125/Htmls/PICT1202.html]]
LOA winners of the [[8th Computer Olympiad#LOA|8th Computer Olympiad]]: [[Bernard Helmstetter]], [[Mark Winands]] and [[Jun Nagashima]] <ref>[http://www.yss-aya.com/photo/graz2003/1125/index01.html Computer Olympiad 2003 in Graz, Austria, November 25] by [[Hiroshi Yamashita]]</ref>
=Selected Publications=
==2000 ...==
* [[Mark Winands]] ('''2000'''). ''Analysis and Implementation of Lines of Action''. M.Sc. thesis. [[Maastricht University|Universiteit Maastricht]], [http://ilk.uvt.nl/icga/games/Loa/documents/Analysis%20and%20Implementation.pdf pdf]
* [[Mark Winands]], [[Jos Uiterwijk]] ('''2000'''). ''Analysis and Implementation of Lines of Action''. [[5th Computer Olympiad#Workshop|5th Computer Olympiad Workshop]], [https://dke.maastrichtuniversity.nl/m.winands/documents/workshop_2000.pdf pdf]
* [[Yngvi Björnsson]] ('''2000'''). ''YL wins Lines of Action Tournament.'' [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]] » [[5th Computer Olympiad#LOA|5th Computer Olympiad]]
* [[Mark Winands]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2001'''). ''The Quad heuristic in Lines of Action'', [[ICGA Journal#24_1|ICGA Journal, Vol. 24, No. 1]], [http://www.personeel.unimaas.nl/m-winands/documents/The_Quad_Heuristic_in_Lines_of_Action.pdf pdf]
'''2001'''
* [[Yngvi Björnsson]], [[Mark Winands]] ('''2001'''). ''YL wins Lines of Action tournament''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]] » [[6th Computer Olympiad#LOA|6th Computer Olympiad]]
* [[Mark Winands]], [[Jos Uiterwijk]] ('''2001'''). ''PN, PN2 and PN* in Lines of Action''. [[6th Computer Olympiad#Workshop|6th Computer Olympiad Workshop]], [https://dke.maastrichtuniversity.nl/m.winands/documents/PN_PN2_AND_PNstar_%20IN_LOA.pdf pdf] » [[Proof-Number Search]]
'''2002'''
* [[Yngvi Björnsson]], [[Mark Winands]] ('''2002'''). ''YL wins Lines of Action tournament''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]] » [[7th Computer Olympiad#LOA|7th Computer Olympiad]]
* [[Mark Winands]], [[Levente Kocsis]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2002'''). ''Learning in Lines of Action''. [[7th Computer Olympiad#Workshop|7th Computer Olympiad Workshop]] <ref>[https://dke.maastrichtuniversity.nl/m.winands/publications.html Publications - Maastricht University]</ref>
* [[Jun Nagashima]] ('''2002'''). ''Realization-Probability Search: Its application to Shogi and LOA''. [[7th Computer Olympiad#Workshop|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, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.9038&rep=rep1&type=pdf 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#26_4|ICGA Journal, Vol. 26, No. 4]] » [[8th Computer Olympiad#LOA|8th Computer Olympiad]]
* [[Darse Billings]], [[Yngvi Björnsson]] ('''2003'''). ''Search and Knowledge in Lines of Action''. [[Advances in Computer Games 10]], [http://webdocs.cs.ualberta.ca/~darse/Papers/skloa-sub.pdf pdf]
'''2004'''
* [[Mark Winands]] ('''2004'''). ''MIA 4++ wins Lines of Action tournament''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]] » [[9th Computer Olympiad#LOA|9th Computer Olympiad]]
==2005 ...==
* [[Mark Winands]] ('''2006'''). ''MIA 4.5 wins Lines of Action tournament''. [[ICGA Journal#29_3|ICGA Journal, Vol. 29, No. 3]] » [[11th Computer Olympiad#LOA|11th Computer Olympiad]]
* [[Mark Winands]] ('''2009'''). ''MIA wins Lines of Action tournament''. [[ICGA Journal#32_2|ICGA Journal, Vol. 32, No. 2]] » [[14th Computer Olympiad#LOA|14th Computer Olympiad]]
==2010 ...==
* [[Mark Winands]], [[Yngvi Björnsson]], [[Jahn-Takeshi Saito]] ('''2010'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5523941 Monte Carlo Tree Search in Lines of Action]''.[[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4
* [[Marc Lanctot]] ('''2013'''). ''LOA Wins Lines of Action Tournament''. [[ICGA Journal#36_4|ICGA Journal, Vol. 36, No. 4]] » [[17th Computer Olympiad#LOA|17th Computer Olympiad]]
=External Links=
* [https://en.wikipedia.org/wiki/Lines_of_Action Lines of Action from Wikipedia]
* [http://www.iggamecenter.com/info/en/loa.html igGameCenter :: Lines of Action]
* [https://www.game-ai-forum.org/icga-tournaments/game.php?id=6 Lines of Action (ICGA Tournaments)]
* [http://ilk.uvt.nl/icga/games/Loa/ ICGA: Lines of Action] by [[Mark Winands]], [[ICGA]]
* [http://www.personeel.unimaas.nl/m-winands/loa/ Mark's LOA Homepage] by [[Mark Winands]], [[Maastricht University]]
* [https://webdocs.cs.ualberta.ca/~darse/LOA/ Mona and YL's Lines of Action Page] by [[Darse Billings]] and [[Yngvi Björnsson]], [[University of Alberta]]
* [http://www.gillion.de/loa/ Lines Of Action] by Christian Weninger and [http://users.physik.fu-berlin.de/~jtt/ Jens Thoms Törring], [[Free University of Berlin]]
=References=
<references />
'''[[Games|Up one Level]]'''
[[FILE:Lines of Action.svg|border|right|thumb|Starting position, Black to move <ref>The starting position of a game of Lines of Action, by [https://en.wikipedia.org/wiki/User:Elembis Elembis], [https://en.wikipedia.org/wiki/Lines_of_Action Lines of Action from Wikipedia]</ref> ]]
'''Lines of Action''', (LoA)<br/>
a [https://en.wikipedia.org/wiki/Two-player_game two-player] [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] and [https://en.wikipedia.org/wiki/Perfect_information perfect information] [https://en.wikipedia.org/wiki/Abstract_strategy abstract strategy] [https://en.wikipedia.org/wiki/Board_game board game], a [https://en.wikipedia.org/wiki/Connection_game connection game] played on a standard [[Chessboard|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|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 [http://fr.wikipedia.org/wiki/Claude_Soucie Claude Soucie] around 1960, <ref>[http://ilk.uvt.nl/icga/games/Loa/ ICGA: Lines of Action] by [[Mark Winands]], [[ICGA]]</ref> , described 1969 by [https://en.wikipedia.org/wiki/Sid_Sackson Sid Sackson] in [https://en.wikipedia.org/wiki/A_Gamut_of_Games A Gamut of Games], and published in 1988 by [http://de.wikipedia.org/wiki/Hexagames Hexagames]. Since 1997, human players annually compete at the [https://en.wikipedia.org/wiki/Lines_of_Action#Champions world championship] as part of the [https://en.wikipedia.org/wiki/Mind_Sports_Olympiad Mind Sports Olympiad], Lines of Action programs regularly at the [[Computer Olympiad]], organized by the [[ICGA]].
=Complexity=
In his thesis, [[Mark Winands]] lists a [https://en.wikipedia.org/wiki/Game_complexity#State-space_complexity state-space complexity] of about 1.3 x 10<span style="font-size: 70%; vertical-align: super;">24</span> positions, an [[Branching Factor|average branching factor]] of 30, and a [https://en.wikipedia.org/wiki/Game_complexity#Game-tree_complexity game-tree complexity] of 10<span style="font-size: 70%; vertical-align: super;">56</span> positions <ref>[[Mark Winands]] ('''2000'''). ''Analysis and Implementation of Lines of Action''. M.Sc. thesis. [[Maastricht University|Universiteit Maastricht]], [http://ilk.uvt.nl/icga/games/Loa/documents/Analysis%20and%20Implementation.pdf pdf]</ref>.
=[[Computer Olympiad|Computer Olympiads]]=
* [[5th Computer Olympiad#LOA|5th Computer Olympiad, London 2000]]
* [[6th Computer Olympiad#LOA|6th Computer Olympiad, Maastricht 2001]]
* [[7th Computer Olympiad#LOA|7th Computer Olympiad, Maastricht 2002]]
* [[8th Computer Olympiad#LOA|8th Computer Olympiad, Graz 2003]]
* [[9th Computer Olympiad#LOA|9th Computer Olympiad, Ramat Gan 2004]]
* [[11th Computer Olympiad#LOA|11th Computer Olympiad, Turin 2006]]
* [[14th Computer Olympiad#LOA|14th Computer Olympiad, Pamplona 2009]]
* [[17th Computer Olympiad#LOA|17th Computer Olympiad, Yokohama 2013]]
* [[18th Computer Olympiad#LOA|18th Computer Olympiad, Leiden 2015]]
* [[20th Computer Olympiad#LOA|20th Computer Olympiad, Leiden 2017]]
=Photos=
[[FILE:olympiad2000loa.jpg|none|border|text-bottom|640px|link=http://spaz.ca/aaron/gallery/england2000/games.html]]
[[5th Computer Olympiad#LOA|London 2000]], first medals in LoA: [[Mark Winands]] (B), [[Yngvi Björnsson]] (G), [[Darse Billings]] (S) <ref>[http://spaz.ca/aaron/gallery/england2000/games.html Mind Sports Olympiad, England, August 2000] by [[Aaron Davidson]]</ref>
[[FILE:LOAGraz2003.jpg|none|border|text-bottom|640px|link=http://www.yss-aya.com/photo/graz2003/1125/Htmls/PICT1202.html]]
LOA winners of the [[8th Computer Olympiad#LOA|8th Computer Olympiad]]: [[Bernard Helmstetter]], [[Mark Winands]] and [[Jun Nagashima]] <ref>[http://www.yss-aya.com/photo/graz2003/1125/index01.html Computer Olympiad 2003 in Graz, Austria, November 25] by [[Hiroshi Yamashita]]</ref>
=Selected Publications=
==2000 ...==
* [[Mark Winands]] ('''2000'''). ''Analysis and Implementation of Lines of Action''. M.Sc. thesis. [[Maastricht University|Universiteit Maastricht]], [http://ilk.uvt.nl/icga/games/Loa/documents/Analysis%20and%20Implementation.pdf pdf]
* [[Mark Winands]], [[Jos Uiterwijk]] ('''2000'''). ''Analysis and Implementation of Lines of Action''. [[5th Computer Olympiad#Workshop|5th Computer Olympiad Workshop]], [https://dke.maastrichtuniversity.nl/m.winands/documents/workshop_2000.pdf pdf]
* [[Yngvi Björnsson]] ('''2000'''). ''YL wins Lines of Action Tournament.'' [[ICGA Journal#23_3|ICGA Journal, Vol. 23, No. 3]] » [[5th Computer Olympiad#LOA|5th Computer Olympiad]]
* [[Mark Winands]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2001'''). ''The Quad heuristic in Lines of Action'', [[ICGA Journal#24_1|ICGA Journal, Vol. 24, No. 1]], [http://www.personeel.unimaas.nl/m-winands/documents/The_Quad_Heuristic_in_Lines_of_Action.pdf pdf]
'''2001'''
* [[Yngvi Björnsson]], [[Mark Winands]] ('''2001'''). ''YL wins Lines of Action tournament''. [[ICGA Journal#24_3|ICGA Journal, Vol. 24, No. 3]] » [[6th Computer Olympiad#LOA|6th Computer Olympiad]]
* [[Mark Winands]], [[Jos Uiterwijk]] ('''2001'''). ''PN, PN2 and PN* in Lines of Action''. [[6th Computer Olympiad#Workshop|6th Computer Olympiad Workshop]], [https://dke.maastrichtuniversity.nl/m.winands/documents/PN_PN2_AND_PNstar_%20IN_LOA.pdf pdf] » [[Proof-Number Search]]
'''2002'''
* [[Yngvi Björnsson]], [[Mark Winands]] ('''2002'''). ''YL wins Lines of Action tournament''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]] » [[7th Computer Olympiad#LOA|7th Computer Olympiad]]
* [[Mark Winands]], [[Levente Kocsis]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2002'''). ''Learning in Lines of Action''. [[7th Computer Olympiad#Workshop|7th Computer Olympiad Workshop]] <ref>[https://dke.maastrichtuniversity.nl/m.winands/publications.html Publications - Maastricht University]</ref>
* [[Jun Nagashima]] ('''2002'''). ''Realization-Probability Search: Its application to Shogi and LOA''. [[7th Computer Olympiad#Workshop|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, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.9038&rep=rep1&type=pdf 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#26_4|ICGA Journal, Vol. 26, No. 4]] » [[8th Computer Olympiad#LOA|8th Computer Olympiad]]
* [[Darse Billings]], [[Yngvi Björnsson]] ('''2003'''). ''Search and Knowledge in Lines of Action''. [[Advances in Computer Games 10]], [http://webdocs.cs.ualberta.ca/~darse/Papers/skloa-sub.pdf pdf]
'''2004'''
* [[Mark Winands]] ('''2004'''). ''MIA 4++ wins Lines of Action tournament''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]] » [[9th Computer Olympiad#LOA|9th Computer Olympiad]]
==2005 ...==
* [[Mark Winands]] ('''2006'''). ''MIA 4.5 wins Lines of Action tournament''. [[ICGA Journal#29_3|ICGA Journal, Vol. 29, No. 3]] » [[11th Computer Olympiad#LOA|11th Computer Olympiad]]
* [[Mark Winands]] ('''2009'''). ''MIA wins Lines of Action tournament''. [[ICGA Journal#32_2|ICGA Journal, Vol. 32, No. 2]] » [[14th Computer Olympiad#LOA|14th Computer Olympiad]]
==2010 ...==
* [[Mark Winands]], [[Yngvi Björnsson]], [[Jahn-Takeshi Saito]] ('''2010'''). ''[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5523941 Monte Carlo Tree Search in Lines of Action]''.[[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4
* [[Marc Lanctot]] ('''2013'''). ''LOA Wins Lines of Action Tournament''. [[ICGA Journal#36_4|ICGA Journal, Vol. 36, No. 4]] » [[17th Computer Olympiad#LOA|17th Computer Olympiad]]
=External Links=
* [https://en.wikipedia.org/wiki/Lines_of_Action Lines of Action from Wikipedia]
* [http://www.iggamecenter.com/info/en/loa.html igGameCenter :: Lines of Action]
* [https://www.game-ai-forum.org/icga-tournaments/game.php?id=6 Lines of Action (ICGA Tournaments)]
* [http://ilk.uvt.nl/icga/games/Loa/ ICGA: Lines of Action] by [[Mark Winands]], [[ICGA]]
* [http://www.personeel.unimaas.nl/m-winands/loa/ Mark's LOA Homepage] by [[Mark Winands]], [[Maastricht University]]
* [https://webdocs.cs.ualberta.ca/~darse/LOA/ Mona and YL's Lines of Action Page] by [[Darse Billings]] and [[Yngvi Björnsson]], [[University of Alberta]]
* [http://www.gillion.de/loa/ Lines Of Action] by Christian Weninger and [http://users.physik.fu-berlin.de/~jtt/ Jens Thoms Törring], [[Free University of Berlin]]
=References=
<references />
'''[[Games|Up one Level]]'''
