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)

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...

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"

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