Warning: Use of undefined constant view - assumed 'view' (this will throw an Error in a future version of PHP) in /homepages/9/d106089208/htdocs/dinsights/POTM/ASSETS/contest_top.php on line 22
You may want to reduce the size of the text using your browser controls. The game length averages are individual player moves (max of 100 per game - 50 per player).
1. elopes scored 148   (74 wins, 0 losses, 0 draws)
In 74 wins, avg winning margin was 8.96 points and game length 15.76 moves. Overall avg game length 15.76 moves.

Doug Beardsley

Where? USA
What? Software Engineer
Who? I develop software for my job and during my free time. I also try to throw in sports and music when Im not working on the POTM or some other programming project.
The word "elopes", which in its most general form means "to run away", was chosen to convey the fact that my entry is intended to run away from the competition. This combined with the obvious homonymity with LOAPS. Add to that the fact that the letter e is a common prefix that generally has a computer connotation (the obvious example is the word "email"), and you get what I considered to be the perfect name.
Approach I used the alpha-beta search algorithm to look ahead as many moves as possible and choose the best one. Positions are evaluated according to an evaluation function that is based on a combination of several game features.

I also spent a large amount of time developing an opening book of moves to help elopes in the opening.

A more detailed description of the evaluation function can be found at:


And the search is described at:

Try Again? I would try a few more sophisticated ideas in the eval and maybe implement some type of learning algorithm (TD(lambda) comes to mind). I would also put as much effort as possible into more opening book knowledge.

2. Loaputa scored 140   (69 wins, 3 losses, 2 draws)
In 69 wins, avg winning margin was 12.81 points and game length 17.64 moves. Overall avg game length 20.05 moves.

Boris Levine

Where? UK
What? IT
Who? I wish I would have more time for POTMs...
it is a mixture of LOAPs and Laputa (Jonathan Swift)
Approach In general Loaputa uses classical Alpha-Beta search. The depth may vary from 6 half-steps to 9. The valuation function includes difference in scores plus distance between pieces. The distance is calculated as distance from all pieces that do not belong to the biggest group (of course minimum of possible distances). The program stores results of previous calculation (best path) in the temporary file between moves to use it on the next step as a hint. (This improves significantly pruning). First move is precalculated and put into small opening book (together with future hints). Lot of tricks was used to optimize memory and speed up calculation. Look in the code. It has no comments but if it will be required I can comment any part of it.
Try Again? More advanced distance calculation algorithm (I have one in mind)
Better opennings book, I have overlooked 500K limit...

3. thangngo scored 126   (63 wins, 11 losses, 0 draws)
In 63 wins, avg winning margin was 13.60 points and game length 17.76 moves. Overall avg game length 18.57 moves.

Trieu Nguyen

Where? Palo Alto, California .
What? I am a software engineer at nextag.com
Who? I was born in Vietnam, came to US a few year ago . I currently with my wife and 2 children.
In Vietnamese, it means dumb guy . Is it really dumb ? I dont know
Approach I use alpha-beta, expand aggressively at threat node .

4. SirChimpensteinThe2nd scored 124   (58 wins, 8 losses, 8 draws)
In 58 wins, avg winning margin was 10.93 points and game length 17.09 moves. Overall avg game length 21.81 moves.

Bryce Pasechnik

Vancouver, Canada
No job currently
SirChimpenstein1 didnt make the grade. Enter his successor....SirChimpenstein The 2nd.
Approach SirChimpenstein2 values three factors:
The actual score - the higher the better
The density of pieces - the higher the better
The closeness to the center - the higher the better

If the board is connected, its considered an infinite score for the winning player.

He uses a standard AlphaBeta search with transposition tables, move ordering, and a number of little optimizations to try and speed up the basic search as much as possible.

Poor SirChimpenstein2, however, couldnt quite figure out how to balance those primary valuation factors in relation to eachother.
Try Again? Try to improve the early game and board evaluator to better determine an optimal board condition.

5. 1111221 scored 122   (58 wins, 10 losses, 6 draws)
In 58 wins, avg winning margin was 10.07 points and game length 17.72 moves. Overall avg game length 21.84 moves.

Bill Wade

Where? Houston, TX USA
What? Software developer

Lack of imagination, and when I named it .11.11., the sandbox change . to _.
Opening book handles up to first six moves (has replies for all opponent attacks against my 100 weakest positions from the previous turn number).

After that, AlphaBeta PVS, with iterative deepening and hash table (typically looks ahead 5-7 plys in sandbox). Quiescent search for connection, all captures, and moves to d4. Best move is taken from hash table. No search for second best move (code is in place for history heuristic, but is turned off). I was never happy with MTDF, or null-move-heuristic results. Hash table is not saved from one turn to the next. In addition to the opening book, there is a table of known-wins that are loaded into the hash table. These actually came from "surprise" losses, and end up being treated as positions to be avoided.

Time allocated to the current turn is
Dont start the next deeper ply once 2% of my remaining time budget is gone.
No matter what, stop searching when 15% of my remaining time budget is gone.

Evaluation function is weighted sum of

