Hi, I'm working on adding Dots and Boxes to Vying Games ( vying.org). I'm still very new to this game–I've only played a handful of games with x-rated here on LG.

I'll probably get it wrapped up sometime this month, but before I get too far along with it, I thought it'd be a good idea to ask if there are any features a new Dots and Boxes site should have?

I'm planning on 6x6, is this a good grid size?

i think wccanard gave some arguments saying 5x5 was the best size. I hadn't enough knoweledge to understand him, though :)

5x5 boxes, 6x6 dots, is best.

Basically, 5x5 dots is 'solved', and 7x7 dots and higher tend have higher endgame values, which means that more of the time you just want to win the long chain battle at almost any cost.

I think 5x5 boxes, i.e. 6x6 dots is the best. I suspect Gregorio was talking about boxes and not dots.

Yes, I had some kind of argument was to why 6x6 was the one worth bothering with on a game site. Phil has summarised it correctly. I can give more details.

Let me stick to square boards, just for aesthetic reasons, and when I say

t x t, I mean t *boxes* by t *boxes*.

2x2 is just like a harder version of 0s and Xs; you just learn the winning lines and that's it.

3x3 is even easier—there's a basic “strategy” [P2 forces a chain through the middle of the board and uses a standard trick to ensure it's the only one, and then learns to recognise the few special cases where this trick doesn't work]

