Championship Dots and Boxes
19 replies. Last post: 2021-05-28Reply to this topic Return to forum
Hjallti at 2021-04-04
I ended second in the latest championship with pretty mixed feelings. On the one hand I only lost from a computer program so it looks I was the best player. I do NOT understand why proven strong AI is in the championship, which brings me to the other hand.... The players that are ussualy better don’t play in the championship anymore. Probably because of these programmed players....which makes my second place not such a big deal.
What can we do to make it better?
_syLph_ at 2021-04-04
today i learned i am robot. beep beep boop
Wickedestjr ★ at 2021-04-04
Do you have any evidence for thinking he’s a ‘proven’ AI? That’s a pretty strong statement and one that I don’t believe to be true.
Hjallti at 2021-04-07
Oh sorry, I was convinced because the underscores which could be an indication of ai, although here is the habit of adding _c or _ai.
What I told before was another indication. Where are the other strong players. For sure my level didn’t raise enough to be suddenly runner up.
Mostly they leave because they don’t want to play a computer.
My statement about proven AI was bad miscommunication. My apologies
_syLph_ at 2021-04-07
I think you are raising an important issue for the game. The level of play has without a doubt declined over the years and I think the issue is that we don’t have a stream of new players and I see many reasons for that.
Dots and boxes is being played worldwide by many people, notably kids in school. The core reason why none of these pick it up as a competetive game is that the chain-rule needs to be known in order for anything to even make sense, kids in school aren’t going to figure this out by themselves. So thats a big issue when it comes to the games accessibility. Stuff like Numberphiles video with berlekamp are by far the best method of helping the game in this regard atm.
Then because Dots and Boxes isn’t being perceived as a competetive game by the general population it in return isn’t being added to many internet websites. Other than littlegolem and jijbent I know of not a single place online where it can be played on even a half-decent level.
Finally there is the exclusive look on just littlegolem, a platform where the game has been understood but still isn’t doing well on. I think lg has a bunch of issues, imo its stuck in time and desperately needs some kind of live-chat / discord server. There needs to be some kind of communication among the playerbase of littlegolem in order for dots and boxes to be picked up by players of the site and this dead forum is obviously not doing that. Wccanard used to do a phenomal job of putting out content into this forum and get users of this site to read his posts and develop an interest. Not only that, but any game ever imo is only fun with a community, so if the forum is dead then thats all the more reason to lose interest even if you do pick the game up. More communication and tip giving would definitely also help players improve. Perhaps it would be my role as a stronger player to share more insights into the game, unfortunately my interest in the game has declined as a result of feeling shunned out by the community as a response to my 2015 post where I admitted to cheating during the 2012-2014 timeframe, plus I just moved on to other things over time. Just having moved on to other things is generally the reason why many top players have left the game of course, you can only ever stay interested in a game for so long. The bigger issue for sure imo is that new people need to be brought into the game and taught how to play it.
I think it actually has very little to do with computer programs though, because afaik no computer program even plays the game at the moment and in fact the appearance of the_shark years ago had actually raised interest within the games community back then.
Florian Jamain ★ at 2021-04-07
I made a video on Dots and boxes just to explain the chain rules cause I totally agree with the fact that if you don’t know this rule the game does not make any sense.
When I did not know it I thought that this game is pure bullshit :D
Hjallti at 2021-04-10
I used to be posting a lot on the forum until I started to play from my phone. I really don’t feel the community anymore like in the old days.
Maurizio De Leo ★ at 2021-04-11
One possibility would be to get it implemented on BoardgameArena. It would surely have a sizable player base, as it is very well known, at it might spark interest in people who want to improve.
SadGrayDay at 2021-04-11
Hi everyone, thought I’d chime in as someone with a bit of D&B history. Many-many years ago I used to play here at a decent level, under nickname Polydarya. Then I quit playing for something like five years, lost my password — and now I’m trying to return. On the personal side: originally I came to Dots&Boxes together with my ex-partner, who became a top player here in those good old days. So the game wasn’t just an online thing to me: we could discuss finished games at home, or play a quick pen-and-pencil one... Now I come to realize I benefited from that a lot: my ex-partner remains the only strong player I know irl, and I’m finding it difficult to get back to my old level of play. So if there are plans of something like a discord group or whatever, I’d love to be in!
Also hi syLpf, I’m so sorry to hear you felt shunned after 2015! It’s so unfair. All the cool stuff you’ve done for Dots&Boxes dramatically outweighs that childish cheating episode. The short guide you wrote remains a great concise introduction to meaningful playing.
Christian K at 2021-04-16
I enjoyed playing here a lot. I did find it discouraging that sylph (previously cute girl) as a bot was dominating the championship. Also, trmph stopped working for analysis, which made it a lot more work to analyse my positions using pen and paper.
I assumed it was a bot since I got this message
"Greetings friend! This is an automated message to inform you that you have just attempted conversation with a robot."
Reading this thread it seems it is not a bot but just the return of a really strong player (Dryad/7ics). This game has had a few super strong players over the years that I feel really are playing a different game than me.
wccanard at 2021-05-21
Hi! Long time no see! syLph nice to meet you!
I got interested in dots and boxes because of Conway-Berkelamp-Guy’s Winning Ways. I can proudly tell you that I have beaten John Conway at dots and boxes, and when I had a meal with Berlekamp in Berkeley whilst I was supposed to be doing number theory, he declined to play me on 5x5, saying that he knew he would be hammered. They were both a lot older than I was.
The reasons I was good at dots and boxes are easy to explain. First, as a mathematician I had understood the theory of chains and nim, and during my early studies of the game I made much use of a C++ program by Glenn C. Rhoads and Freddy Y.C. Mang which computed nim values of positions, which I used to get a “feeling” for this invariant of a position. When I had become an expert at this sort of thing (knowing e.g. the cunning move in a 2x3 corner with nim-value 4 and all this other high-falutin' nimber stuff) I started playing here and I was getting hammered off the board by 16 year olds who knew absolutely nothing about nim because they realised that it didn’t matter what the nim-value was, you actually have to count the endgame to know whether or not you should lose control. Keeping control costs money in the real world, in contrast to the abstract world of nim. The authors of Winning Ways have these throw-away statements that “in our experience the best way to play is to make sure you win the nim battle even it means sacrificing a piece or two” or whatever they say -- “your best odds are in the chain battle” or somehing, but this approach had not dated well, and the players at littlegolem and jijbent were well aware of this. They make a couple of 4-loops (something I would explicitly aim for as P2 in order to complicate the game — as I got better and realised it was probably a P1 win because my P1 win ratio was so high — note that 3x3 is a 6-3 P2 win IIRC but I am now very rusty on these matters). I realised that after about 20 or maybe a few more moves I was in a really good position to be able to count the position on pencil and paper and win, because I had proved theorems precisely classifying the cost of a 1x1 and a 2x1 corner using a more refined metric than the nimstring one, and this result about how you can add long loops: 4+6=5 in the sense that these games play in exactly the same way — this is a stronger invariant than the nimstring one, which just says they both have nim-value 0. I guess Berkelemp did the same kind of thing with go, it’s just that dots and boxes is a shorter game, so an important endgame strategy (i.e. counting) has a higher payoff — I could become an expert dots and boxes player, but he could not become an expert go player until the endgame, by which time he had long lost against the experts.
Every well-played game on this website was 13-12, I remember losing something like 17-8 to Flipster and once feel very humiliated (people often resigned before the end but experts all knew what the final score would be, we were all learning to count). Flipster became better at counting than I did — I made some conjectures and he proved them for a school project he was working on; we ended up writing a joint paper on the subject which was published in the mathematical journal “Integers”: it’s article G8 on the Integers website . I was very proud of this paper because we had beaten Conway at his own game, we had proved a much harder theorem than the main theorem of Winning Ways about actual values of games (i.e. beyond nimstring — for nimstring they were the masters). We had an algorithm which humans could apply using pencil and paper. Flipster was so good at running this algorithm, so young, even before we’d proved it worked, that when I realised that he was playing essentially perfectly from move 16 or so, I accused him of cheating; after a heated discussion I realised that actually he was just extremely smart and I apologised. Cheating, which was always present on the site (in my opinion), is using a computer to analyse a game in progress. This is something I never did, even in high pressure games, although the moment an interesting game I was involved in would finish on a site I would instantly feed it to the dots evaluation program — I never used the nim evaluation program any more. The dots evaluation program was available online for free, it just analysed the true value of the game by brute force, and there were a few people who would use it to cheat.
The main reason I quit dot and boxes was that the computers were coming. Computers had solved 4x4 long ago (the version played on Yahoo, and the reason I never played there). The computer program Dabble got quite good at 5x5 and the number of clear cheaters on this site began to increase. Dabble was fairly strong, although I could usually beat it even as P2, as long as I was careful and played carefully from about move 15. But I didn’t play it much because I just found playing computers boring. My favourite pastime was discovering I was going to lose 13-12 to a human opponent and finding a complex line which I thought would be very difficult for them to play correctly, and then proudly telling them “your mistake was on move 17 where it's essential that you make this sacrifice” at the end. Bill Fraser was a student of Berlekamp and he was working hard on brute-forcing 5x5 for academic reasons, and he let me play on a prototype which had solved every game which had a line from each of the four corner “dots”. He turned this into a prototype game which I played privately against a few times: you could choose to be P1 or P2, and the computer’s first <= 4 moves were all joining a line from a corner which previously had no lines coming from it (and avoiding some stupid trick where you can lose a box by being dumb) and then after that you were guaranteed that it was playing perfectly, so if you’re P1 and not 13-12 up at this time then you’re already dead, and you were going to have to work hard to beat this thing as either P1 or P2. I knew what was coming, so I quit. I had my publication.
My interest in games then led me to the book by Hearne and Demaine. I got interested in P v NP, whilst trying to understand if there was a better approach than brute force to dots and boxes, and even gave a talk about P v NP at the Royal Institution of Great Britain! https://www.youtube.com/watch?v=A6J9p4iOr3A .
So it’s clear that computers can solve dots and boxes — my (former) hobby. But can they solve my first true academic love — pure mathematics? This is what I’ve been trying to figure out for the last few years. I have lost track of the dots and boxes wetpaint blog, but I have a new blog now at xenaproject.wordpress.com where I talk about trying to teach pure mathematics to computers. I never play dots and boxes any more! But with proving mathematical theorems, I am now on the side of computers.
Kevin Buzzard a.k.a. wccanard.
wccanard at 2021-05-21
Can I not edit that message? There are a few typos. I never finished my “They make a couple of 4-loops” sentence — it’s supposed to end something like "...and then they just count the game using vague principles like “two 4-loops seems to cancel” and hang the nim battle at this point".
_syLph_ at 2021-05-21
Love all your work on dots and boxes, wccanard. I think you maybe understate the complexity of dots and boxes endgames in your post. Flipster is one of the greatest, but playing perfectly from move 16 isn’t something humanly doable. I also think that the amount of games without a mistake is extremely low, so even if a lot of games ended 13-12 there were likely mistakes in most of those games at some point. In my last game with Loony I made a mistake in move 19 and then he followed with a mistake in move 20 which we thought was funny when we talked about the game afterwards, concluding how bad we humans are at this. In human play I would say the P1 advantage is fairly negligible. It may have been a bigger deal 10+ years ago when it was the meta for P2 to aim for 3 chains, because it’s significantly easier to get 2 chains than 3. Nowadays I tell people to not aim for 3 chains and instead try to adopt a playstyle that lets you aim for 1 and 3 chains at the same time. Against the people who know how to play like that I run into extremely complex positions in the vast majority of games.
As for dabble, I would say by itself it isn’t very strong, because by the time it can actually evaluate a position it will have found itself in a clearly losing position. As a tool however, used by a human player it becomes outcome decisive. I mess up between move 18 and like 23 all the time; I’m unwilling to put hours of analysis into these positions so I play them by intuition and a lot of the time my moves are just not correct. In 2012 I was using some laptop that my mom bought in 2008 or whenever and dabble would be able to evaluate positions at some point between move 18 and 20 depending on the complexity of the game. Nowadays I use a laptop that I got in 2015 and dabble can analyse most games at move 16. Idk how early it can do it on a 2021 consumer laptop but they have only gotten more powerful of course. So yeah, I’d say even a half-decent player using dabble can likely beat a non-cheating top-player a quite significant amount of the time, if the top player is like me and can’t be arsed to analyse his positions for more than 10 minutes, which in a way is unfortunate, but then again chess is flourishing despite stockfish.
Putting Bill Frasers database aside I have seen no bot that has any mastery of the early part of a dots and boxes 5x5 game. They could be making such a bot easily with a neural network approach I’m sure; I think algorithmic approaches are kinda futile. But yeah, I’m sure not too long and there will be some public program available that just plays the game kinda perfectly from the beginning.
I would love to play dots and boxes in a live play format, I find that to be more enjoyable and I believe program abuse is less incentivized in such a format, but again there is no place where you can play dots and boxes live with stronger players.
_syLph_ at 2021-05-21
aaahhhhhhhhhhhhhhhhhhhhhh what happened to my paragraphs. god damnit littlegolem
wccanard at 2021-05-22
There would be a point at around move 18 or so in a game where if I was playing a strong opponent I would just try and brute force analyse the rest of the game by hand, or at least come up with what I felt were the “tight” lines. I would end up with several pieces of paper which I would then keep during the endgame to make the re-analysis easier after every move was played. I am quite obsessive-compulsive so had no problems spending 3 or more hours analysing an endgame. However when I realised that I had tools on my computer which could just do the job so much more quickly and easily I got disheartened, because I didn’t want to cheat, but I knew I had to keep playing like this if I wanted to keep my ranking, and after a while it all seemed a bit pointless when computers could do it so much more easily. I analysed a whole load of top games played on this site from move 14 or so (typically the point where it became feasible to brute force) after they had finished, and often found that both players were playing perfectly from around this point.
Proving mathematical theorems on a computer is now a game I’m enjoying a lot more, because when you use a computer then instead of calling it cheating we call it progress, and furthermore if I spend three hours on a theorem (analysing it both on paper and using a computer) then I can call it research (i.e. part of my job) rather than calling it “goofing off and playing puzzle games” (which was what LG was all about for me, until I started realising that I could probably turn my thoughts into a research paper...). Somehow turning my hobby (Zen puzzle games) into my job (mathematical research) has been a really interesting development, and in some sense it started with the dots and boxes paper. Hey, did you see on ArXiv a week or so ago that they proved Dots and Boxes is PSPACE complete? I’m yet to read the paper but I see it cites the “LG paper” I wrote with flipster.
William Fraser at 2021-05-26
I’m sure I posted this on another thread, but just to get everyone up to date, I’ll note that The_Shark_c has now fully solved the game, and it proved that not only is it a P1 win, but that P1 has no losing first move.
Miwarre ★ at 2021-05-28
@William Fraser: big new and thanks for re-posting. Is there some text one can read about it?
Carroll ★ at 2021-05-28
Part of the discussion is here https://www.littlegolem.net/jsp/forum/topic2.jsp?forum=110&topic=148.
There is also a Google group.