Loaps Score.
Number of connected groups. (actually #groups-#holes)
Number of 2x2 grids with 3 or 4 pieces of the same color.
Mobility towards center of line.
Mobility with capture.
Variance in piece x and y (variance(x)=sum(x^2)-sum(x)^2/N)
Ring: Different scores for pieces at different distances from outer edge of board.

The weights were fixed, except for score which uses values
23/point (or so) when score difference is 0 to 11.
256/point for differences 12-20.
1/point when difference > 20.
this encourges the program to try hard for a 12+ point lead, and then switch to looking at connectivity if the lead gets above 20 (with a lead above 20 you will probably never lose, but you might tie).

Hash table uses a zobrist key (64-bit hash) based on xor of random values associated with each occupied square, and another value based on whose turn it is to move. Hash entries are stored in a bucket based on zobrist_key+loaps_score, where loaps_score is the current lead for the player to move. Hash table remembers deepest, and most-recent entries at each bucket. Entries for wins (or losses) are stored at the next (or previous) 16 positions also. If I have a winning move when up-by-3, it is also a winning move when up-by-7.

For every possible line of action, there is a precomputed table of moves for both players and the evaluation functions score for the mobility terms for this line. For instance, for the line (some diagonal) 11..21, player 1 has one move and player 2 has no moves. Player 1s move is also towards the center, and is a capture move.

For every possible move (say b2-d4) there is a precomputed table for the change in variance (not counting the division by N) and Ring portions of the evaluation. A similar table for each single square is used for captures, and to initialize the board.

For every possible 3x3 square, considering only one players pieces, there is a table showing the change in group count evaluation and the "dense 2x2" count evaluation caused by adding or removing the center of the 3x3. For instance,
Putting a 1 in the center reduces the group count and creates a new, dense 2x2 square,
Try Again? Automated testing to find better weights. I wasted a lot of test time using a large negative weight for having pieces at the outer edge of the board. That also corrupted my opening book.

Profiling to see where my program is spending time.
Investigate saving hash table from one turn to the next.

Id use a best-first search to generate my opening book. I ended up running 1 day of CPU for each ply of the opening book, but had no good way to "back-up" when I found out that some of my earlier entries were bad. With lots of CPU, Id change the opening book so that it only needed about 3-bytes per entry (currently I use 10 bytes per entry). However, I couldnt generate good entries quickly enough for the difference to matter.

6. lopsided scored 119   (58 wins, 13 losses, 3 draws)
In 58 wins, avg winning margin was 13.31 points and game length 18.93 moves. Overall avg game length 23.22 moves.

Hagen von Eitzen

Where? Bonn, Germany.
What? Sysadmin of a large law firm there. (So they′ll sue You if I do not get the trophy )
Who? I′m still mostly coping with the fact that has recently stumbled upon me, namely that of no longer being a thirty-something. Also, at almost the same instant I changed my job from last-line-of-defencea trouble-shooter of a not-so-healthy-any-more computer firm to system administrator of a large and well-known multilocated law firm.
These being quite massive changes in my life, I am quite happy that at least the POTM contest features as a fixed point in my life. Well, of course so do my home, my spouse, my family, ...

The task was for all of us to do some LOAPS.
So this is the LOAPS I did, almost pronounced lopsided.
It might also sometimes describe its way of playing, but that would be by pure coincidence. The search tree it uses is anything but balanced, could this be described as lopsided?

Anyway, at some moment mid-contest, the program made some real bad mistakes (short-sighted eating of opponentspieces) as if it had had half its brain surgically removed through a lobotomy. This (well, and Fred′s remark that lopsided had missed the high quality level for the Program Name Award) caused me to consider renaming it loapotummy. However, the program improved behaviour again and I kept the original name.


The first principle is look-ahead.
I build a game tree in memory of unspecified (and varying) depth, but bounded memory. I limit memory to what can be allocated without much harm to avoid swapping although swapping would not count significantly against sys+user time (while it would cause the wall-clock time to explode). With a fixed depth it would have been wiser to save memory and do recursion with intelligent pruning, but

  1. I did not want to force a strict time management on a search with (growing) fixed depth.
  2. Originally I wanted to keep results (i.e. the tree) across moves; however, that was unfruitful, mostly because even with a very lopsided tree only so little information would remain valuable that the overhead turned out to be not worth while. (The overhead was fairly little, though, as I used memory-mapping instead of rereading a file; the thing would have been pretty cool if it had only been of any use).

I repeatedly make a "thought" as long as there was space and time left.
A thought consists of expanding one leaf of the tree, estimating the resulting new leafs and adjust the rest of the tree accordingly.
There remains the problem of deciding where to expand the tree and how to estimate positions.

Where to expand?
For each thought, I follow the tree from its root, always going to the best child. Well, not always: At each level I would visit the next-best child and so on if it had been neglected too much (visited 5 times less than others). This would pursue apparently good variants deeper until I am happy or until they turn out to be not so good at all without neglecting others too much.
How to estimate a position?
Without any experience in LOA, I had no big idea how to make a static evaluation of a position.
I describe below what I have actually done, given a position after my opponents move:
Count connected components of me and you.
if #components(you)==1, subtract 12 from score and "finalize" this position. (i.e. instead of small numbers as with usual evaluation, set the value to +infinity, -infinity or 0 and make sure we will not try to expand any further).
Otherwise, if #components(me)==1, add 12 to score and finalize.

[ Of course, also a check of the 50 move limit is made and also failure to expand a position (i.e. player has no valid move) is recognized, but that happens outside the position evaluation function ]

The remaining cases depend on the score (or rather score difference, I do not even save the individual scores of the players):

If I am way behind (i.e. "accidental" connection, perhaps with a capture, might almost lead to a loss):
Count 4 points per score point; add minimal extra points (1/256 each) for each component of me or you and each piece (of me or you).
In other words: Absolute top priority is scoring. Apart from that reducing the number of connected components is a bad idea as that might make the game end sooner.
If I am way ahead:
Kill! Kill! Kill!
Each component of either you or me counts -4 points, as does each piece.
Add score/256 just to add a secondary influence.
Otherwise (score not very decisive):
  • Each score point counts 1.
  • Having few components is good (less to connect):
    n components result in 10.0/n points for the owner.
  • Having more pieces is good (more potential moves):
    The owner of 2 pieces gets 1/3 point, for 3 pieces 1/6 point, otherwise no change (piece count is in fact already somewhat covered by capture score)
  • Prefer them nearby (don′t know if that′s realy wise):
    Count Your pieces and all their adjacent fields (whether empty or not, but do not count twice). Each counts -1/10 points for the owner, so an isolated piece might count up to -9/10. (Again, this indirectly counts pieces, *sigh*)
  • Center is good:
    Each piece on the center field or on one of its four horizontal/vertical neightbours adds 1/4 point to the owner; each piece on a diagonal neighbour of the center adds 1/8 point to the owner.
  • Blocking opponent is good:
    A piece on the boundary and next to a piece of the opponent (not necessarily on the boundary) counts -257/256 for the owner.
The numbers used are more than arbitrary, the blocking count could be more sophisticated, things like guarding the bonus fields could be better emphasized, etc. etc. etc.
Since my method involved creating leafs at various depths, it is important that they be comparable (i.e. that making a good move does not change the estimation function a lot). Therefore, I "gauged" (once per run) the three main cases (way ahead, way behind, intermediate) to avoid too high jumps.

Now the sad part: In many games, this method is not or hardly used.
I have continuosly been building up an opening library for the most often played variants (esp. all positions occuring in the first ten moves of any game of lopsided against the various SYSTESTs).
The suggestions from the opening library were collected by letting the same lopsided program run but with much more time or possibly more space granted (and compiled with optimization and run on a fast machine with much memory).
Some positions were fed into a variant of lopsided that makes (pruned) search up to a depth of 12 ply, say. I did this especially with positions that appeared to be very "critical", i.e. the normal method would cause a loss within 12 ply.
I even let the program run overnight with even deeper depth for two or three extremely critical positions.

Just a few days before deadline, it turned out that this search program had some bugs, thus rendering my library theoretically worthless (although this was not obvious from lopsideds good results). As of writing this, the complete executable including library of more than 2000 positions is approximately 100KB (might still grow a bit until the end of contest), way below the limit of 300KB that Fred had imposed to discourage too big libraries. I assume that the POTMaster would have considered this library too big, so the rules are going to be tighter next time.

My latest (but unnecessary--it saves less than .01s per move) modification of the library was to add a hash for faster lookup with binary search and to store the precomputed positions in a compressed form (again not necessary--the 300KB space limit was never in danger of being touched) reducing the space needed per library position from 40 bytes to 14 bytes (minimally slowing the program down again due to alignment faults [yeah, I should have padded to 16 bytes] and the need to decompress the one or two positions with suitable hash)

Try Again?

I wish I had read more about modern game algorithms. I could not make use of α-β-pruning because I did not know how to handle the 60 secods time limit then. With more advanced techniques like transposition tables (i.e. hashing and caching good ideas&emdash;ideally with a surviving temp file), and maybe some ideas about conspiracy numbers which I found on the net only in the recent weeks would have made a thorough α-β-implemetation feasible.
Well, at least the offline library calculator could have gained from that.

My estimation function is very hand-cooked. Instead of brute-forcing a library, i should have invested more time in optimizing the estimation function...

7. Enveloap scored 118   (59 wins, 15 losses, 0 draws)
In 59 wins, avg winning margin was 14.88 points and game length 19.03 moves. Overall avg game length 20.31 moves.

Kevin Burfitt

Where? Melbourne, Australia
Im the Senior Producer at Atari Melbourne House (I make computer games for a living). Ive previously been a Lead Programmer but crossed over to the dark side of management
Who? I live in Melbourne, Australia with my wife Erica and my 6 month old son Hunter(assuming you are reading this in late January 2006).
Im a programmer by nature, a nerd/geek with no sporting ability as such. I have however managed to excel in a few things close to sports!

Ive bowled a sanctioned perfect 300 game in tenpin bowling (5 man team, probably the first time it was ever done in Australia in a 5 man team)
Im also the state champion and state record holder for a form of Archery known as Clout, which I only started last year (not bad success so far!)
Im also a bronze medallist from the World Masters Games in Beach Volleyball!
I wanted Anteloap but it was taken, so settled for Enveloap. My code doesnt actually try to envelope the opposition though :-)
Approach Enveloap does the following:

First, sees if it has the current board in its library, if so it uses the library move (hope its a good one!)
Then, starts a lookahead of 4 deep using the best 13 moves at each level
Best move is based on score plus number of groups plus standard deviation of pieces

The library consists of opening moves, and "closing moves" which it has previously found using a slightly slower version of the program - these are basically the choices it would have made if it had enough time.

Enveloap has no knowledge between moves, although this would have allowed better strategy I couldnt really be bothered figuring out how to do it!

Unfortunately my home computer died during the new year, so my progress stalled - I managed to make a few updates in the final hours but actually had a stronger version in progress on the PC that died (better lookup tables)
Try Again? Alpha-Beta searching, better heuristics

but Im a "brute force" kind of guy, I probably wouldnt have got them working anyway :-)

8. linemup scored 114   (56 wins, 16 losses, 2 draws)
In 56 wins, avg winning margin was 11.38 points and game length 17.89 moves. Overall avg game length 20.99 moves.

Eric Polino

Where? Home Home is Alberta, Canada, but I am currently living in Collegedale, TN.
What? I am an entry level software developer for the Southern Adventist University. I am also a 2nd year Freshman studying Computer Science and Mathematics.
Who? I spent several years in the Pacific islands where I spend a lot of my time programming. I enjoy other things other than programming. Mostly high intensity sports such as soccer, hockey and recently racketball.
I figured that since the game ended with all the pieces lined up, I would be thoughtful name. Line them up.
Approach My entry was using alpha beta pruning to itteratively search the tree for timeLeft/movesLeft seconds. It utilized killerMoves, transposition tables, move ordering to increase my cutoffs. My evaluation is where I believe my engine lacked the most. It was only checking for clustering, score, and centralization of pieces.

I was using a genetic algorithm to optomize the weight of those evaluation categories. My gAlgo simply played two sets of values against eachother. The winner would move on, the loser would transform into a variation of the winner.
Try Again? Id work on getting a pn2 algorithm working to solve position and give my engine a decent opening book. Id do some more research on good evaluation functions. Last semester I was busy in a programming class, so my entry creation didnt begin till mid-December. Therefore, I would like to start working on my entry earlier next time, given a next time. This was by far my favorite POTM so far, and would greatly like to see more like it in entries to come. Three cheers for the POTM-Master

9. outsider scored 114   (55 wins, 15 losses, 4 draws)
In 55 wins, avg winning margin was 13.42 points and game length 20.42 moves. Overall avg game length 24.66 moves.

Dyakonov Alexander G.