4x4 is computer-solved [it's a draw]. I know people who seem to play essentially perfectly, and in real time too; there are people who hang out at Yahoo Games that can play a ferociously good 4x4—*much* better than me, that's for sure. Note: 4x4 (boxes) is the standard size for Yahoo dots. Being P1 is a huge advantage on 4x4; P2 has to really fight for a draw and know what he's doing. The main problem with 4x4 is that there are easily-available programs that play the game perfectly and in real time.

5x5 is what we play here and at jijbent. I don't think this is a coincidence. I think 5x5 has got everything. It's not just a chain battle and it's too big for one to be able to just “learn the standard endgames”; you can play endgame theory on 4x4 by just knowing about 10-20 maxims of the form “two 4-chains and a quad is worth 0” etc. There are far more complicated endgames in 5x5 and you have to be able to count them properly which, although not difficult, most people seem to find hard to do: I should think that all of div 1 and about half the people in div 2 can count accurately, plus possible random upcoming youngsters. So it's counting, chain battle, and different games have different flavours (1-chain game, multi-chain game, one loop, two or more loops) making playing a lot interesting; you don't know whether you'll be in a chain battle or counting up the short chains to see if it's 13-12 or 12-13. 5x5 rocks. 5x5 boxes, that is. Computers can't play anywhere near perfectly; it might take a day of CPU time to analyse a position perfectly after 15 or so moves have been played and by that time a human can have beaten a rabbit anyway. It is certainly not uncommon for humans to be playing perfectly from move 20-22 or so.

So now why go further? 6x6 is playable, but has an even number of boxes which is a bit unsatisfactory. And 7x7 is the standard board at Richard's PBEM server but it takes so long to play—twice as long, in fact, and it's not clear that you've gained much at all. And who would play a game where about the first 5 moves the players made would be essentially random? The only thing you think is “don't make the 3rd side of a box”! A novice could play 5 random moves against a grandmaster and I bet that if computers could analyse the resulting position, there would be a 50-50 chance that the novice was winning. What sort of a game is that?? Wouldn't happen in go, right?! Even bigger but much less random.

Features: the jijbent crowd would ask for a java applet enabling you to do analysis; people might want the box where you can save your secret notes. There are two other variants of dots and boxes—don't go with them. The first is “you must take if you can” and this game is basically solved. The second is “you don't get an extra turn after getting a box” and this is just an easy parity game too; far far too simple to completely master, so I've heard. Finally I guess one could consider implementing nimdots, i.e. dots and boxes but the winner is the person who takes the *last* box, rather than the *most* boxes. The problem with this is that there are again publically available computer programs that play this very very well indeed and which, I suspect, could easily beat a human in real time. You could just make up some kooky board size e.g. play on 1x15, but there are serious risks to this: there might be easy strategies involving reflection of moves; I've not thought about it. Certainly on 1 x even the first player seems to be able to guarantee a draw by playing in the middle and then copying; 5x5 boxes has got a proven track record, there is no reflection trick.

That's probably enough from me :-)

Wow, thanks all. Especially wcc, that was very informative!

I was referring to 6x6 dots (aka 5x5 boxes), as the way it's programmed now (though the dimensions are the easiest thing to play with). I'll keep it at that size since it seems to be the most established. I think variations could be added later, and nimdots sounds like the most interesting (though it's too bad if computers have taken the fun out of it).

Would something completely out there like random starting positions be of interest? Not as the main variation, obviously, but as something different to play? Perhaps go to 6x6 boxes with an odd number of pre-completed neutral boxes (leaving an odd number of boxes to compete for)?

I'm going to work on analysis, not just for dots and boxes, but for all the games. At least, manual analysis (try out various sequences of moves by hand)… Accurate computer analysis kind of goes hand in hand with the strength of whatever bots I can put together. Since I don't know dots and boxes strategy well yet, the bots will probably start out quite weak. Though I find AI programming fascinating, my immediate goal is that the bots provide an easy opponent for new players to learn the rules against.

Thanks again, everyone. I'll keep an eye on this thread and post back when I'm done with Dots and Boxes.

For a variation - how about dots and boxes on Ingo's new grid tiled with squares of different sizes?

Do you have a link for the grid of different sized squares, Phil?

I assume inner dots are removed to form larger squares. So, for example, if only one dot were removed it'd form a single box the size of 2x2 boxes? It'd then take 8 lines to complete the larger box and the player to complete it would be awarded 4 points, right?

I like that idea. It'd be easy to creating a grid with random dots removed. Or, does Ingo suggest a specific static grid of dots?

http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=140&topic=88

I like the idea of a grid with a few missing dots.

A 6x6 boxes with 6 dots missing would need the same amount of moves as 5x5 boxes game.

The “risk” with playing funny variants is that they won't be as popular, I guess. At Richard's PBEM server the standard board size is 7x7 but to ensure that the game doesn't go on too long the computer throws about 24 random lines down to get the game going. If you start a game there but say when starting it that you want to play 5x5 (boxes—I'm always talking about boxes when I give dimensions) then it throws in a bunch of random lines anyway, and michael once told me that sometimes it throws them in such a way that a human can analyse the game from the starting position. I guess you don't want this to happen. My guess is that for a website like vying or here you want to ensure that you don't work to put in place a game which is “trivial” in some way, so you have to be careful if you come up with some “interesting” idea—you need to make sure that there is not a trick for 1 player to get something for nothing. For example if you made the middle box a neutral box and let players battle it out on the remaining 24 squares then P2 can always ensure at least a draw just by some kind of copying moves with 180 degree rotation trick and you surely don't want that. The thing about vanilla 5x5 dots and boxes is that it is absolutely tried and tested, it doesn't go on too long, it's popular here and at jijbent, you can't get beaten by a rabbit with a computer program (although you can get beaten by an expert with a computer program, although this is presumably true for almost any game) and there are no daft tricks to ensure that one player can guarantee at least a draw by doing something mindless.

If you wanted more than just vanilla 5x5, I would say that 4x4 wouldn't be a bad alternative. It's still a non-trivial game even though it has the disadvantages that (1) there is plenty of computer-generated information on it (there's even a huge computer-generated perfect opening book out there, so it's really very easy to cheat) and (2) that it can be a draw (and indeed is a draw with best play).

A crazy alternative would be what Berlekamp calls “The Swedish Game”, where you start with a rectangular grid but with the outer boundary drawn in! This makes for a very very different game because no chain ever can run to the “ground” (the outside of the board) and it would really change the nature of the game. Again a problem will be that it I'm almost certain that it would not be hard to get a computer to play the 5x5 Swedish game perfectly: the position is well within the boundaries of what a computer can do. If you go for a Swedish game then perhaps 7x7 would be better; there are then…erm…84(?) free lines, which makes the game only a bit longer than the traditional 5x5.

AI: I would be interested in giving you my input on how I think a computer AI might work. I have had some ideas about this but don't have either the time or the skills to write a program myself. You might also want to talk to the guy who wrote knox, a computer program which used to play here.

I remember reading something about some variant in which completing a rectangle of any size gives you all the boxes inside. I haven't played it yet though, and there might be some perfect strategy

@Phil: Thanks that's a pretty cool looking board.

@Yper: With math that works out that nicely, I think I'd have to do the “missing dots” variation with those dimensions. I won't do it immediately, I usually prefer to do variations that are at least a little established, but it sounds like too much fun not to try.

@wcc: I certainly agree there's risk in little played variations (or completely untested variations, for that matter). Once players figure out how to exploit a weakness in the rules of a game it does become much less fun to play. Although sometimes it's fun to play a rare game / variation just to discover how it works and if it has shortcomings or not.

I'm mostly interested in Dots and Boxes variations because I like code reuse and

a fair amount of new code will go into the boxes UI. To be able to reuse that UI for a variation or two at some point in the future would be nice.

That and I enjoy discussions like these. : ))

