|^^^\ /^^^\ ^^^^^ /^^^ | \ / \ | / | \ | | | \ | | | | | ^^^^\ | / \ / | | | / \ / | / ^^^^^ ^^^ ^^^^ |\ | | \ | | | | | \ | | \ | | \| |^^^\ /^^^\ \ / |^^^^ /^^^ | | / \ \ / | / | / | | \/ | \ |^^^^\ | | /\ |^^^ ^^^^\ | | \ / / \ | | | / \ / / \ | / ^^^^^ ^^^ ^^^^ ^^^^ version 1.1 December 12, 2003 by Chris Calabro ---------------------------------------------------- INTRODUCTION Thanks for downloading dotsnboxes! This is the familiar game that many people play on a napkin when bored at a restaurant. Most people are already familiar with this game so let's get right to how the program works. ---------------------------------------------------- INSTALLATION Unzip dnb.zip somewhere. Make sure that dotsnboxes.ini and log.txt are both writable (ie not readonly). Start the program by running dotsnboxes.exe. ---------------------------------------------------- CONTROLS ESC to exit. LEFT CLICK on an untaken edge to take that edge. Edges are colored according to who takes them. The last move played will flash. F1 to open/close the menu. All game controls can be accessed from the menu. In addition, all of their hotkeys are listed there, so you don't need to memorize them. You can also alter the game board size from the menu by left clicking on the grid and then closing the menu. UP, DOWN, ENTER to operate the menu. N to start a new game. P to pause the game. The CPU player can't think when paused. This is useful because when you try to go back by a few moves, the CPU may play so fast that it replays the move you just tried to undo. LEFT to go back by 1 move. You can go all the way back to the 1st move of the game by using this repeatedly. S to ask the CPU to suggest a move for you. The suggestion will appear as a flashing green edge. 1 to toggle player 1 between Human and CPU. 2 to toggle player 2 between Human and CPU. You can toggle at any point in the game. You may want to start off with Human vs. Human to set up a situation, then change one of the players to CPU to see how well it plays from then on. You may also want to try CPU vs. CPU just to watch two equal strength players play really fast! F12 to show/hide frames per second - very useful when bragging about how powerful your computer is. ---------------------------------------------------- INITIALIZATION FILE dotsnboxes initially reads dotsnboxes.ini to get the default players, game size, etc. Read the comments in dotsnboxes.ini if you wish to change any of this. ---------------------------------------------------- SYSTEM REQUIREMENTS This program should work very well on a 500MHz PIII, as this is on what it was developed, but it should not require anywhere near this much power. The video card must support 640x480x24 resolution. I tested this on Windows XP, but it should work on other DOS platforms. Previous versions worked on Windows 98 and Me and this version may still. ---------------------------------------------------- RULES OF THE GAME Dots-and-boxes is a 2 player game played on a matrix of dots. A 2x2 submatrix of dots is called a box. 2 dots, say at (i, j) and (k, l), are adjacent iff |i - k| + |j - l| = 1. The 2 players alternate turns; passing is not allowed. An edge of a box is a pair of its adjacent dots. All edges are initially untaken. A player makes a move by taking an untaken edge. A box is completed iff all 4 of its edges are taken. If a player completes a box on his current move, he captures that box and gets another move. His turn ends when he takes an edge without taking a box, or when no move is available. Notice how move and turn are distinguished. The game ends when no move is available. The winner is whoever has claimed the most boxes. Ties are possible. ---------------------------------------------------- HOW DO I GET GOOD? Most people play dots-n-boxes by looking for a move that gives away as few boxes as possible or, even better, takes as many as possible. This naive approach will not work against someone who knows what he is doing. Good strategies can be found in the book Winning Ways by Conway, Berlekamp, and Guy. Included in this release are several essays on game strategy and development of the CPU game playing algorithm used in the program. They are not in the same format since I wrote them at different times. ---------------------------------------------------- CPU PLAYING STRENGTH The CPU player should stomp flat anyone who plays using the naive strategy. The precise strength can be adjusted by changing max_move_depth, max_rg_depth, and max_time in dotsnboxes.ini. Note that max_move_depth is _not_ how many moves deep the CPU player can see, it is more like (but not exactly) the maximum size of a certain internal evaluation stack. Each of these 3 parameters obeys a simple rule: larger values increase CPU playing strength but may cause it to take longer to make a move. The CPU player has many small weaknesses, especially when playing on small boards. Exploiting these weaknesses on large boards almost certainly will not result in a victory over the CPU. But the CPU player, and indeed any player, has a weakness even on large boards: on any board the sum of whose dimensions is odd there is a 'middle' edge that can be played by player 1. Subsequent moves by player 1 should mimic the last move made by player 2 using an odd symmetry about the middle edge (eg if player 2 takes the horizontal bottom right edge, player 1 should take the horizontal top left edge). Player 1 should abandon this doppelganger strategy as soon as player 2 gives away the 1st chain of at least 3 boxes (which almost always happens when this strategy is employed), at which point it is nearly assured that player 1 has a forced win. It is possible to counter the doppelganger strategy in much the same way that it is defeated in the game go. But rather than countering proactively, the CPU counters by making a careful sacrifice move in an attempt to create a game situation that is too complex to analyze and such that the wrong response can be brutally exploited. My goal was to make a CPU player so strong that on large boards, no human could consistently defeat it. I failed, but just try to find such a strategy! ---------------------------------------------------- THANKS I made dotsnboxes "by myself", but like Newton's works, it would not have been possible without some big shoulders to stand on. So let me thank some people. the www.allegro.cc community for all of their expert programming knowledge, especially bdavis for his help with libamp. DJ Delorie for a great c++ compiler. Go get it at http://www.delorie.com/djgpp/ Shawn Hargreaves for the allegro game programming library. go get it at http://www.talula.demon.co.uk/allegro/ David Aranda Alonso for the text border library. Go get it at http://www.geocities.com/SiliconValley/Platform/7903 Doug Eleveld for the allegttf true type font library. Go get it at http://huizen.dds.nl/~deleveld/index.htm Eric Vannier and IJG for the libjpeg library. Franz Miklis for the background. ---------------------------------------------------- VERSION HISTORY 1.1 ported to Windows XP shrank executable by 1mb updated some libraries 1.0 initial release ---------------------------------------------------- CONTACT INFO Report bugs, serious flaws in the CPU playing algorithm, or just if you like the game to ccalabro@cs.ucsd.edu. ---------------------------------------------------- COPYRIGHT I claim this game in the name of myself! Don't 1) sell it, 2) pretend that you created it, or 3) change it slightly and then do one of the above. I don't claim that the music nor graphics are mine, just the program. Distribute it without charging others and enjoy!