Where? Russia, Moscow region, Ivanteevka (small town)
What? Researcher (Moscow State University)
Who? My name is Alexander. Im 26. I think that POTM is very interesting competition! It is my second attempt... I like programming for fun, sport, science, pretty girls (of course), hiking, and other...
In Russian outsider means loser. So, I suggest, that my program will be outsider.
Approach Simple alpha-beta search (NegaScout modification) + heuristics in evaluation function (for connections).
Try Again? Nothing!
I am tired...
But now I know how to win!!! :)

10. kasporav scored 108   (53 wins, 19 losses, 2 draws)
In 53 wins, avg winning margin was 17.42 points and game length 19.83 moves. Overall avg game length 19.97 moves.

Marcel van Apeldoorn

Where? Heerhugowaard (a small city about 40km north of Amsterdam), The Netherlands
What? Senior R&D Manager at the National Aerospace Laboratory in the Air Traffic Managment & Airports department.
Who? My life in a nutshell;
From a professional point of view:
C64 -> Amiga -> PC (Linux) -> building air traffic control systems

From a personal point of view
Baby -> Scholar -> Student -> Job -> Wife -> Kids
Some parts still need to be filled in, but probably ending in death at the end.
Well assuming I dont win any matches; it is named after Garry Kasparovs slightly dumber brother. However, if I do win a match or two, it is named after the same brother who people thought was Garrys dumber half but actually was brilliant at playing LOAPS.
Approach In short:
search tree (minimax algo with alpha-beta cutoff), iterative deepening with a timer (signal handler) and a timing algorithm which assigns time to use (based on assumption that remainder of the game always last about 15 moves), move ordering based on previous iterations. A small (~5000 entries) offline computed openingbook stored in a hashtable using zobrist numbers (10 bytes per entry). The position evaluation function is a weighted sum of different parameters; score difference, difference in clustering and difference in positions taken. The weights depend on whether we are a certain amount of points ahead or not.
Try Again? I guess it would be the same (but without the minor bug in the opening book; I forgot to copy the symmetric positions). I started without any experience in game theory, and figured that a search tree with some optimizations/pruning would suffice to give some opposition to at least a human player. Later, I found out that the algorithm I came up already existed and had an official name (minimax with alpha beta cutoff).
It was educational (as was the genetic algorithm approach I took in the POTM/NUTS), THANX FRED!

11. FourtyTwo scored 108   (53 wins, 19 losses, 2 draws)
In 53 wins, avg winning margin was 15.57 points and game length 20.04 moves. Overall avg game length 24.97 moves.

Michael van Fondern

Where? Germany, Ense, about 40km from Dortmund
What? Software developer
Who? I am 38, married, no kids so far. I like skiing, climbing, reading, cinema, and programming, of course.
Because 42 was the final answer of Deep Thought, which was not only the computer you all know from Douglas Adamss novel, but also the name of one of the greatest chess machines some years ago.
Approach FourtyTwo uses some classic chess programming techniques, so I will
just give you the main facts in short form:

- recursive min-max-algo
- alpha/beta pruning
- iterative deepening
- presorting of moves, moves with most bonus points first
- null move pruning
- increased search depth for bonus moves
- "killer heuristic" (with one killer move per depth)
- very fast test for connnected areas, avoids rescanning the complete board when possible
- maximum search depth is steered by the remaining time, typical look-ahead depth ist between 6 and 7

You can find detailed explanation on most of these features on

Fourty two does not use transposition tables. I implemented this feature, but it needs a lot of memory and did not make the program really play stronger.

12. abc scored 103   (47 wins, 18 losses, 9 draws)
In 47 wins, avg winning margin was 19.04 points and game length 33.68 moves. Overall avg game length 34.57 moves.

Nawanol Theera-Ampornpunt

Where? Thailand
What? College student
Who? Im currently a Carnegie Mellon University freshman. I enjoy competing in programming competitions.
I was going to give it a better name once I think my program is worthy enough. Too bad it never is.
Approach I just use basic alpha-beta searching. Board evaluation is by score only.
Try Again? I might include the likelihood to connect in the board evaluation. Otherwise, I cant think of anything to improve anymore.

13. 2005_12_03_c scored 98   (47 wins, 23 losses, 4 draws)
In 47 wins, avg winning margin was 13.85 points and game length 18.23 moves. Overall avg game length 23.15 moves.

Lou Thompson

14. Apollo scored 90   (44 wins, 28 losses, 2 draws)
In 44 wins, avg winning margin was 11.52 points and game length 20.20 moves. Overall avg game length 23.91 moves.

Mike Sweeney

Where? Canberra, Australia with Wife and three little scientists + cat in suburbia.
What? Computer Scientist - software architectures, decision support, UI design, semistructured data, hard AI.
Who? 40 something.
Middle runner in many internet programming competitions...
Python, linux, microcontroller hacker.
Badminton player.
Apollo has most of the LOAPS letters and sounds kinda cool...
Approach Final version: Apollo2g 20 December 2005
Python script. 320lines 10kB. No opening book.

About five move look-ahead (3 me and 2 opponent, but less if time is running out) with estimate of move value depending on the difference in value from original configuration to final configuration. Evaluation of move considers points to score, connection of mine or opponents, central positions, pieces joined, opponent chains disrupted, and many others. The evaluator was tuned with many test matches between players with different bias values using the Harrigan referee, but I am sure contains many bugs and non-optimal values...

Apollo will be aiming to finish in the top 10 overall (it certainly cannot compete with the top 3 though), and striving for the best scripting program award.
Try Again? Keep it simple and short. Complex programs are too much like work, and Apollo has become way too krufty. If I was serious about winning, I guess I would write it in C and drag out those books on game theory (trees, pruning, minimax, alpha-beta cutoff, etc), but I do this for fun only (I follow Larry Walls philosophy).

15. jleap scored 86   (41 wins, 29 losses, 4 draws)
In 41 wins, avg winning margin was 13.37 points and game length 22.17 moves. Overall avg game length 25.31 moves.

Johan van der Werf

16. aleap scored 86   (37 wins, 25 losses, 12 draws)
In 37 wins, avg winning margin was 16.59 points and game length 23.32 moves. Overall avg game length 32.18 moves.

Ad Kremers