The Swedish Game sounds like a nice variation too. Much more simple to code than even the missing dots variation, so I'll probably give it a shot. (I like the fact that it has a name, and a little history, even if it might not be too well known)

I'd welcome any AI advice, too.

@flip: That's another interesting variation. Would the completed rectangle have to be empty? (eg, no interior lines or completed boxes?)

The “problem” with writing a *basic* AI (i.e. under 100 lines of code which does some basic analysis of some sort and then makes a move based on that analysis) is that if a human actually knows what the bot is doing then the human can always win. E.g. you might want to code a bot that always wins the chain battle. Then a human just makes some quads and lets the bot sacrifice and wins. A “good” bot will know some opening theory and will do a brute force analysis of the game when about (at most) 20-22 moves have gone past, I should think. That would make him a tough opponent. Also I think that if you write a bot to play perfectly from move x (and presumably *whatever* bot you write, you'll have to write a function of the form “analyse this game completely to the end unless you find that it will take too long to do so”) then there actually might be a strong argument to let it play completely randomly for the first few moves—this is hard for a human to play against and usually leads to complex positions. Dots and boxes isn't at all like go; you can play 5 random moves against an expert (starting from an empty grid) and, especially if the expert doesn't know that you're doing this, you might find that you're still not losing. On the other hand, one random move after move 25 or so and you might well be sunk; that's why you need to analyse perfectly from some point onwards.

that sounds like a nice bet: 100 lines of code that a human cannot always win.

You could surely write a very simple brute force recursive algorithm that plays perfectly but takes months to make a move in under 100 lines of code. Don't you think? Very inefficient but would always win. Obviously I'm not going to count all the lines needed for the GUI and stuff. But for the core move algorithm, I bet that even “play 10 moves at random subject to making boxes if possible and not giving boxes away ever”, followed by “brute force analysis via simple minimax” (not even alpha-beta!) would fit into 100 lines. I wouldn't be surprised if you could even squeeze alpha-beta into it if you were someone like Phil, who is of course famed for his squeezing-code-into-as-little-space-as-possible abilities!

Heh. That reminds me of a funny contest we had at the office a few years back. We had a contest who could write the better Othello (Reversi) program in MatLab. However, there were two restrictions: 1) No more than 2 kb code and 2) the program had 2 seconds for the entire game (on a specified computer). It was rather fun, although the code became completely unreadable :-)

I think 100 lines of code is reasonable for an entire bot. (Although, as with any program, one has to draw the line as to what is library code and what is not)

My minimax is 28 lines. The alphabeta implementation weighs in at 59 (with optional support for move ordering and forward pruning). That leaves some boilerplate and an eval function. A simple score based eval function would really only need a couple lines of code. The question would be how many lines would a sophisticated eval function be?

How slow can the bot run would also be a point of contention. As wcc says, if I can let it run for months per turn, I think it should be nearly unbeatable… Of course, I'll limit it to less than 1 second per turn and it will likely be very beatable as a result. :/

Oh, and thanks for the AI advice wcc. I like the idea of making the first 5 or so moves random. Saves the trouble of developing an opening book. It'll be interesting to see how deeply I can search in the endgame. It'll be interesting to see what effect move ordering will have on the cutoffs. I would think that putting any move that completes a box first would be very effective. But I wonder if parity should also be taken into account when move ordering (eg, maybe a double cross move should be considered first if parity dictates?)

Let me tell you more of what I know.

Because dots and boxes involves filling in lines in a fixed grid, one can model the game tree as a tree in the usual way but one can do something better: one can simply enumerate the actual possible future positions reachable from a given position and then compute the value of each of these e.g. via minimax. This cuts the search space down from n! to 2^n (with n lines yet to be drawn) which is a big saving on time. This is an observation of David Wilson. It's a *theorem* that if there's a move that takes an isolated box then you should take that box. It's also a theorem that you should take all but two of any long chain, and then stop to think about whether to take the last 2, and similarly all but 4 of every loop. The big problem with dots and boxes is that, as far as I know, no good evaluation function is known. The evaluation function I try and use when playing is: “if there are no loops and I've won the chain battle then I'm OK; I don't need to consider lines where he opens a chain or a loop and I have to make the all-but-two decision when I am not losing on boxes; otherwise just play out plausible lines and count”. The game is very different to chess or go in this respect. In a game of go someone playing randomly will have lost against a good player after 5 moves each. The same is not true in dots and boxes. I sort of have an algorithm for playing endgames but at the end of the day I don't know any eval function that even comes *close* to “just play it out and count it out”. You should ask the knox dude what he did.

While I may occasionally obsess about making things small (obfuscated C code, for example), I generally have an extremely obvious and one might even say verbose coding style. RoRoRo is several thousand lines of perl, and game-play-wise that only includes a rudimentary EinStein and dvonn placement.

