Black to play and win
If you are unfamiliar with this elegant game, here are the simple rules.
Mona and YL are two computer programs that play Lines of Action (LoA). They were developed at the University of Alberta by Darse Billings and Yngvi Bjornsson, two members of the U of A GAMES group.
Aaron Davidson has written a Java web applet that will allow you to play against YL or Mona. Try it out, and let us know what you think!
The updated list of regular ratings, as of July 2004, gives the following LoA rankings for e-mail games played in Dave Dyer's Annual LoA Tournament, from 1999 to 2004, and e-mail games played on Richard's PBeM server, from 1999 to 2002 (the PBeM games from 2003-04 are not easily available, and are not included).
The 2003 and 2004 tournaments were won by Marc Decroos of Belgium, moving him into the top four human players by rating. Two new players, "slowdean" and "kevin", also had impressive results. (If you know the full name and country of these individuals, please contact me).
Rank Nickname Games W L D WFreq ARtg Name (Country) 1 mona 23 23 0 0 1.000 2718 Mona (Darse Billings, Canada) 2 mia 6 5 1 0 0.833 2371 MIA (Mark Winands, Netherlands) 3 jarrausi 28 24 4 0 0.857 2326 Jorge Gómez Arrausi (Spain) 4 chaunier 76 66 10 0 0.868 2194 Claude Chaunier (France) 5 mdecroos 34 27 7 0 0.794 2152 Marc Decroos (Belgium) 6 kerryh 13 11 2 0 0.846 2151 Kerry Handscomb (England/Canada) 7 slowdean 11 8 3 0 0.727 2090 8 kevin 22 15 7 0 0.682 2082 9 hthordsen 49 33 16 0 0.673 2057 Hartmut Thordsen (Germany) 10 uli 60 49 10 1 0.825 2054 Uli Vogel (Germany) 12 ragnar 56 39 17 0 0.696 2019 Ragnar Wikman (Finland) 13 koichin 23 17 6 0 0.739 1981 Koichi Nicholas (England) 14 ddyer 54 38 16 0 0.704 1962 Dave Dyer (USA) 15 pduff 14 8 6 0 0.571 1948 Patrick Duff (USA) 16 sharkey 39 29 10 0 0.744 1946 John Williams (USA) 17 johnbosley 23 16 7 0 0.696 1934 John Bosley (New Zealand) 18 sclark 16 12 4 0 0.750 1890 21 fredkok 61 38 23 0 0.623 1833 Fred Kok (Netherlands) 22 andidi 40 26 14 0 0.650 1824 Antonio Diago Andidi (Spain) 23 bernhard 17 14 3 0 0.824 1814 Bernhard Herwig (Germany) 24 pedro 122 80 42 0 0.656 1799 Pietro Rossi (Italy) 25 elloco 77 39 38 0 0.506 1792 Ronald Lokers 26 marconte 49 29 20 0 0.592 1772 Marco Conte (Italy) 29 bharat 50 21 29 0 0.420 1730 30 treesong 6 3 3 0 0.500 1721 Philip Cohen (USA) 31 kurtvdb 24 14 10 0 0.583 1720 Kurt Van den Branden (Belgium)
Please note that the ratings are precise, but not necessarily accurate, since they are based on a small number of outcomes. The rating system accounts for the statistical significance of each player's record. The rating program and the LoA results database that it uses are available.
You can also view the list of historical ratings for games from 1996-2004.
Mona won the Fifth Annual E-mail Tournament with a perfect 14-0 record, including wins over most of the top players in the world.
Jorge Gómez Arrausi defended his title as the human champion, winning all of his other games.
A special prize was awarded for the best played game against Mona. John Bosley defended tenaciously, producing a marvelously complex position, and lasted longer than any other human opponent (with White no less!). Jorge Gómez Arrausi found a brilliant plan to give himself a dynamic position with lots of chances, and then defended almost perfectly, taxing Mona to the limit. Both of these gentleman have been awarded some souvenirs from Alberta.
The tournament began in September 2000, and finished in May 2001. Several of Mona's games can be viewed with Dave Dyer's LOAviewer. His applet can also be used to play through all of the games from the first round and the final.
Player | score | ||||||||||
Mo | JG | RW | JB | HT | PD | PR | DP | ||||
Mona | x | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 7 - 0 | ||
Jorge Gómez Arrausi | 0 | x | 1 | 1 | 1 | 1 | 1 | 1 | 6 - 1 | ||
Ragnar Wikman | 0 | 0 | x | 0 | 1 | 1 | 1 | 1 | 4 - 3 | ||
John Bosley | 0 | 0 | 1 | x | 1 | 0 | 1 | 0 | 3 - 4 | ||
Hartmut Thordsen | 0 | 0 | 0 | 0 | x | 1 | 1 | 1 | 3 - 4 | ||
Patrick Duff | 0 | 0 | 0 | 1 | 0 | x | 1 | 1 | 3 - 4 | ||
Pietro Rossi | 0 | 0 | 0 | 0 | 0 | 0 | x | 1 | 1 - 6 | ||
David Priddy | 0 | 0 | 0 | 1 | 0 | 0 | 0 | x | 1 - 6 |
vs Jorge Gómez Arrausi (Spain) vs Ragnar Wikman (Finland) vs John Bosley (New Zealand)
vs Hartmut Thordsen (Germany) vs Patrick Duff (USA) vs Pietro Rossi (Italy) vs David Priddy (USA)
The Fifth Computer Olympiad was held in August 2000, in London, in conjunction with the Mind Sports Olympiad.
YL, written by Yngvi Bjornsson, took the top spot in Lines of Action, as expected. Hooray for Iceland!
Mona, written by Darse Billings, came close to sharing the gold, but lost a heartbreaker to YL on time, just seconds before announcing a win.
MIA, written by Mark Winands, took the bronze and acquitted itself well, winning one game against each of the U of A programs.
No other programs were entered, perhaps due to the expense of travelling to London, but we did not know of any other contenders at that time.
Here we are after the medal ceremony (left to right: Mark, Yngvi, and Darse). Yngvi checked to see if it was real gold, but alas, no such luck.
An extensive move-by-move analysis is now available for each game, along with an introduction covering some of the highlights of each match. This could provide good study material for the serious student of the game. The gamescores file contains some background information on the computer olympiad, and explains how to interpret the program's output.
YL vs MIA: Game 1 Game 2 Game 3 Game 4
Mona vs MIA: Game 7 Game 8 Game 9 Game 10
YL vs Mona: Game 5 Game 6 Game 11 Game 12
The Fourth Mind Sports Olympiad featured the annual over-the-board Lines of Action championship. Fred Kok (gold medalist in 1997, 1999 and 2002) is pictured at the top right (burgundy shirt), and Koichi Nicholas (2001 gold medalist and 2000 silver medalist) is on his left. More photos of the Computer Olympiad, and the human Lines of Action tournament are also available, courtesy of the Mind Sports website.
The Sixth Computer Olympiad was held in August 2001, in Maastrict, The Netherlands.
YL, by Yngvi Bjornsson, successfully defended it's title, but needed to win a playoff match against a much improved MIA II, by Mark Winands. Apprentice, by Don Beal, is a new entry to the computer Lines of Action competition this year. Mona did not compete (Darse is focusing on his Ph.D. research, which does not involve LoA).
YL vs MIA: Game 1 Game 2 Game 3 Game 4
The Seventh Computer Olympiad was held in July 2002, again in Maastrict, The Netherlands.
YL made it three championships in a row, winning the gold medal yet again. Yngvi improved his program considerably before the competition, and it was probably necessary against the once again improved MIA III, by Mark Winands. T-T, by Hiroyuki Iida earned the bronze. More details are available at the 7th Computer Olympiad website.
The original Mona-2000 was hoping to play this year, but Darse had to withdraw due to other commitments. A friendly exhibition match was played with MIA III during the Computers and Games conference (CG'02), held later in July. The same Mona that competed in London was able to hold her own against the vastly improved MIA, with each program winning two games, at two minutes per move. At faster time controls, Mona benefits quite a bit from faster machines and newer technology, reaching the critical 9-ply search depth more often.
This is where it all began for Mona and YL. Students in Jonathan Schaeffer's graduate course on heuristic search each wrote a computer program for Lines of Action, and an open tournament was held in April 2000. Here are the complete results of that tournament.
Shortly after writing our programs, we were fortunate to have the opportunity to test them against one of the best Lines of Action players in the world, Kerry Handscomb.
Kerry tied for first place in the 1999 e-mail LoA tournament. This is an annual event which features most of the world's best LoA players, including several medalists from the Mind Sports Olympiads. Full details are available on Dave Dyer's LOA website.
These games were very valuable in the development of both programs, and we are eternally grateful to Kerry for his contributions.
Mona has played on Richard's PBeM (play by e-mail) server, against some of the best players in the world.
She also participated in the Fifth Annual LOA E-mail Tournament, which includes most of the elite players.
Mona has had a lot of success so far, winning every game, and the program appears to be stronger than any human player. Humans can still improve though, so perhaps a future Lines of Action grandmaster will overtake the silicon beast.
vs Claude Chaunier (France) vs Dave Dyer (USA) vs Uli Vogel (Germany) vs Pietro Rossi (Italy)
vs Antonio Andidi (Spain) vs Yu Leong Wong (Hong Kong) vs Fred Kok (Netherlands)
At fast time controls, YL is stronger than Mona because of its deeper search. A 622 game match (all two-move openings, played from both sides) was played with a moderate time control of three minutes per move. Although we both expected an easy win for YL, it turned out to be a lot closer than we thought.
After two months of continuous play, YL won the match with 319 wins, 263 losses, and 40 draws (+56 games, 54.5% overall win rate).
The series with the starting move 1. d1-b3 was by far the most important, because there was beer riding on the outcome! :) Mona won that 66-game mini-match by 5 games (+34 -29 =3, 54%).
This match featured deeper searches than are normally reached in over-the-board play. YL analyzed about ten times as many positions per move, in about half as much time (YL is about 20 times faster than Mona). YL typically needed about 20 minutes to reach 13-ply early in the game, dropping to just a few minutes near the end. All four games were played with the first move of d1-b3, in order to explore strategic blockading positions, and test new code.
Somewhat surprisingly, Mona won all four games, despite the shallower search. Mona's slower evaluation function appears to pay dividends after the benefits of deeper search reach the point of diminishing returns.
An 8-game match was played with a leisurely time control of one hour per move. Playing with a fixed time per move favours YL, because it iterates one ply at a time rather than two, utilizing more of the available time on average. This difference appeared to be particularly bad in the opening, resulting in some inferior 9-ply moves by Mona. The match ended in a draw, with four wins each.
Another 8-game match was played in April 2001, with a long time control of eight hours per move (essentially "correspondence games", like those in the e-mail tournament). The time advantage for YL was less important here because Mona always finished at least 11-ply (and usually 13-ply). Most of these games were tough struggles -- perhaps the highest level games of LoA ever played. Mona won the match convincingly, with seven wins and one loss.
As expected, YL obtained better results with sharper openings, such as 1. b1-b3 h2-f2, while Mona did better in blockading positions, like 1. d1-b3. Thus the struggle to obtain each program's preferred style of position is critical, and future games may be decided by their respective opening books.
All of these matches were between older (May 2000) versions of Mona and YL. The results do not necessarily indicate the relative strength of the current programs. The outcome of future contests are still very much in doubt!
The position in the diagram at the top of the page occured in a training match between Mona and YL. After YL narrowly missed a win earlier in the game, Mona found a long forcing line, leading to a mate in 11 moves (21-ply) in the given position.
The solution is presented move by move, so that you can treat it as a series of progressively easier problems, until you're able to find the mate. Only the toughest line of defence is given, so you'll have to work out the details for yourself.
You are visitor
to this page since June 2000. Last updated: November 2002.