17. Clowaapsaa scored 80   (38 wins, 32 losses, 4 draws)
In 38 wins, avg winning margin was 11.84 points and game length 22.08 moves. Overall avg game length 23.53 moves.

Martijn Pieterse

Where? Netherlands
What? Code generator
Who? Working in the IT industry for about 8 years now. I have made 3d worlds for traffic experiments, analytical software, and now im building embedded software for lithography machines.

Other hobbies include kung-fu and climbing.
My extry name is Clowaapsaa.
Its a combination of cloaka and loaps, and some phonetical nonsense. I just thought it sounded nice. :-)
Approach I had a recursive min/max function. I think i implemented alpha/beta cutoff, but i am not sure it that really worked as it should.

Depending on the amount of stones on the board a would look more moves ahead. No real time conservation, i would stop looking ahead if i had less than 5 seconds of time left.

4 evaluations to come to the best move:
1. How close are my pieces to each other. A move that would put them closer would be better.
2. How many points would a move give me.
3. Did is hit an enemy?
4. Are things moving towards the center?

Depending on which player is was, how many points i had and which turn it was i gave these 4 options different values.

Hardest part about the whole thing was that you could not evaluate a board, you had to know how you got there, how many points everyone had.
Try Again? Add a dictionary.

18. koala scored 77   (36 wins, 33 losses, 5 draws)
In 36 wins, avg winning margin was 16.14 points and game length 23.53 moves. Overall avg game length 27.77 moves.

Sven Reichard

Where? In Perth, Western Australia.
What? I am a research assistant doing Mathematics (currently, computational group theory) at the University of Western Australia.
Who? I just moved from the Baltic Sea to the Indian Ocean, from Winter to Summer... Actually, the container with our things is scheduled to arrive the day after this contest ends.
As a reference to the country I moved to at the beginning of the year. It also helped that the word contained the letters L O A ...
Approach I used a tree search algorithm known as ABC (alpha-beta conspiracy) search. The evaluation function consists of the following terms:

  1. The bare points achieved on the "special" squares;

  2. A piece placement term which evaluates the position of each single piece;

  3. A connectivity feature based on "minimal weight spanning trees"

Here, I try to avoid connectivity if I am badly behind on points; I try to connect my own pieces if the points are approximately equal; and finally I try to connect either my own or my opponent′s pieces when I am ahead pointwise.

The weighting of these features was obtained through a learning algorithm ("TDleaf(lambda)") during hundreds of self-play games.

Well, that was the plan. The self-learning didnt quite work, so I eliminated the piece placement and returned to hand-tuned parameters. Didnt help me with the last SYSTEST, though.
Try Again? Use the "-Wall" switch! In general, do more testing. Investigate the use of bitboards in LOA, in particular for move generation. However, since 80% of the time were taken by the evaluation function, I guess it wouldnt matter that much.

19. Player scored 63   (28 wins, 39 losses, 7 draws)
In 28 wins, avg winning margin was 14.68 points and game length 23.75 moves. Overall avg game length 28.19 moves.

Andrew Gauld

Where? New Jersey
What? Technical Consultant for AT&T
Who? I like downhill skiing, playing music, and programming.
I never had time to come up with a good name.
Approach Player looks 2 full moves (2 by each side) ahead. The best move is selected by
looking for (in order) a forced win, the best score at the limit of the search, or a draw. If it is in a situation where only a forced loss is available or where there are no legal moves, it will output "RESIGN" rather than a move.

20. raze scored 62   (29 wins, 41 losses, 4 draws)
In 29 wins, avg winning margin was 23.03 points and game length 23.66 moves. Overall avg game length 29.57 moves.

Mark Mammel

Where? Maryland, USA
What? Bioinformatics
Rays are lines (of action?) and raze means to destroy.
Approach Uses standard minimax with alpha beta.
Try Again? I am starting to work on a TD-reinforcement learning approach to evaluate connectivity but I will not finish that in time for this contest. I will try to put together a regular LOA program using the reinforcement learning to compare to other programs.

21. loa_bo_lwp_so scored 62   (25 wins, 37 losses, 12 draws)
In 25 wins, avg winning margin was 17.88 points and game length 19.60 moves. Overall avg game length 30.11 moves.

Doug Jones

Where? Evergreen Colorado USA
What? software developer for AT&T
I wanted to use loa=bo+lwp+so but this got changed, which didnt surprise me. Anyway, its a formula for LOA from an unrelated field (sailboat handicapping). Its short for Length Over All = Bow Overhang + Length On Waterplane + Stern Overhang.
Approach At the moment its just a simple 3 move look ahead with positions evaluated just on points. Connection is recognized and scored appropriately, but no other attempt to connect is made. Hopefully I will get around to making something better.
Try Again?

22. CorporalFlapjackJr2 scored 62   (17 wins, 29 losses, 28 draws)
In 17 wins, avg winning margin was 2.82 points and game length 36.12 moves. Overall avg game length 54.26 moves.

Ben Farrell

Where? UK
What? Software Engineer
Who? I like drinking beer, playing FPS games, going to be movies and rock music.
cause i have a little beaver from canada on top my monitor called CorporalFlapjackJr :-)
Approach approch was to generate a list of valid moves. the version uploaded always picks the last move in this list. Other than that I have not had enough time to do anything more fancy :-)
Try Again? 1) adding opening moves book.
2) at each move, take list of moves and see what one will improve scoring.
3) add some look ahead, try to get connection.

23. jon_gnagy scored 56   (16 wins, 34 losses, 24 draws)
In 16 wins, avg winning margin was 1.81 points and game length 41.12 moves. Overall avg game length 54.73 moves.

Fred Hicinbothem

Where? New Jersey, USA
What? Aside from POTM-MASTER AT&T pays my salary to do assorted reporting and data-mining from their web-sites. And I occasionally unclog drains and take out garbage.
Who? Joined Bell Labs in 1968 ... married my high school sweetheart in 1968 and now we are empty-nesters with three kids all out on their own. Three grand-sons (and the POTM) keep me young.
I decided I could not compete with some of the experts, so I decided to "Learn to Draw". Jon Gnagy had a television show in the late 1950s where he taught kids to draw simple figures. He sold a kit and you would draw along with him. I actually had one of these as a kid!
Approach No connection attempt, no look-ahead, in fact: no winning strategy whatsoever although I admit that I considered many, many alternatives before settling in on my goal of trying not to let the other guy win and either run him out of time or reach the 50 move limit.