phil@made:golem$ wc golem*.p?   3648  10866 130809 golembot.pl   490   1026  16620 golemconsole.pl   472   1256  15066 golemcore.pm   489   1485  20719 golemmsgs.pm  5099  14633 183214 total

GWG is 700 more lines of perl (could be reduced, there's lots of duplication). The dvonn engines and the GWG grid search utility are both over 1000 lines of C, and the new EinStein engine is about 500 lines of C.

phil@made:golem$ wc golemempathy.pm 267  654 7765 golemempathy.pm

Highly redundant code, lots of copy-paste, but sod it, I got the bot playing empathy in less than 3 hours, I'm allowed to cut corners!

In addition to the Swedish game, Berlekamp has an Icelandic version – half of the border is filled in, instead of all of the border. Other variants include playing the game on the torus or cylinder. I think that I've only played one game of each of these. They are very different in flavor, as you can't ground chains as easily (or at all).

Also, I think that I've seen a version played on a hex grid. The sixth side of a box wins the point….

I computer-analysed the 5x5 Swedish game; it only took a couple of days, so it's probably “not hard enough” for a serious turns-based site. It's a 14-11 win to P2.

Every move on the board is worth the same, in fact; all first moves are equally bad for P1.

I don't think I'd have a good feeling at all for playing on a torus, or playing the Swedish game: I have a gut feeling about where chains will form on a normal board, and this would be thrown completely out of the window on a board with no edges.

Do you think the P2 advantage will hold for 6x6 (boxes) and 7x7 (boxes) for the Swedish game? I don't have enough experience with dots and boxes to have a feel for how grid size changes strategy to extrapolate.

What about a “corridor” game, with only 2 opposite sides already filled in?

A 2x12 or 3x10 corridor might be playable.

@Eric: I don't know anything about 6x6 Swedish or 7x7 Swedish. I don't think one can extrapolate given the facts about 5x5. My gut feeling is that perhaps 5x5 Swedish is a P2 win because the board is so enclosed that only one chain gets to form. With a bigger board it might not be true that 1 chain forms but perhaps e.g. 2 chains form naturally instead. The reason the usual 5x5 game works so well is that there is just enough room for 2.5 chains :-) so typically one player is working this number down to 2 and the other one up to 3.

@yper: one key question is whether there's a rotation trick. Can P2 play a 2x12 corridor just by copying (180 degree rotation)? Does this ensure a draw for him? If so then this wouldn't be great. Actually I don't think the strategy works on 2x12, or if it does then it will be delicate to pull it off, so maybe you're OK. The nice thing about 5x5 is that if P2 copies then after a while P1 sacrifices the middle box and then P1 copies and wins. But this can't happen in a well-played game because P2 has to “set the scene” and will then lose! Copying is very delicate though; it doesn't work on a 2x2 board, for example.

I don't think a copy strategy would work.

The first player would sacrifice the top left corner and the second player would have to sacrifice the bottom right box (following the copy strategy).

Then the first would sacrifice the top second left box and then the second player would sacrifice the bottom second right box, etc…

When the first player sacrifices the top middle box, one chain will have been created and the second player loses by 18-6.

Would you have the guts to sacrifice a box on your 2nd move, given that your opponent might not copy? :-)

How about P1 starts building a “snake” in from one edge, wiggling up and down the corridor? If P2 copies then the two snakes meet in the middle and if I got it right P1 can sacrifice a box right at the end and make a 23-chain :-)

Dots and Boxes is now available (in beta) at Vying Games:

Dots and Boxes at Vying Games

The AI is pretty poor, but it's fairly responsive. I don't think it's too bad for a first try.

If you get a chance to try it, I'd love to get some feedback on the bot, the user interface, and of course, any bugs you might find!

Thanks,

Eric

It's good. The bots are too easy though. The site http://www.math.ucla.edu/~tom/Games/dots&boxes.html seems to have a harder bot. As always I like the presentation and the fact that the bot pauses makes it seem more real.

I tried the bot:

- it gave a box in the 3th turn to me without any reason.

- it doesn't know the chain-rule.. (I gave a quad away, and it rather took all boxes instead of dubblecross and win)

- it did a loony move

- it played in the longest chain first, so I didn't even needed to dubblecrosses to win.

Thanks for the feedback Norak and Karel!

I think I have some good ideas for improving the AI. A lot of it's shortcomings are due to lack of search depth. At least with respect to double cross moves. Sometimes it sees that they are appropriate and sometimes it doesn't get far enough to see them.

It definitely does not know the chain rule. I think a deep search would cure that too, but I'm wondering if a smarter eval function is possible. It'd be interesting to find an algorithm for identifying the chains, quads, etc, since the board is so stable.

