POTM Home POTM Forums Previous Contests

05/2005: » POTM home » introduction » the details » system tests » final tests » tiebreakers » final boards » code » entry descriptions Members Section » NEW USER: sign up » POTM forums » POTM sandbox » email Fred »  Who visits?

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. panda scored 128   (64 wins, 0 losses, 0 draws) In 64 wins, avg winning margin was 8.62 points and game length 33.83 moves. Overall avg game length 33.83 moves. YOUR HANDLE: avm YOUR NAME: Anton Maydell YOUR ENTRY: panda Where? Russia, St-Petersburg What? no job Who? EDUCATION 1998-2003 St-Petersburg State University. Valladolid Online Judge Top User Winner SPOJ Open Contest 2006 Author Winboard chess engine Eeyore Program Name? Approach Q. How did panda solve the LINESANDBOXES POTM? Openning * no Middle game * NegaScout * hash with replacing scheme DEPTH and NEW * zugzwang detection (deeper search in zugzwang position) Endgame * NegaMax search with memoization (positions with 17 free lines) * detect zugzwang patterns in root position a) "2x2 squares pattern" (-2 score) b) "3 connected squares" (-1 score) c) "blocked corner" (-1 score) Q. Did you use strategies from the original DOTS and BOXES game? No, I never play DOTS and BOXES game. Anybody interesting game programming, I recommend visit this site Links for chessprogrammers Try Again? I has not motivation do it again. 3 months contest duration is too long for me. 2. AllYourBoxAreBelongToUs scored 122   (61 wins, 3 losses, 0 draws) In 61 wins, avg winning margin was 10.49 points and game length 33.31 moves. Overall avg game length 33.12 moves. YOUR HANDLE: Tempus YOUR NAME: William Little YOUR ENTRY: AllYourBoxAreBelongToUs Where? The USA. More specifically, right here, or in the general vicinity of nearby. What? What's on second. Who? No, What. Who's on first. Program Name? AllYourBoxAreBelongToUs. Why? FOR GREAT JUSTICE. Approach Start by preparing the search engine. In a medium mixing bowl, blend 1 cup each of NegaMax, MTDf, and Alpha-Beta Cutoff, withholding the alpha. Add one drained can of hash, Zobrist if you can find it, but any brand will do. Whisk the mixture until it forms stiff peaks, or until you can no longer lift your arms. Next prepare the evaluation function. In a small bowl, thoroughly mix a pint of the current score differential, one teaspoon of Nim, and the remainder of the melted butter. (The Nim is the secret ingredient, without which we would need considerably more search to feed the same number of people.) Stir until life loses all meaning. Gently fold the completed evaluation function into the search engine. Do not over stir. Once incorporated, transfer the completed program to an oven safe dish, and bake at 350 degrees for about 30 days. Once cool, chisel from dish with a pneumatic drill, and sprinkle with program description immediately before serving. Makes about about three dozen servings. Try Again? I probably should have: - Started earlier - Spent more time on it - Flossed - Incorporated more game knowledge into the evaluation function - Baked at a higher temperature 3. Succulence scored 118   (59 wins, 5 losses, 0 draws) In 59 wins, avg winning margin was 8.80 points and game length 32.78 moves. Overall avg game length 32.56 moves. YOUR HANDLE: mmaxim YOUR NAME: Mike Maxim YOUR ENTRY: Succulence Where? Santa Barbara, CA What? Software Developer Who? Went to Carnegie Mellon for B.S degree in Computer Science, work at Green Hills Software in Santa Barbara, CA Program Name? It plays on a succulent level. Approach Succulence literally plays randomly in the beginning of the game, it just selects moves that touch boxes once. This allows it to get the game spread out and ready for it to try and overpower other programs with its lookahead capability. Once this phase is over, then it uses alpha-beta search with standard improvements (PVS opt, null-move, transposition table, etc.) to search for the best move. The evaluation function is very simple (probably overly). All it does it see how much length Succulence accounts for on the board, and tries to minimze this value. As a result, most of its moves span only one set of dots. It also obviously looks to see who leads in box count. Move generation is very fast, all moves are precomputed at start time. To generate moves, all you do is obtain a 32-bit signature for the move, use that in the lookup table, and you have moves. Similar steps are taking for getting things such as what boxes are touched by moves. Capture moves are search first, and are determined at move generation time. No opening book is used, although my executable is like 312KB, so I guess Ill need to ask for an exception. I did not use any strategy from Dots and Boxes. Try Again? I would try and make it so that Succulence would play more aggressively in the beginning, and not get into situations with large cascading capture sequences which it sometimes gets lost in. I think it also has some bugs, but I ran out of time, I started pretty late into the contest... 4. Zola scored 114   (57 wins, 7 losses, 0 draws) In 57 wins, avg winning margin was 10.00 points and game length 33.04 moves. Overall avg game length 32.67 moves. YOUR HANDLE: sven.reichard YOUR NAME: Sven Reichard YOUR ENTRY: Zola Where? In Perth, Western Australia What? Im doing a post-doc in Pure Mathematics. Who? Originally from Germany, married to an Italian, college in the Middle East, graduate work in the States, working Down Under... hopefully Ill get a permanent position in Antarctica :) Program Name? In German, the original D&B game is called Käsekästchen, that is, cheese box. Zola is short for Gorgonzola, my favourite cheese. Approach Very basic alpha-beta lookahead. The only evaluation feature is the box differential. Iterative deepening, Zobrist hash tables. Reaches 4 ply lookahead in the opening, 15 ply in the endgame on the target machine. Uses bitmaps for legal move generation and for counting captured boxes. Try Again? 5. Sunny_Coupe scored 108   (54 wins, 10 losses, 0 draws) In 54 wins, avg winning margin was 8.98 points and game length 32.85 moves. Overall avg game length 32.45 moves. YOUR HANDLE: mmammel YOUR NAME: Mark Mammel YOUR ENTRY: Sunny_Coupe Where? Laurel, MD, USA What? Bioinformatics. Who? Live with wife and 2 kids, like to go geocaching/orienteering/hiking. Program Name? Datsun (Dots and) makes a car called Sunny Coupe. Approach Simple alpha-beta game tree search. Try Again? A better heuristic for game position. 6. simplesandboxnote scored 98   (49 wins, 15 losses, 0 draws) In 49 wins, avg winning margin was 6.84 points and game length 31.76 moves. Overall avg game length 31.09 moves. YOUR HANDLE: mvapldrn YOUR NAME: Marcel van Apeldoorn YOUR ENTRY: simplesandboxnote 7. DosPassos scored 94   (47 wins, 17 losses, 0 draws) In 47 wins, avg winning margin was 8.64 points and game length 32.55 moves. Overall avg game length 31.80 moves. YOUR HANDLE: hagman YOUR NAME: Hagen von Eitzen YOUR ENTRY: DosPassos Where? Bonn, Germany What? Sysadmin of a somewhat big law firm. So You better let me win or they will sue You! Who? Im 40 years old, live in Bonn and love to compete in online programming contests until my better half gets upset. Program Name? With Miro already taken, I thought about a street grid as in Manhattan. I wanted to make a reference to some song by the 80s vocal group Manhattan Transfer, but then I found out that there is a novel named Manhattan Transfer. The name of the author is Dos Passos, and I never assumed my program would be able to look ahead by more than dos passos (two steps). Approach I try to look ahead with alpha-beta, but the huge number of possible moves makes this unfeasible. I note that positions can repeat (e.g. by switched moves) even when it is the other players turn (if lines concatenate), therefore I make use of a hash array (which survives between moves). First level lookahead selects the top 20 moves (according to preliminary value function), second level as well. Deeper levels are investigated if and as long capture moves are possible, but at most 10 moves per level. As a shortcut, if in the first two levels a capture is possible, only capture moves are regarded (even if others appear better by value). Investigation stops prematurely if time is running out, but only after at least one child (and child of child ...) has been investigated. While in all deeper levels, moves are sorted by immediate value (it is always better for alpha-beta if You investigate the right move first), the first level moves are sorted better: A first run is simulated with each possible first move under the assumption that time has run out. In other words, only the main variant according to immediate value (or already cached fully-fledged value) is investigated to determine a rough estimate. This is only used for sorting first level moves, the full investigation follows. A short note on the immediate evaluation function: Count boxes produced by a move with 1, 2, 3 edges around. (4 edges = captures go into another statistics) Assuming a capture as 1 unit, count 3 edges as -1/3 units (as it probably allows the opponent to capture this), 2 edges as +1/9, 1 edge as -1/27. The numbers were not chosen for any particularly reason, at least not for a good one. Try Again? Find a better immediate evaluation function, have a look at some meta-features, e.g. bounded 2x2 boxes that occur so often. 8. _IHES scored 80   (40 wins, 24 losses, 0 draws) In 40 wins, avg winning margin was 9.85 points and game length 32.05 moves. Overall avg game length 31.22 moves. YOUR HANDLE: Boris YOUR NAME: Boris Levine YOUR ENTRY: _IHES Where? UK What? Who? Program Name? Im programmer, you know... so: LINES&BOXES = L & B = @ I & O = I N & X = H E & E = E S & S = S so it turned out to be "@IHES" but sandbox decided that it will be "_IHES" ... sandbox is almost POTM Master,- so Im not complaining.... :) Approach Sorry guys, I have to take out my entry from competition, I havent touched it for months (last submit somewhere in March...) because of absolute "zeitnot".... really pitty, I had few nice ideas and sure would finish in top 3 places... Boris Try Again? 9. Lunokhod scored 80   (40 wins, 24 losses, 0 draws) In 40 wins, avg winning margin was 9.15 points and game length 32.90 moves. Overall avg game length 31.48 moves. YOUR HANDLE: toljan YOUR NAME: Anatolijs Gorbunovs YOUR ENTRY: Lunokhod Where? Riga, Latvia. What? I study in school. Who? I like Informatics, Physics and long distance running. Also a bit playing guitar and singing. Program Name? Because of Soviet Lunar robots called Lunokhod-1 and Lunokhod-2... Approach Just brute-force deep-first search with variable depth, depending on time left. Try Again? The same, but a bit more heuristics, maybe. 10. FlatLand scored 80   (40 wins, 24 losses, 0 draws) In 40 wins, avg winning margin was 9.15 points and game length 31.02 moves. Overall avg game length 30.25 moves. YOUR HANDLE: scotta YOUR NAME: Scott E August YOUR ENTRY: FlatLand Where? Longmont, Colorado USA What? Servo Engineer Who? Program Name? FlatLand: A romance of many dimensions - written by Edwin A. Abbott in 1884 Story of 2-dimensional beings encountering the 3-dimenional world was what came to mind when I first thought of naming my entry PlanesAndCubesTheNextDimension. It would be interesting to play this game in 3-dimensions where cubes are the scoring shape. Approach Analysis: Move types: 0) Random - to select one move from a list of all the best moves when move values are the same 1) Win/Lose - flag == move depth 2) Points a) points gained from move b) points allowed for opponent c) points allowed for next move - assuming opponent takes best move 3) Border - is a boarder piece 4) Outer - makes contact with the boarder 5) Center - distance from the center of the board 6) Length - long vs. short 7) Axis - major axis vs. minor axis 8) Divide - divides a line into forced multiple moves 9) Join - joins line 10) Parallel - parallel to existing lines 11) Perpendicular - perpendicular to existing lines 12) Change in available moves (non-scoring?) 13) Odd/even moves left Knowledge needed to determine move types: 0) Number of moves 1) Game over after move, and point difference 2a) Points after move 2b) Points available for next move 2c) Points available after next move 3) Location 4) Location 5) Location 6) Size 7) Direction relative to board dimensions 8) Position left open at each end 9) Positions closed at each end 10) Positions taken on either side parallel to move 11) Positions taken perpendicular to move 12) Positions open (scoring positions open) 13) Moves available Strategy: Move selection will be determined by the sum of gains applied to attributes of each move. Method: Determine best move type against random. Continue to determine next best move type against previous best move types. Try Again? Not much, I am interested in seeing if this "learning" approach will work - I have tried it on the past two potms, but have had too many bugs to work out to have enough processing time to get throught the gain selection. 11. Dec27 scored 80   (40 wins, 24 losses, 0 draws) In 40 wins, avg winning margin was 10.03 points and game length 32.67 moves. Overall avg game length 26.00 moves. YOUR HANDLE: InsaneWayne YOUR NAME: Johan van der Werf YOUR ENTRY: Dec27 Where? Eindhoven, The Netherlands What? Embedded Software Engineer Who? I am 49 (almost), married, no kids. Hobbies are reading, Japanese language, programming and solving puzzles. Program Name? Because BoxingDay, my first choise, was already taken. Approach In the initial stages Dec27 tries to cut up the board in bite size pieces as many as possible and preferably of approx. the same size. Once the board is cut up and no more "harmless" moves can be made it tries to get in step with the opponent in such a way that the opponent has to eat all the negative boxes. When there is only one fight somewhere on the board a minimax algorithm takes over that tries to maximise the points while not losing the advantage. Once advantage is lost, Dec27 has several algorithms to restore it, sometimes even by offering boxes to the opponent when that is the only way. Try Again? Store and reuse data across moves. 12. hakone scored 76   (38 wins, 26 losses, 0 draws) In 38 wins, avg winning margin was 7.79 points and game length 32.05 moves. Overall avg game length 30.27 moves. YOUR HANDLE: fred YOUR NAME: Fred Hicinbothem YOUR ENTRY: hakone Where? New Jersey, USA What? During the day I work in Web Analytics, deriving insight from gigabytes of raw data. During the evening I am omnipotent. Who? Married, three kids, three grand-kids ... currently looking around to find an "adult community" in which to spend my retirement - one with high-speed internet of course. Program Name? The first Japanese puzzle boxes were designed over 100 years ago in the Hakone region of Japan. Puzzle. Boxes. Ah well, I cant win best name anyway. Approach I looked at all possible moves and used an evaluation function to determine which move to make. If two moves scored equally I chose one at random. My evaluation function valued box completion (adding the fourth side of one or more boxes) most highly. I De-Valued adding the third side to a box and encouraged adding a second side to a box. I was able to do a one move look-ahead to see what my opponent might answer with using the same evaluation function ... but only during the end-game on smaller boards. KSH is fun, but not particularly quick - my clock invariably ran out as the boards and possible moves grew larger. Eventually I only attempted a one move look-ahead if there were less than ten possible moves left. Try Again? I think the notion of evaluating "snakes" and trying to create collections of subregions that were advantageous will be the way to go ... but not by me! 13. SonsOfBecker scored 72   (36 wins, 28 losses, 0 draws) In 36 wins, avg winning margin was 8.50 points and game length 31.61 moves. Overall avg game length 29.41 moves. YOUR HANDLE: lutz YOUR NAME: Lutz Steinbach YOUR ENTRY: SonsOfBecker Where? Brussels, Belgium (but Im a german). What? Sysadmin Solaris. Who? Im used to think about myself as not being a geek. But participating in POTM might strongly indicate that Im wrong about that. Most of my time I spend for work and my family. I dont have enough time to visit Berlin as often as Id like to. Program Name? This goes back to an album title of The Coral: The sons of the rich german ex-tennis player Boris Becker follow their father all over the world to get money out of him. As this isnt much to do it leaves them enough time to be cool and to do interesting things meanwhile .. Approach Original DOTS AND BOXES game: nope, its too different; but I read a bit in Elwyn Berlekamps book to get an idea about how to find strategies for the game. There are 3 kind of moves: 1) scoring moves - moves that capture at least one box 2) preparing moves - moves that draw the 3rd edge for at least one box 3) starting moves - all other moves Basic move finding strategy: - if there are scoring moves play the one that scores most boxes except the opponent has a move as response that scores mores boxes than my move (if so play a starting move) - if there are starting moves play the move that draws the most edges - if no scoring nor starting moves are available play a preparing move For the move classes different optimisations apply (at the end of the game look ahead 5 plies for scoring moves, try to play the last starting move of the game, play a preparing move thatll force the opponent to play the next preparing move etc.) Try Again? I use the POTM to learn some C++. So next time Id try to get the program body faster coded to have some time for profiling, tuning etc. 14. ThinBlackLine scored 70   (35 wins, 29 losses, 0 draws) In 35 wins, avg winning margin was 9.17 points and game length 30.14 moves. Overall avg game length 29.73 moves. YOUR HANDLE: sema638 YOUR NAME: Sema A YOUR ENTRY: ThinBlackLine Where? Russia, St. Petersburg What? Software Developer Who? I like to solve puzzles, therefore I like POTM Program Name? There was the movie "The Thin Red Line", but as we have black lines in LINES AND BOXES, so I called it "ThinBlackLine". Approach The program looks through the all available moves and gives every move a weight. If one move is better than another it gets higher value. Then a list of moves is sorted and the program takes the first move with the highest weight. When program checks a move it checks the next opponents move for determining bad moves that give advantage to oppponent. Try Again? Some better algorithm 15. Malsin scored 68   (34 wins, 30 losses, 0 draws) In 34 wins, avg winning margin was 8.35 points and game length 30.15 moves. Overall avg game length 29.48 moves. YOUR HANDLE: NirmalK YOUR NAME: Nirmal Kamaraj YOUR ENTRY: Malsin Where? India What? Analyst Who? I am a Engineering graguate, completed B.Tech(Information Technology) in the year 2003. Presently working as an Analyst in IT firm. Reading, watching movies, participating in programming competition are my hobbies and interest. Program Name? Never thought if this question would be asked :-) Its last 3 letters of my first name and last three letters of the lady I admire a lot. Approach for a box I gave the following scores 1 -> if left side of the box alone has a line 2 -> if top of the box alone has a line 4 -> if right side of the box alone has a line 8 -> if bottom of the box alone has a line. the score in the box would be bitwise OR of the above scores for the sides filled by a line. so a box would be represented by an integer 0 to 15. for every move the program would search for the line that makes maximum number of boxes with the score 15 and provides it as the output. when there is no such line available, then the program with the unused space tries to build a box with three concecutive emply boxes, giving way for the opponent to capture one box and the program caputres two boxes when there is no space for the above logic to be implemented, the program searches a line that is not the third line of the box and filles it. when there is no such line, the program would then fills the first line available from top Try Again? Yet to think :-) 16. Helena scored 66   (33 wins, 31 losses, 0 draws) In 33 wins, avg winning margin was 7.55 points and game length 31.42 moves. Overall avg game length 25.69 moves. YOUR HANDLE: Corrosion YOUR NAME: Martijn Pieterse YOUR ENTRY: Helena Where? Somewhere in Holland. Near Eindhoven airport. What? Embedded software engineer, integrator, trouble shooter, sometimes even designer Who? just reached the age of 32. Still not getting any older though. These human years dont really count, you see. When im not working im mostly found performing kung-fu, or climbing up some wall. When i find the time i like too cook. Other than that i just wait for the end of the world. Program Name? A long time ago, there was this beautifil girl, named Helena, ofcourse. Since she didnt like me a lot, i had to lure her to my lair. Then when she was sleeping i boxed her! Mhuhahahaha! Hm. That sounds pretty pathetic huh? Well, its just named after the movie Boxing Helena. Which i saw a long time ago. Approach At first i had no idea how to tackle this problem. Made a little program "deepthought" which could analyze small boards. Then i noticed that certain small boards would give you a lot of points if you didnt make the first move in that small board. So my program now just creates a lot of small (hopefully independent) small boards and tries to force the enemy to make the first move. I tried to make some sort of detect routine which can recognize certain configurations. But that didnt work very well, or i was just lazy.. So whenever the amount of moves in a region is low enough i just "deepthought" them all. And store the result in a temporary file. At the time of writing there are still a couple of "TODO/TOFIX" in my code. Things include: 1. Fix the "a lot of squares situation" 2. If there is only a negative chain, to to break the chain, by making a "region crossing" move. 3. The "get the easy points" grab is not always the best thing to do. Other than that it works pretty good now. Didnt look at any other similar program or source code from a DOTS and BOXES game. Try Again? I think i would do the same... maybe if i read other peoples idea, i might want to try one of theirs. Except that my code is now one giant "doit" function. That should be fixed. :) Ow, using some sort of version control would be nice. And i shouldve saved all the games i played against the SYSTESTs and put them on my POTM page (which i dont have). 17. BIFES_50lines scored 66   (33 wins, 31 losses, 0 draws) In 33 wins, avg winning margin was 8.33 points and game length 31.82 moves. Overall avg game length 27.84 moves. YOUR HANDLE: mjs YOUR NAME: Mike Sweeney YOUR ENTRY: BIFES_50lines Where? Canberra, Australia What? Computer Scientist and midnight hacker. Who? Work in a government research lab and live in the suburbs with my wife, 3 kids, and a cat. Hacks microcontrollers, linux, and python. Plays badminton. Program Name? Why BIFES? If we use base 26 with A=0,B=1,etc, and apply a bitwise AND operation between the numbers "LINES" and "BOXES", we get "BIFES"... Why 50 lines? I limited my entry to 50 lines of code, and hoped others might be interested in a mini-entry subcompetition. I thought entries in the subcompetition could be identified by the _50lines suffix. Not much interest though... Approach As I find short useful programs the most interesting (doing the most with the least), I set a limit of 50 lines of code (and one statement per line), and developed the most competetive entry I could. The program creates a number of index structures and populates them with the input data, then interates through all legal moves and evaluates each one to a depth determined by the number of moves available. The evaluator gives a point for captured boxes, and subtracts 1/10 point for each box opportunity created. All else being equal, it also prefers short moves. A small random value is added to reduce its predictability. Try Again? With a limit of 50 lines, most of the program is creating data structures and processing the input data, leaving not much room for an algorithm to find a good solution. Next time, I think a mini-entry should be limited to 70 lines (that would fit on an A4 sheet of paper using raw printing), not 50. 18. CassiusClay scored 62   (31 wins, 33 losses, 0 draws) In 31 wins, avg winning margin was 8.77 points and game length 30.87 moves. Overall avg game length 30.08 moves. YOUR HANDLE: akre YOUR NAME: Ad Kremers YOUR ENTRY: CassiusClay 19. TARO scored 58   (29 wins, 35 losses, 0 draws) In 29 wins, avg winning margin was 10.10 points and game length 29.72 moves. Overall avg game length 29.14 moves. YOUR HANDLE: yura YOUR NAME: Fumitaka Yura YOUR ENTRY: TARO 20. nout scored 54   (27 wins, 37 losses, 0 draws) In 27 wins, avg winning margin was 8.85 points and game length 31.22 moves. Overall avg game length 29.94 moves. YOUR HANDLE: Tominator YOUR NAME: Tom Muylle YOUR ENTRY: nout Where? Belgium What? Student (computer science, medical imaging) Who? Coming from qbasic, then java, python is always a challenge. Too bad I lost interest after a month. Program Name? Nout are the first four letters of some python function. It sounded okay. I chose it at random really. Approach My program solves minimax basically. It looked ahead either one or two or no levels (just evaluating one step I mean), depending on the number of lines already on the grid. It had no time control. The thing Im proud of (a bit) is the way I represented the lines internally. I thought about storing letters in a matrix, like A meaning the box is closed above, and B closed above and right and so on. I quickly threw that idea out because it would make my lookahead algo complicated. Instead I stored in a matrix how many lines were around it. 4 means the box is surrounded, and it is filled. I also stored the lines separately in a list. When it was my turn, my algo brute-forcedly tried every possible line that could be added, and of course stopped a line along a path where there was overlap with an existing line. After the valid lines were generated, they were given to a recursive loop (the minimax) that weighed the board before and after the line was added (I used something like (nr of matrix cells with 4 * 12) + (nr[3] * -6) + (nr[2] * 2) + {nr[1] * -1)). I gave cells with a 4 high value, and the ones with 3 a bad score (because leaving those meant the opponent could score on the next move). After the weighting, I calculated the movescore (score_after - score_before). If this was higher than the highest movescore already found, this move was kept. Now the line was removed from the board again and the next was tried. This loop scored all possible moves. In the next loop, the high scored moves were applied to the board again. If a next-level search was needed, the algorithm recursed, which means it generated all possible moves, scored them all and continued only with the highest scored. Depending on the recursion depth, the best score from the recursion was added or subtracted from the movescore on the parent level. Then the line was removed and the next was tried. I hope that this is a bit clear. A big assumption by me was that the selection to keep a line based on its immediate score was okay to do. The algorithm was a lot faster when I put this in, and it still seems to do okay. Try Again? Not use python, look at the time. Test a bit more with different weights and guesses for recursion depth. Make it win instead of barely winning/losing. 21. mondrian scored 54   (27 wins, 37 losses, 0 draws) In 27 wins, avg winning margin was 8.67 points and game length 30.11 moves. Overall avg game length 28.61 moves. YOUR HANDLE: MBCook YOUR NAME: Michael Cook YOUR ENTRY: mondrian Where? Kansas, USA What? Student in my final term of college, about to get a BS in CIS. Who? Spend much of my time programming. You can check out my website at http://www.foobarsoft.com. Program Name? When I saw this contest I immediately thought of those famous paintings that just have black lines making boxes filled with white, blue, red, and yellow. After a little research I found the name of the artist who painted them was Piet Mondrian, so I used his last name for the name of my entry. Approach Ive been itching to try AI or a genetic algorithm for a long time, so I took this as my chance. After creating the basic parts (logic to keep the boards for me, generate a list of all legal moves, etc) I created a scoring mechanism. I programmed it in C for speed, simplicity, and practice; and was amazed at how well it ended up doing in the systests. Here is how things work: Each possible move is played and a board is thus generated. These boards are run through a scoring algorithm that multiplies some calculations by weights. The results of this are added to produce a score for the board. The highest move leading to the highest rated board is taken (randomly among tying entries if necessary). The scoring mechanism takes the following things into account: 1. The number of squares with no sides (as a percent) 2. The number of squares with one side (as a percent) 3. The number of squares with two sides (as a percent) 4. The number of squares with three sides (as a percent) 5. The length of the line that was played (scaled so the max length is 1, half the max is .5, etc) 6. Our winning margin (our squares - his squares, normalized) Each is given a weight between 1 and -1. When you add it all up, the possible scores range between -6 and 6, with 6 being the best. There are a few short circuit checks so that any move which is a win in that turn is taken (it is given a score of 7, guaranteeing its selection), and if there is only one possible move, we dont bother to score it. I created a second program that would call the first and run the tournaments for me, and these were later merged for speed reasons (forking takes a LONG time on OS X). This program could also generate random DNA and "breed" the DNA. So I generated 99 bits of DNA (plus one based on my own play style for a total of 100) and ran the 100x100 tournament. The DNA was then sorted based on the points received. I dont seem to have written down details of what happened next, so here is the best I can do from memory. The top 10 bits of DNA are carried in to the next round straight. Then each of the top 10 is bred with 5 other top 10 entries, and 2 top 100 entries. This produces 70 new bits of DNA, plus the top 10 for a total of 80. The other 20 are newly randomly generated. Once this is done, we have 100 new entries and we can do it again. Mixing DNA is a simple crossover, where each "base pair" (weight) is randomly selected from one of the two parent DNA bits, then a random mutation may or may not be applied afterwards. This seemed to work pretty well. At first things didnt go so well, but after running about 45 tourneys on various random boards a clear winner emerged (which was copied almost verbatim into every DNA slot). It is this DNA that was embedded in my final entry. Here are its weights: 0.984120 (blank) 0.576126 (one) 0.315090 (two) -0.972065 (three) 0.020435 (line length) 0.660055 (margin) You wouldnt think blank squares would be good, but apparently they are. There is a VERY strong bias AGAINST squares with 3 sides, which does make sense. Line length has very little impact apparently. As for other details, my program was rather simple. The board was just a one dimensional array of integers that I used to hold a bit mask of each box (which walls were filled in, and which empty). Try Again? If I had it to do again, I would have spent more time. I had to spend a ton of time on my senior project for school so I havent touched it since March 25th. I would have liked to restructure the weights to see if that would have worked better, as well search one or two levels deep. My program is so fast (one of the fastest if not the fastest) that I would have easily been able to do that and I think it would have helped quite a bit. I would have also liked to divide it up. One one of the systests I was at the top of the rankings, but on the one with a small board my entry didnt do very well. I think giving it three sets of DNA (one to use on small boards, one to use on medium boards, and one to use on large boards) would have allowed me to fix this error (as well as the specialization probably would have produced better results). Still, it was very fun and Im glad I got to play with a genetic algorithm. I learned quite a bit. 22. KT scored 54   (27 wins, 37 losses, 0 draws) In 27 wins, avg winning margin was 9.22 points and game length 30.41 moves. Overall avg game length 29.80 moves. YOUR HANDLE: BobBlack YOUR NAME: Steve Trevorrow YOUR ENTRY: KT 23. fairlyodd scored 52   (26 wins, 38 losses, 0 draws) In 26 wins, avg winning margin was 8.04 points and game length 29.88 moves. Overall avg game length 29.34 moves. YOUR HANDLE: daniel_t YOUR NAME: Daniel Tartaglia YOUR ENTRY: fairlyodd Where? Tampa Florida 34683 What? Video game programmer. I work for Gorilla Systems Corp which primarilly does contract work for Disney Interactive and Mettel Interactive. I am currently working on a Buena Vista Games title for the Nintendo DS. Who? I love sailing. My favorite movie is Memento. I have a lovely wife. My favorite board game is Magic Realm. My favorite newsgroups are ones on program methodologies and philosophy. Program Name? Becaue the algorithm it uses tracks the number of "odd" squares. IE the number of squares that have one or three sides filled in. I thought this was a farily odd thing to do so the name is a double entendre. Approach My first version (which also seemed to fared best in the standings :-) did no look ahead and determined the best move by attempting to reduce the number of "odd squares" as much as possible. An "odd square" is one which has one or three lines filled in. The idea being that if my opponent is never given a board with squares that have three lines filled in, he cant close the box and get a point. I later moved to a scoring system on the boxes because I saw my program handing over boxes to the opponent if it could create fewer "odd squares" overall. The scoring system didnt work so well on its own, so I went with a combination that used "odd squares" and then scored the moves that were equal in the "odd square" metric. Later I added a look ahead but the time alloted only gave me room for 4 move looks. Try Again? Id learn how to play the game first. :-) I cant beat my own program, yet I suspect that I will not win the contest. Im hoping to at least come in the middle of the pack. 24. LinearBee scored 50   (25 wins, 39 losses, 0 draws) In 25 wins, avg winning margin was 9.00 points and game length 29.28 moves. Overall avg game length 29.03 moves. YOUR HANDLE: SpaceDog YOUR NAME: Colin Cameron YOUR ENTRY: LinearBee Where? Edinburgh, Scotland What? Software Engineer, working in Telecoms Who? Im a bored software engineer, thats about it. Program Name? I was stuck for inspiration and I liked the pun Approach It just examines each possible move and gives it a score. Moves that create boxes get points, moves that leave boxes lose points. Its far from perfect because a move that leaves 3 possible boxes that can be completed in the opponents move gets the same penalty as a move that leaves 3 disconnected boxes that cant be completed. The lack of consideration past the next move really harms it against good opponents. Try Again? I didnt have time to implement that second version, which would have used the same system but with a scoring system that looked ahead for a second move. 25. BoxingDay scored 44   (22 wins, 42 losses, 0 draws) In 22 wins, avg winning margin was 11.41 points and game length 30.36 moves. Overall avg game length 29.30 moves. YOUR HANDLE: kweinert YOUR NAME: Ken Weinert YOUR ENTRY: BoxingDay Where? Westminster, CO, USA What? Programmer/Analyst Who? My first computer I had to solder together and then program using the switches on the front panel. Ive done paper tape, Hollerith cards, ... I enjoy programming, doing it for both work and leisure. Program Name? Seemed like a nice pun. Its supposed to create boxes and win a present :) Approach Basically I iterate through the playing field looking for boxes with 3 sides completed and create a list of endpoints that would complete the box. Then I sort the lines, consolidating any adjacent/sequential ones to create the most boxes in one line. If no boxes can be completed then I look for empty boxes so I add the first line - or the 2nd line if necessary and the 3rd line only I cant avoid it. No lookahead and I did not use any strategies from the original game. Try Again? A bit more analysis and perhaps some lookahead. I think I could have been a bit smarter about looking for places to play when trying to avoid completing boxes. 26. Agent5 scored 44   (22 wins, 42 losses, 0 draws) In 22 wins, avg winning margin was 8.82 points and game length 27.73 moves. Overall avg game length 21.05 moves. YOUR HANDLE: Agent_Smith YOUR NAME: Agent Smith YOUR ENTRY: Agent5 27. Dragon scored 40   (20 wins, 44 losses, 0 draws) In 20 wins, avg winning margin was 10.65 points and game length 26.30 moves. Overall avg game length 27.00 moves. YOUR HANDLE: freud YOUR NAME: Jeffrey Rainy YOUR ENTRY: Dragon Where? Vancouver, Canada What? Software Engineer Who? Programming video games for a living, wishing for some more algorithmics in my day-to-day work. Program Name? I was hoping to optimize my player for endgame where long chains of unconnected squares remain. In some other game (Go) some similar patterns are called Dragons. Approach My entry is a very incomplete program. I have, in another program, a good solution for endgames, provided you can only play lines one segment long. I was hoping I could make a program that forces the endgame into positions where there isnt that many longer moves possible. Well, it didnt work, and I didnt get to finish it. Try Again? No idea. :-) 28. labrat scored 24   (12 wins, 52 losses, 0 draws) In 12 wins, avg winning margin was 15.50 points and game length 28.67 moves. Overall avg game length 26.08 moves. YOUR HANDLE: daveymatey YOUR NAME: David Cox YOUR ENTRY: labrat 29. stef_first_sol scored 20   (10 wins, 54 losses, 0 draws) In 10 wins, avg winning margin was 12.40 points and game length 25.00 moves. Overall avg game length 19.81 moves. YOUR HANDLE: stefan.ciobaca YOUR NAME: Stefan Ciobaca YOUR ENTRY: stef_first_sol 30. gordon scored 18   (9 wins, 55 losses, 0 draws) In 9 wins, avg winning margin was 2.22 points and game length 1.22 moves. Overall avg game length 7.70 moves. YOUR HANDLE: Jax YOUR NAME: Olivier Jacquet YOUR ENTRY: gordon 31. LineInTheSandbox scored 14   (7 wins, 57 losses, 0 draws) In 7 wins, avg winning margin was 15.14 points and game length 17.57 moves. Overall avg game length 23.97 moves. YOUR HANDLE: Zaph YOUR NAME: Kevin Burfitt YOUR ENTRY: LineInTheSandbox 32. Tamtam scored 2   (1 wins, 63 losses, 0 draws) In 1 wins, avg winning margin was 1.00 points and game length 0.00 moves. Overall avg game length -0.98 moves. YOUR HANDLE: hnawar YOUR NAME: Hatem Nawar YOUR ENTRY: Tamtam 33. NosyNono2 scored 2   (1 wins, 63 losses, 0 draws) In 1 wins, avg winning margin was 1.00 points and game length 0.00 moves. Overall avg game length -0.98 moves. YOUR HANDLE: nederhoed YOUR NAME: Robert-Reinder Nederhoed YOUR ENTRY: NosyNono2 Where? The Hague, The Netherlands What? Web Developer Who? Male, 30yo, outgoing, friendly Program Name? Well my solution tends to stick its nose deep onto possible solutions, hence the Nosy. And then still tends to come up with sub-optimal moves, hence the Nono. And this is the little brother of a previous NosyNono. Approach It looks ahead about 3 moves. No strategies from the original game. Try Again? Take more time. Start more early. I ran into some trouble getting my Python program running in the sandbox. Next contest wont be a problem!

	The POTM is unsponsored and just for fun.       Saturday 03:03:16 AM      Copyright © 2004-6 - Fred Hicinbothem