In order to accomplish this feat (at least to attempt it) I evaluated the current board position and looked at the move both myself and my opponent could make. In its simplest form, jon_gnagy simply tries to avoid having any of his pieces taken and tries to always move to squares which will not be under attack by the opponent on their next move.

Along the way I considered many "weighting" factors to try and evaluate the best move without doing any "look-ahead". Since I was programming in Korn shell, I eliminated deep-diving (or even shallow-diving) look-ahead as an approach very early in my design since it took too long ... I eliminated attempting connectivity since I couldnt figure out an efficient way to evaluate it.

Here are the weights I considered in my evaluation function:
WEIGHTBONUS          # Multiplier of bonus/capture square score
WEIGHTCAPTURE # ADDITIONAL weight for a capture
WEIGHTTOCENTER # weight value of shouldigotocenter
WEIGHTSTOPOPPONENT # weight output of FINDMOVE score of opponent above
WEIGHTKILLERMOVE # thwart opponents near-connectedness
WEIGHTATTACKCENTER # get in position to attack the center
WEIGHTDEFENDCENTER # get in position to attack the center if opp goes there
WEIGHTDRAW # weight moves towards single square
WEIGHTAVOID # avoid capture by encouraging moves to safety

I tried a LOT of combinations along the way! For my final attempt, with the goal of achieving a draw, I chose WEIGHTAVOID=10 and WEIGHTDEFENDCENTER=1 ... the intended effect was to always avoid capture and if all pieces were safe to choose a defense of center square move that did not move me into danger. All other weights were set to zero. My object was to have as few pieces of either kind removed from the board - thus prolonging the game and maintaining complexity to the best of my ability. Of course, I cannot compete against programs which attempt to achieve connectivity - but I have set my goals and will be satisfied with scoring a few points for ties!
Try Again? I think actually playing a game or two might have helped ...

24. MyOwnPrecious scored 55   (24 wins, 43 losses, 7 draws)
In 24 wins, avg winning margin was 19.33 points and game length 25.71 moves. Overall avg game length 28.73 moves.

Tomasz Machalski

Poland, Wieliczka
Really, nothing interesting to say here :)

Recently I was watching Lord of the Rings... :)
Unfortunately I had no free time to develop and enhance my program. The first version was very simple and did not look ahead into the next moves. It just tries to calculate the score for current situation on the board and choose the move which will improve this situation for me and worse for the opponent.

Thats all :)
Try Again?
Game tree and deeper thinking ... :)

25. refractory scored 52   (25 wins, 47 losses, 2 draws)
In 25 wins, avg winning margin was 42.76 points and game length 34.36 moves. Overall avg game length 27.84 moves.

Michael Cook

Where? Kansas, USA
What? College student in my final year
Who? Like computers, video games, cartoons, photography, and more. My homepage is http://www.foobarsoft.com

I needed a name and the idea of the lines in a box made be think of light bouncing around (aka refracting) so I decided to name it "refractory".
My best move is determined by random chance. The program generates a list of all valid move and chooses randomly between them. That was as far as I got (and I was quite proud of figuring that out) before a large school project drew all my attention. I havent been able to work on or update my program since I got it to that stage. I was planning to work on connecting logic as my method of move selection.

26. TheBestMoveIs scored 52   (22 wins, 44 losses, 8 draws)
In 22 wins, avg winning margin was 8.45 points and game length 27.82 moves. Overall avg game length 33.97 moves.

Scott E August

Where? Longmont, CO USA
What? Servo Engineer at Sun Microsystems (used to be StorageTek).
* Name explaination:
* Since I plan on winning this POTM, I did not spend any time trying to
* think of a really good name, and decided to my program what it will be
* producing. "TheBestMoveIs /tmp/inputfile > filecontainingthebestmove"
* Even after the forum discussion about the lameness of names, I still
* continued to work on the program vs. trying to think of a better name.
Approach * Analysis:
* Move types:
* 1) Win/lose
* a) current move
* b) next move
* 2) Opening moves - player1
* a) first move
* b) second move
* c) third and beyond moves
* 3) Opening moves - player2
* a) first move
* b) second move
* c) third and beyond moves
* 4) Connection
* a) Make move to connect pieces
* b) Make move to block opponent from connecting pieces
* 5) Capture
* a) Make move to capture opponents piece
* b) Make move to avoid/promote capture
* 6) Points
* a) Make move to get points in square
* b) Make move to setup next move to get points in square
* c) Make move to prevent opponent from getting points in square
* 7) Blocking
* a) Make move to reduce opponents possible moves
* b) Make move to avoid reduced possible moves
* 8) Random - to select one move from a list of all the best moves when
* move values are the same
* Knowledge needed to determine move types
* 1) Points after move and connectivity
* 2) Other selections need to be in place before evaluating the opening
* moves
* 3) Player1 moves need to be in place before evaluating player2 opening
* moves
* 4a) Change in connectedness
* 4b) Change in opponents connectedness
* 5a) Will move capture opponents piece
* 5b) will move prevent/promote piece from being captured
* 6a) Will move get points in square
* 6b) Will move setup possible points in square
* 6c) Will move prevent opponent from getting points in square (will move
* keep opponent away from getting points in square)
* 7a) Will move reduce opponents possible moves (by how many)
* 7b) Will move avoid possible reduced moves (by how many)
* 8) Number of moves
* Strategy:
* Move selection will be determined by the sum of gains applied to attributes
* of each moves.
* Method:
* Test all move types against all opponent move types
* Test combinations of move types against all combinations of move types
* Connectedness:
* The diameter of the minimal-spanning-tree of graph:
* Longest all-pairs-shortest-path.
* The distance is measured by the minimal number of steps from one point
* to another. A step can be one position change horizontal, vertical
* or diagonal.
* A totally connected tree will have diameter of 0 (steps are counted
* from 0 - connected nodes).
* Sequence for determining gains:
* See TheBestMoveIs.txt
* Current algorithm:
* Evaluate all valid moves for a value determined by the sum of:
* Win/lose
* Points gained by the move:
* The value of the move is increased by 3 for landing on a 3 square
* and increased by 7 for landing on a 7 square
* Moves that setup the piece for the next move to gain points:
* The value of the move is increased by 3 for setting up to get a 3
* square on the next move and increased by 7 for setting up to get a
* 7 square on the next move
* Moves that reduce the opponents possible point moves
* Moves that capture/avoid capturing opponents pieces
* Moves that avoid/promote opponent capturing pieces
* Opening moves
* Blocking and avoid being blocked
* Connectivity
* Evaluate all combinations of move types above for best gains
* Next algorithm changes:
* Determine first move for player1
* Determine first move for player2 given player1 move
* Evaluate all combinations of move types against all combinations of opponent
* move types - determine best gains against all opponent strategies