I'm just learning dots and boxes (aside from very naive play as a child), so even in a short time I can see that there's much more that the bot could look at. The key is finding the right mixture of clever eval function and search depth.

The problem with Eric's situation is that he has imposed the constraint that he wants the bot to move quickly. I don't know any satisfactory eval function; I actually find it quite hard to formalise what I'm doing in the opening/middlegame of a game of dots and boxes. Definitely I'm initially trying to win the chain battle, but I am not trying to make chains, I'm trying to make regions that will surely either form chains or which will cost my opponent too much to sacrifice to stop them—except that “too much” is very hard to quantify; if there are quads then a 1 box sacrifice can be too much, but if there aren't then you might be able to sacrifice 5 boxes and still win easily. It's a definite mixture of eval and search depth but somehow it's very hard to quantify and I would have no idea how to write a program which attempted to mimic what I was doing. Another problem is that later on in the game, by move 18 or so, “there is no eval function”: if you want to win you have to analyse the game—because the best players are playing perfectly by around 21 moves in even the most complex positions.

I think the opening / middle game will be the hardest part to code to. I think the best option for the middle game is to find an eval function that can approximate the ending score from further out without actually having to search to the end. If such a beast exists.

I haven't played enough, but it seems like once chains start to take shape it's easy to see how they'd play out individually without a deep search. For example, there are X moves remaining before the chain is “saturated” and the next move will give away N boxes. Or, N-2 in the case of a double cross.

In othello, the game I've had the most success with (AI-wise), I use edge lookup tables to effectively extend the depth of the search. So, there's a table that says, an edge that looks like this or that is worth so many points in the end game. The table is precomputed either by having an expert assign values, or playing the edge out with a normal game tree search.

I'm wondering if it'd be possible to do something similar in a dots and boxes game…

Ultimately, I'm getting closer to adding bots that act like normal users. Where the existing bots are meant to be played in realtime, these bots would be tuned for turn-based play. This should allow for more difficult bots at the expense of playing a much slower game.

So (a) you're right, in that once the game is “saturated” (the commonly-used term for this is a “loony position”, because then every available move is a loony move in the sense of Berlekamp-Conway-Guy) then it's not hard to compute the value of the game. But (b) the problem is that well-played games frequently never become saturated because the player who is going to lose the chain battle wants to start the chain battle as soon as possible, before the chains have grown to their maximum length, and so starts opening chains early—this is called a pre-emptive sacrifice. And then it can get a bit delicate because your decisions on whether to keep control or not might change depending on how complete the chains are.

For saturated games you can do look-up; the table lengths are very very reasonable once you know a trick (long chains “add”).

Hi Eric, nice job even if we would like tougher bots…

Would it be hard to modify your bot to play percube's corridor game (2x11 or 2x12 is already interesting). I have the feeling it would be easier to make it stronger on these thin strips and to decide earlier where the chains will form.

Thanks again wcc! It's quite challenging to write AI for a game where one's still only a beginner. I'm an okay othello player and I've played some of the best players in the world, so I generally know what a good move looks like (although, I'm still surprised by unusual positions). With Dots there's still a very long ways to go…

@Carroll: It'd be pretty easy to experiment with different board sizes. I'm pretty sure the AI does not currently take board size into account. (Although, I'm playing around with having it copy it's opponent when playing second, and I think I the copycat code is hard coded to 5x5 boxes, so I'd have to change that or remove it for other board sizes).

If anyone is curious, the code is available at http://vying.org/dev/public The code for the game rules is in the “vying” project and the code for CapellaBot is in the “starbots” project.

did you improve it? i can't suddenly win her!!!

Nope. : ))

I worked a little yesterday on making the bot play “copycat” when it's the second player. But, I haven't really finished that work, yet, much less deployed.

I think the bot plays some situations much better than others. I really nerfed it before release because it would occasionally pause for 30 seconds to a minute to think. It still uses the “smarter” code just not as often throughout the game. So, a lot depends on how the game develops and whether the critical moments come at the right time.

yes, i crushed her again… it was a strange collapse of my brain or something :P

RoRoRo is now accepting challenges in Dots & Boxes. (And signing up for tournaments with the same protocol as for Dvonn (RTs, and MCs only as first entrant).)

It's pretty dumb at the moment, it basically knows not to play stupid moves, but does no lookahead at all. (And has no idea what a long chain battle is.) There are also a few code paths that I've not coded yet, so your game might suddenly halt (or even worse, RoRoRo might suddenly halt). If that happens, please message me.

Can RoRoRo register at vying games and then play a bazillion games against Eric's bot and we can see who wins?

Phil: what's a “stupid move”?

It won't throw away a box for no reason at all. (This also means that it won't do any sacrifices presently.) It won't open a 2 when there's a 1 available. In theory it won't double-cross when it should take all, and vice versa.

But deep down it doesn't even know what it's doing (it doesn't even keep score! :-\|)

If Eric will de-obfuscate the interface, then it might be possible to play on Vying games. Currently the interface is hidden somewhere inside a disgusting mess of AJAX about 99% of which is nothing to do with actually interfacing with the server. (Unlike LG, where it's immediately obvious how it gives information to you, and how you should give information back to it.)

“In theory it won't doublecross when it should take all and vice-versa”. Can I cause a memory overflow by making a loony move on e.g. move 8 or so?

No overflow, but it'll not respond to that. I've not programmed the code for early sacrifices yet. Much of it will be a copy-paste of the end-game code though. Hopefully I can get it coded within a day of someone putting him into that state.

I had thought a fair bit about how one might write an algorithm to play dots and boxes, but I was only ever thinking about code that was allowed to spend a day making a move. Both Eric and Phil's code seems to want to spend a few seconds making moves, at least most of the time, and this seems to me to be much much harder. The way I'm playing the opening and middlegame is to try and guess where the chains will form and to rig it so that the right number form, and that all the rest of the open spaces (where I don't want chains) turn into loops. The logic is that if you win the chain battle without sacrificing anything then you are in a good position—it's very hard to defend when your opponent hasn't sacrificed a single box. I don't know whether the above para is too “vague” for the idea of it to be implemented on a computer, but it's definitely what I am doing in the early stages of a game. For example I played RoRoRo yesterday and after about 10 moves I could see what looked like a stone cold 2 chains and I knew I was winning. If RoRoRo or CapellaBot could look at the position and think the same (“one at the top, one at the bottom, not much scope for much more”) and act accordingly (i.e. either push the game in that direction or away from that direction depending on which player they are) then they are on the way to becoming reasonable bots.

I wonder if one could “analyse” a position where 10 moves have been played thus: try 1000 10-move lines, each consisting of 10 random-subject-to-not-making-loony-moves-and-always-taking-free-boxes moves, and then chain count. Do this 1000 times and take the number that comes up the most: that's the number of chains that the position has. [Perhaps also count the loops: the more loops the less importance one attaches to this number.] And now play the move that pushes the chain count most in the direction you want from the stats you have. How does that sound?? Could one do that in a few seconds??

Dabble plays reasonably fast, and plays a decent game. As far as I know the AI from dabble was also used here as Knox and KnoxB.

Interesting idea wccanard. I would like to see it working.

Indeed, nice idea!

RoRoRo will evolve slowly, but I have no idea how I'll implement any kind of looking ahead yet. Random probing is not ruled out, but I certainly don't want to slow him down by a factor of 10000.

First things first - get him to at least acknowledge there is such a thing as a long chain battle, and be aware of which player he is. He's remendously basic currently.

What is Dabble's algorithm?

I thought that with Knox, what happened was that the guy who wrote it, wrote it and then let it play here and then thought about where its weak spots were and tried to make Knox better. I *think* that Knox knew something about chain-counting, and might even have known nim (didn't it occasionally compute nim-values??). On the other hand I *thought* that dabble just did a brute force alpha-beta search plus some sensible evaluation function.

I'm pretty sure I had a conversation with Knox' developer, where he told me he basically wrote an email to JP Grossman (the guy who wrote dabble) and asked him for his code. Then he made a couple of adjustments, perhaps added a nimcalculator. But in the end I didn't really feel much difference in playing Knox or Dabble, to me they looked like the same strength.

For more info about dabble u can go here:

http://www.mathstat.dal.ca/~jpg/dabble/

I just played dabble for the first time in my life. I agree, it's not a pushover! I played instinctively and fast and won 3-2 but for a computer playing so quickly (I put it on 10 secs per move) I think that I would have predicted a 5-0 whitewash before the game. I wonder what evaluation function it was using.

Michael: the web page you point me to seems to indicate that dabble is doing nothing more than alpha-beta. On the other hand I certainly felt that dabble was playing quickly and intelligently—an order of magnitude above Eric or Phil's program.

@Phil: I'd love to have RoRoRo play on Vying Games. The interface is actually pretty simple, but yes if you try to figure it out from the javascript… : (( On the production server the js is several files concatenated and mini-ized so that it'll load faster. And, yes, it contains tons of stuff that's unrelated to the actual interface with the server.

I've been planning on working on a simple bot interface, and it would be extra motivation to have RoRoRo as the target.

A few questions:

1. Would I be right to assume that RoRoRo can handle login and session cookies okay?

2. Moves are submitted by HTTP POST, I'd assume that too is not a problem?

3. Right now the positions are available as JSON, will RoRoRo have a problem parsing it? With very little effort I could provide the positions in YAML or some other format.

4. If parsing JSON is a problem, or mapping the server's representation of a position to RoRoRo's representation is a problem, I can also provide the sequence of moves. That way, you can have RoRoRo recreate the game by playing back the sequence. For dots and boxes, I label the dots 1 to 36, and represent the moves as strings like “1:2” (a line from dot 1 to dot 2).

I'll need to add something to get a list of game ids (unless you want to scrape them, but I think it'd be better to avoid scraping). I'll also have to add something to make accepting invites, joining tourneys, etc, easier for a bot.

Anyway, if you're interested I'll make this a priority. I don't think it'll take a lot of effort on my part to make the server bot friendly. : ))

Eric - you're a dude!

RoRoRo can login and handle cookes quite happily, and POST submission of moves.

RoRoRo's 'interfacing' engine is 100% perl, so I can probably hack together 20 lines of perl to parse simple JSON (or even use the CPAN module!). So probably no need for (4).

It will be interesting to see how tied to LG's interface RoRoRo is…. Currently the board parsing and game-play engine are very loosely coupled together, so it should be very easy to bolt in a different board parser.

I'm up for it!

Great! We should probably take this to email. I'll send you my address.

Thanks for the link to Dabble, michael… I'll take a look at it. The page does say, “it knows about chains and double-crosses but nothing else” which is interesting assuming he means dabble understands the *chain rule*. When CapellaBot's search depth is a little higher than it is now it finds double crosses on it's own, but it has no understanding of the chain rule.

No Eric—I bet it doesn't mean this. I bet it just means that dabble knows that “all moves which open a long chain are the same”—this greatly cuts down the search space, especially near the end of a game. In fact, my guess is that the best thing for a computer to know about chains (i.e. long chains) is (a) all moves which open them are equivalent, and (b) after a move which opens one, the only responses that one should consider are: (1) take the lot, or (2) take all but two and sacrifice the last 2. If you are just doing alpha-beta then you might also want to take into account the fact that if you're not losing on boxes when faced with that decision, then one choice is provably a win and the line is not worth analysing in detail unless you're actually faced with it in practice.

PS Eric or Phil: the source code to dabble is freely available. Can either of you make any sense of what it's doing?

You're probably right wcc. I haven't looked at dabble's code, yet. It's a windows project and I'm a linux guy, so I don't know how far I'll get with it…

It's written in some kind of Microsoft version of C++, so I would imagine that if you can read C++ then modulo the graphics routines or whatever it shouldn't be too hard to understand, if it's well-documented…Note also that the knox guy ported it to SunOS and linux, if what michael said is true (i.e. that he lifted a lot of the code).

a) I too am a linux guy; and