27. Jan30eve scored 49   (23 wins, 48 losses, 3 draws)
In 23 wins, avg winning margin was 24.00 points and game length 29.70 moves. Overall avg game length 35.61 moves.

Ernst Munter

Where? Ottawa, Ontario
What? Retired telecoms engineer
Who? I am not a professional programmer but have written small and medium size programs for various applications, on and off, for the last 40 years, starting with ALGOL and progressing through various assemblers for mini computers, to mainframe FORTRAN, and eventually PASCAL, and finally C and C++ on DOS and Windows PCs. My favorite platform is now Mac OS X.
Ive been trying to (a) get the program to work correctly, and (b) see the runtime on the POTM site. The entry Jan24 was the last of a series of versions to this end. It was sent in on January 24, is not very good and will be replaced.
Since Jan24, I continued to work removing bugs and testing against the (unbeatable?) System6. My program uses a generic alpha beta search. Points as per the rules are accumulated forward to the deepest recursion, and reported back as the value representing the quality of the move. I observe time and allow 1 extra or 1 less deep search depending on average time per turn so far.

No data is saved across turns. As I observed System 6 always going for connect, and thus winning even if I was ahead on points before, I decided to give Connect extra weight in the search. But it did not seem to matter.
Oh, and before each recursion of the alpha beta search, I collect all possible moves, and sort them by their simple weight, biased towards the bottom of the board, and randomized (using time-left for a seed) to avoid getting into cycles with the opponent.
Try Again?
I would make me a test program first, to allow myself to play against it or a version of itself. And instrument the program better. Given the relatively long time allowed per turn, I would have found a better way to prune the search, probably including a small look-ahead in the "collect legal moves" phase in order to get a better sorted set of moves. This would probably allow deeper searches in the same amount of time.

28. Loa_Master scored 45   (21 wins, 50 losses, 3 draws)
In 21 wins, avg winning margin was 7.57 points and game length 13.71 moves. Overall avg game length 17.62 moves.

Moaz Reyad

Where? Cairo, Egypt
What? Software Developer (C++)
LOA stands for "Lines Of Action" and simply it is the name of the contest topic.
Try Again?

29. mjr scored 45   (19 wins, 48 losses, 7 draws)
In 19 wins, avg winning margin was 7.21 points and game length 32.05 moves. Overall avg game length 36.38 moves.

Pascal Muetschard

San Jose, California, USA
Sofware Engineer
I was born in Zurich... nough said.

That shall remain a mystery.
- negascout with quiescence (captures, points and connecting)
- board evaluation:
  - scores assigned to each row - edge is bad, center, point squares good
  - bonus for quads of three or four
  - bonus if few groups
  - if score difference < 12, ignoring score, otherwise big factor
- uses a flat array for board, keeps base-3 values for each row, column and diagonals for fast move generation, uses quads to determine whether to check for win situation
Try Again? - center of mass
- board mobility
- threat avoidance

30. FastModestGreedyHobbit scored 43   (15 wins, 46 losses, 13 draws)
In 15 wins, avg winning margin was 12.87 points and game length 26.87 moves. Overall avg game length 33.57 moves.

George Sakkis

Try Again?

31. b_line scored 42   (17 wins, 49 losses, 8 draws)
In 17 wins, avg winning margin was 21.88 points and game length 32.82 moves. Overall avg game length 32.65 moves.

Darren Stone

32. Antelopes scored 42   (16 wins, 48 losses, 10 draws)
In 16 wins, avg winning margin was 3.19 points and game length 26.31 moves. Overall avg game length 36.03 moves.

Tom Muylle

Where? Belgium
What? Student, 22 years old.
Who? Started programming in QB way back when, did java in university (I didnt have internet to learn about C heheh). Picked up bits of perl, php, matlab, haskell, prolog, c, c++. Python was a new language, and I only started it for this POTM because a start was available on the forum.
I wanted it to be Antilopes, the Dutch spelling, but that wasnt possible in English. It sounded funny.
Approach I started from the basic random solver, and played a bit against my brother. IIRC I tried to look at the move that gave me the best points (I forgot if the final version checked for 1 point by taking another piece). Then I looked if that move could cause the other player to win by connecting or taking a piece of me. If so, dont do that move. If it seemed fine, do the one with maximum score. If multiple moves were available, do the one that makes all pieces more clustered. I think I took a mean value of all positions and then looked at every move to see which got closest to those coordinates. If no move was possible (all moves made the other player have an opportunity to win), it printed "I resign" to not let the other one have the full glory of the winning move. Thats why my program always ended with badout.
My algorithm consisted only of 2 layers of search. I even hardcoded them. It was really bad, but bleh. Read next question.
Try Again? Finish the program. I lost interest in it a bit (sorry), then had exams. I know its no excuse. I had fun making it in the beginning though, so I dont look back on it in a negative way.

33. ChittyChittyBangBang scored 39   (19 wins, 54 losses, 1 draws)
In 19 wins, avg winning margin was 11.74 points and game length 17.79 moves. Overall avg game length 18.16 moves.

Dale Miller