b) I want RoRoRo to be all my own work. It may take a long time, and it may never be particularly good, but I'd rather that than just port someone else's program.

Anyway, if dabble's available for MS Windows, then there's precisely no reason for incorporating it in a bot here (or at vying). If people want to play against dabble, then they should just play against dabble, and not waste time with a web server being a middle-man.

I did download the code for dabble. I won't be able to use any of it because it's windows centric and, like Phil says, I don't want to spend my time porting someone else's code. However, I don't mind looking at whatever techniques it uses. That said, it's a lot of C++. Several times as many lines as CapellaBot, and I don't much care for C++ so I don't know how hard I'll actually look at it.

(which is not to say it's not a fine program, of course, because I have no idea)

I notice a number of the D&B championship leagues are completing. Does anyone object to RoRoRo playing in the next championship? I reckon he's only batting at about 1550-1600 (he's having some success against 1500s currently), so won't interfere with anyone who takes the game deadly seriously. The more games he plays the easier it will be for me to isolate the weak spots that need attention most urgently.

I suspect the championship won't finish for _ages_. It's the 3rd division that always drags on. ch14 won't start until the end of April. In ch12 none of the four 3rd div rounds had finished when all of the 1st, 2nd and 4th rounds had.

Here's the rough state of play:

1.1 michael vs. everyone

2.2 hoeksmarp vs. 2 people - couple of moves left

3.1 miuek vs Henrik Sjøl - approaching SCB

3.3 Dom vs. Lynda - 2 moves left

3.4 Belen vs. 3 people

4.2 George vs. Denise - last move

4.3 ria vs. 4 people - all in LCB

4.4 asha vs 5 people - most approaching SCB or beyond

4.5 caesar007 vs missA

4.7 Moot Point, roborally, bloke 3-way.