Where? In Wisconsin, USA.
What? Physician
Who? This is my first entry at POTM. I am a hobbyist programmer who still
uses the restricted IDE (VC++ 6) that came with the book I bought to
teach myself C++ programming. My goal as a result of
participating in this contest is to extend my comfort range in programming and enjoy the mental challenge along the way.
I have named my program ChittyChittyBangBang because:
1) chits are game pieces, there are two players, therefore--ChittyChitty
2) a strategy I tried early on was to eliminate as many opponent chits as I could, hence Bang Bang, like a gun used to eliminate the opposition
3)and my program will undoubtedly seem unsophisticated when compared to the competition (just like the infamous childrens movie of the same name).
Approach My program is in C++ because its the only language I know something
about. So far my program focuses primarily on my players options, and not
the opponents options.

My program declares a number of classes to encapsulate the various
structures needed to play the game--theres a class to represent the
game, the board, the player, etc. The board is made up of an array of
cells which are connected in various ways including lines and chains,
each of which is represented by its own class. In addition Im
working on developing a tree of moves/boards to look into the future
rather than just the current move. Since Im having trouble doing
what I want with the tree using forward declarations, friend
classes/functions. etc, Im going to try just writing the tree members
into the Player class rather than having a class to represent the
tree(s) as a stand alone concept.

The program analyses the board position it is given into the number of
and location of each chit, how many chits are on each line of
the board and what chains of chits are present for each player
on the given board. With this information I can determine the
number of legal moves from this board and rank each of the
moves based on a series of evaluations leading to a numerical
value associated with the move. Value is gained or lost for
things such as advancing toward the middle, creating a chain
that is longer a prior chain, disrupting the opponents longest
chain, finding a move to connect (me or opponent) and analyze whether it is
worth doing or not based on current game points, whether a bonus square
is occupied as a result of this move, whether an opponents piece
is removed, can I block the opponent from getting to center square,
etc. The program then selects the best legal move to report.

I am able to time the entire process
internally, but since the timing of my efforts is measured in
milliseconds per match, so far, its not of any consequence.
I suspect if Im able to start evaluating tens/hundreds/thousands
of options/boards/moves into the future, that time may become more
of a factor.

When/if I get my tree up and running it should look at all legal
moves starting from any given board a given number of moves out.
Obviously, if I restrict positions to just mine I can extend the
horizon further but the cost of ignoring the opponent is very
high as demonstrated by the results of the systest runs. At the
moment each node of the tree has a board, the move used to get to
this board, and the cumulative value of all moves in the path from
the root of the tree to this node. Each node also has a pointer to
the child, sibling and parent of the given node. When thought of
as a generic tree, each level represents all the possible moves for
each successive opportunity to move. The pointers allow for the
generic tree to be represented as a highly unbalanced binary tree.
Each node can be considered the root for a child and the roots
siblings, much like each person is connected to his/her parents,
their own brothers and sisters, and their own child(ren). However,
each node has no idea of how many children or siblings
it has, just that it does or does not have a parent, child, sib.
Using the group of legal moves available for each
node to go the next level, the first legal move is the child of
this node and each of the other legal moves are siblings of that

On extending the tree to the next level the program collects
all of the legal moves for this node, evaluates them for their
value, and adds the vale to the value of the parent. I carry a
maxPathValue along and any new path with value higher than the
current high value is saved. That path value will become a
future value for the original legal move at the root of the tree,
and it can be added to the hear and now values already identified.

Now, if I can only get it to work!
Try Again? I would run my program through more tests. I lost 9 games because I didnt recognize an opponent to my left and tried to jump over them. I my world that would be described as homonymous hemianopsia. In this locale it is a bug.

34. FridolinSchabernack scored 32   (14 wins, 56 losses, 4 draws)
In 14 wins, avg winning margin was 11.79 points and game length 19.86 moves. Overall avg game length 24.26 moves.

Lutz Steinbach

35. JohnnyMnemonicLoapIt scored 31   (12 wins, 55 losses, 7 draws)
In 12 wins, avg winning margin was 5.00 points and game length 13.58 moves. Overall avg game length 28.80 moves.

Pat McGinnis II

Cocoa, Florida, Usa
What? Too many
Who? Age:35 , been whacking a keyboard since I was 11. I can build you a house, or program your computer...how much $$ you wanna spend?
The movie Johnny Mnemonic... hes got this data in his head and has to loop it to get it out! Thus: LOAPIT!
Approach My PHP script is limited by the time factor. So I could only realistically look ahead for 3 moves without pruning. So I concentrated on optimizing this given that the hosting machine isnt using php5...yet. The opening book consists of 1 move, it does a depth 1 search, if any moves give a score>6 it does it (greedy...saves clock ticks). Else it looks for the best line (depth 3) by assuming its opponent would find the best move for itself. Its fairly simple, it does test for connectivity (for scoring/ eval) but doesnt NULL move or look beyond depth 3 for anything. I like my connectivity tester. Basically, a not so bright mother of 8 cannibal squirrels with nothing to lose.
Try Again? I have tried many variations. The variation I liked the best (but did not submit) added more weight to squares toward the center of the board. Any square within the middle was worth more than one on an edge. This seems valuable in a low depth searching program, when you definitely have more than 1 possible move that weight the same.
I did zero thinking about blocking moves!!!!!

36. bitshifter scored 15   (6 wins, 65 losses, 3 draws)
In 6 wins, avg winning margin was 4.17 points and game length 12.33 moves. Overall avg game length 20.74 moves.

Jeffrey Fielding

37. helloWorld scored 2   (1 wins, 73 losses, 0 draws)
In 1 wins, avg winning margin was 1.00 points and game length 1.00 moves. Overall avg game length 1.49 moves.

Vinay Jethava

38. LOAPS_JiuJitsu scored 2   (1 wins, 73 losses, 0 draws)
In 1 wins, avg winning margin was 1.00 points and game length 1.00 moves. Overall avg game length 1.49 moves.

Guillermo Sais

The POTM is unsponsored and just for fun.       Tuesday 12:13:00 AM      Copyright © 2004-6 - Fred Hicinbothem