The thing that amazes me is that most of those games are over. There's no choice, no decision, no nothing left apart from either automatic playing of the only sensible thing or, even quicker, a simple resign from one of the parties.

But it looks like divison 3 are the not the most likely division to finish last this time.

Hoeksmarp had been moving regularly, but now hasn't been on in about a week.

I don't know why it seems to be standard in this game to not resign. I do, but so many do not. Perhaps it's because the game can't go that many moves. But in addition to speeding the game up, resignations preserve enough of the play on the bord so that one can look at a final position and remember how the game went. When you play until the board's full, you can't do that.

The thing that Phil will learn, sadly, over the next 6 weeks is “it ain't over till it's over”. Some of these games will plod on for weeks, I bet, even though anyone who knows how the game works could easily “adjudicate” them. It's just one of those things.

@Dvd: people don't resign because it's easy to make a slip in this game :-) I don't resign much; I just tend to play very quickly when I've analysed the game, which I've always felt is not that unreasonable.

Is it really ethat easy to make a mistake when there is at most one box and all the boundaries of chains have been determineed, even if not completely filled in?

In a game where the controlled value is negative (i.e. lots of loops) it's _definitely_ easy to make a mistake!

By “box” I meant loop of 4. If there are zero or one loops, and the only loop if it exists is of minimum size, I don't think I'd make a mistake, and you're a whole lot better than I am.

I absolutely agree that if the endgame is just a bunch of chains then it's hard to make a mistake. I just looked at the last 5 games I lost here, expecting to see loads of loops in all of them, but I didn't. In fact, I think that in practice my algorithm appears to be the following: if my opponent is sub-2000 I make them play it out, regardless of how easy it is, and if my opponent is someone like Scot or gej then I just resign the moment I know that we both know what's going on. I guess that to summarise, I seem to resign when I know that I'm sure that my opponent will win. Perhaps that's an entirely reasonable situation! On the other hand I have no objection to playing out easy wins against weak players who don't make a move for 10 days; that's their privilege. I usually play fast here but the other week I was so bogged down with work at work and childcare at home that I barely played a move for a week in any game, win or loss.

Oh, RoRoRo plays D&B on Vying games too now, for reference.

And he's hopefully fairly immune from player-2's mirror strategy, but still pretty darn stupid.

Thanks for bringing RoRoRo to Vying Games, Phil!

Do you have plans to extend RoRoRo to play other games there, too?

Not currently. My main focus is on LG, as that's my personal playing environment of choice. However, if there are games on both servers, then I'll try to make sure he can play on both.

That sounds good Phil. There are a few games in common between sites, Reversi/Othello, Dots, Amazons, Breakthrough, and Connect6. A few more will be added to that list eventually, but it's not my goal to “replace” little golem, so I doubt the full lineup will ever be at Vying Games.

I thought a little more about AI. I am wondering whether significant speed-up of the usual algorithm for endgames (i.e. “brute force”) can be obtained by spotting isomorphisms between small regions. Imagine an Icelandic 2x2 with the inner corner sacrificed, i.e., in plain English, an L-shaped region in a corner of the board (the corner box and the two boxes touching it).

+-+-+|x|  +-+ +|    + + +    

A sensible program would realise that the two corner moves are “the same” (because the corner moves are the same in any position) and only analyse one. But of course because of the global symmetry there is only one other move to analyse, and I bet most programs think there are two (and most of the rest think there are four). Furthermore, after this one other move the resulting position (an Icelandic 1x2) only has one move worth analysing (the free move) because this move dominates the sacrifice. So really the position above can be represented by a kind of tree: The L-shape, which leads to two positions: the Icelandic 1x2 and

+-+-+|x|  +-+ +|    + +-+    

and the Icelandic 1x2 now leads straight to the 2-chain and then nothingness, and the above position leads to either a 2-chain or a 3-chain (again: there are “apparently” 3 or 5 moves depending on how clever your program is, but in reality there are only two). So all the complexities of the original position are really encapsulated by this tree—actually, one could even make the two 2-chains “the same”, making it a directed graph. The directed graph (with certain labels on the edges indicating (a) whether the move is loony and (b) data about how many boxes the move sacrifices and, if it's loony, whether the resulting decision is an all-but-two or an all-but-four) completely encapsulates the original position in what looks to me like the most efficient way. Now you can forget about the original position completely and work with the graph of its followers. When analysing more complex positions one can spot moves which are isomorphic because their follower graphs will be isomorphic, and you'd only have to “analyse them once” as it were. I don't think any program I know about thinks about the game in this way. Would the added complexity of carrying trees around dominate the resulting simplification in the analysis of the game?

In each pic, move the 3rd and 5th lines left by 1 space.