Methods for calculating Nim-values, and how I should be looking at the board? Dots and Boxes

21 replies. Last post: 2015-02-05

Reply to this topic Return to forum

Methods for calculating Nim-values, and how I should be looking at the board?
  • Sean_Hettenbach at 2015-01-27

    So, first of all, a quick overview of my knowledge on the game. I have played for over 10 years, learned the chain rule, and all the other basic stuff long ago. Played on yahoo dots and became very familiar with the 4x4 board. Once I realized that the 4x4 board was solved, It was gej who directed me to this site a long time ago which brought forth to me the 5x5 board. Excited about the new challenge, but with school and rebellious teenage ways, I never really got serious about the game. Now though, I've started to learn how to calculate nim-values. I'm getting the hang of it, but when it comes to larger portions of the board, all I have to rely on, is my ability to count moves ahead. I look at the board like I would a chess board. Thinking “If I move here, he moves there, I move there, he moves there.” and “okay, what's threat if he plays that move?” or “whats the danger with me playing this move?“. So here are my questions:

    1. What knowledge do I need to have in order to fully comprehend nim-values, and solving for them?2. Are there any methods to calculate a nim-value on the larger portions of the board, that would save time?3. How should I be looking at the board? What should my thought process be, when analyzing positions, and looking for the best possible move? (Especially the ones where I am winning, and I don't want to make a blunder if you will.)

    To be clear on the second question, I'm not looking for a way to cheat the proper calculations, Just a way to speed them up. And any tips that anyone can give me to be the best dots player I can be.

    Here's where I might seem crazy haha, but the goal, is for my mind to be a 'Dots-and-Boxes-Calculator'. If this means using a process that a program like the shark uses when analyzing positions, then what do I need to know?

  • Loony at 2015-01-28

    1. You need to know and understand the mex and xor functions. Solving Dots positions in regards to nim values is done recursively.

    2. I doubt there is an easy way to shorten calculations for big regions. As for small regions I recommend creating a list once and memorize. Then you can use the knowledge to compute nim values for bigger regions due to the recursive mechanics.

    3. I don't think any player is able to explain his thought process precisely. There is just too much subconscious stuff like certain patterns triggering certain thoughts and similar things.

    However, I can try to roughly explain my algorithm:

    a) Is it opening stage? Play a move that I memorized long time ago and I know is reliable.

    b) A position clearly won for me (that means for example, two regions with one big chain each)? Play any move.

    c) Endgame? Cut all social communication for a few days and concentrate on solving the position via brute-force.

    e) So, given you are here, it must be an unclear midgame position. Are there any regions already cut off from the board? Is there any structure that is or will be a chain with certainty? If it's a very early midgame position and you answered both questions with “no”, try to divide the board into the same amount of regions as you would want to have chains. Keep in mind that it's almost impossible to get more than two chains straightforward, because of the loop threat technique: http://www.trmph.com/dnb/board#5,e6f5c6e4d3h5c8e8f1g2i6g8i8e10f11 (looks like 3 regions in the beginning but in reality it's a safe go for player 1).

    Also, don't overestimate the power of nim. It's a useful tool in some situations but I strongly advise you against using it as a base for your thought process. In most cases you would only need to be able to distinguish between regions of nimval 2 or 3 (Also 0 and 1 of course, but that comes down to recognize if a structure is a chain or not. Rule of thumb: Anything bigger than 3x3 is a chain, otherwise try sacrifices to prevent chains, if that doesn't work it's also a chain). There are some surprising positions when it comes to chain building, for example: http://www.trmph.com/dnb/board#5,b5d5e6e8g8f5h5h9i6k8k6j9k4j3h3f3d3g2, try to find the unique winning move for player 1. There are actually tons of similar patterns, that's why the only thing you can do about getting very good is to play many games, analyze them afterwards and expand your internal pattern library.

    Also, try to generally not sacrifice boxes too early. Especially if one of the emerging regions can be outright divided. Being one box ahead usually means a win no matter how the chain fight will proceed.

    One last advice: “Be shapeless, formless, like water […]“. This famous quote taken from Martial Arts applies to board games above all. Regarding Dots this means to me that you should not try to follow a fixed goal like building x chains from the beginning. Use your opponent's moves to your advantage and adapt if needed. For example, when you are player 2, it might be a good idea to threaten small chains at the edge, waiting for your opponent to prevent you from doing this, and at the same time encircling the centre of the board in such a way that the outcome will be one huge chain: http://www.trmph.com/dnb/board#5,f3h9g10d3e2c4b3c6b7f5. Of course, if your opponent doesn't follow your plan, go for 3 chains nevertheless. Just leave the door open until you know you are winning. Of course this abstract principle may have other applications to Dots, so yeah, be like water and crush your opponents. :)

    Oh, and you won't be a “Dots-and-Boxes-Calculator”, because programs like Shark use a database containing billions of positions (that no human can ever memorize) and/or a derivate of brute-force search that is able to analyze thousands of positions every second (which is also impossible for the human mind).

  • Sean_Hettenbach at 2015-01-28

    ???

  • Sean_Hettenbach at 2015-01-28

    Alright, thanks Loony. Lots of helpful information there for me. I appreciate your response. So, to 'a) opening stage?': I'm currently working on my opening's, 1.f3/f5 seem to be the most commonly played, so that's what I'm studying at the moment. The familiarity with the opening game will come from my studying and playing them like you mentioned “I memorized long time ago and I know is reliable”. To 'b) A position clearly won for me': I can recognize if as first player, the board is decided as two large regions where only one chain will be formed in each, and I can give sacrifice boxes to keep it that way, and win the long chain battle. The only problem I have in this area, is seeing the “loop threat technique”. I Understand that one very well, but I struggle when trying to calculate how to win with loops on the board. For example, If I create a loop and there are two regions that are determined chains, but not that many moves have been played in the region, I have trouble looking for ways to limit the small chain battle, and trying not to sacrifice to many boxes, and in turn, allowing my opponent to win 12-13, because my chains were not long enough. Still having said that, I do know how to go about winning those positions against average players, it's the stronger players that I'm prepping for. I'm preparing myself to play against an opponent who plays near flawlessly. Is always making the best possible moves. So, I need a lot of practice in the area of, if I am winning, stay winning. Don't Blunder! Lol. To 'c) endgame?': so the 'b' is practically the middle game, which will need some practice. The endgame however, is what I mean when I say 'Dots-and-Boxes-calculator'. I know that there are so many positions the human mind can memorize, yet, I'd like to be able to figure out, or learn a technique for calculating a best possible move, but hands free. Do it with pure mind power and imagination… (which so far has been super difficult, losing lines, forgetting counts, not seeing a move 6-7 moves down the line.) So that's why I'm looking for a kind of, quick route for calculating nim-val's. Through of course, practice, repetition, memorization, and analysis, I can get better at finding the best possible moves. Learning from my mistakes and etc. To 'e) given you are here': I'm pretty good at determining 'automatic chains' or 'decided' chains. I have a very good understanding of those. So for example, B9 was the winning move, because player 2 cannot sacrifice, nor influence the top left region heavily enough to prevent a chain from forming. It's a lost game for second player. So you pretty much helped me to see that I've got the same kind of thinking pattern, I'm just not as comfortable with playing the positions, because I'm not as familiar with them yet. Great quote from Bruce Lee by the way! Love how you related it to the game. I've been studying the (1.f3, 2.d9/h9) response. Very common response, and looks so far like it has the highest percentage of responses to the 1.f3 move. Thanks again Loony! Another question I have, is how do other games like 'strings-and-coins' help with a strategy in dots and boxes?

  • Loony at 2015-01-28

    If you want to become a top player, your focus needs to be on “how to win the game”, not on “how to get the nimvals right”. Indeed you should learn how to calculate those tricky endgames with many loops, because you can't really prevent those against a decent opponent. Doing such calculation only with your mind is a tough challenge and I doubt it's useful for turn based play (it's a handicap). Furthermore - at least from my experience - using tools like trmph to analyze your positions deepens your insight into the game immensely, while doing everything in your head will get you faster and more confident for matches with little thinking time.

    There are some tricks how to speed up the calculations either way, just read wccanard's counting file. Strings and Coins is kind of isomorphic to Dots and Boxes, so it really doesn't matter which you are studying/playing.

  • Sean_Hettenbach at 2015-01-28

    I agree. I think I'll just focus on getting used to the board, and learning the patterns. I think I'll be studying out the game a little longer, expand my dots and boxes mental database, and then start to figure out a way that I'm comfortable with calculating my positions. I get ahead of myself sometimes, and just want to know everything there is to a certain one thing. Once again, thanks for the feedback Loony!

  • Christian K at 2015-01-29

    Nice to see a dots thread again :) you inspired me to sign up for the championship again.

  • Sean_Hettenbach at 2015-01-29

    Haha! Good to here Christian! I see we have a match against each other in the monthly cup, so good luck in that. I'll be making my move soon I promise. I just want to get to a point in my other games where I know the outcome, and can focus on the mc games. Especially the ones against you and purgency! I'm hoping to bring more people to this site. I work at a Starbucks right up the road from a high school, so a bunch of kids come in there everyday after school lets out. So, around the time that they start coming in, I take a break, go out in the café, pick a table, and set up a sketchpad notebook, a pack of Crayola markers, and ask people if they want to play. And these kids are always up to play haha! So I draw out a 3x3 board and we play a game. I play first to give them the advantage, but of course, since they don't know the tricks, I usually end up winning. Once I win, I then teach them the 'double-cross' and 'The all but two' trick, what a chain is, the chain rule, how to prevent chains from forming on the board, and the second go around they beat me!:) (makes me so happy lol) and then I say “Good game, gotta get back to work”. Well, now most of the kids are asking me to play them again, because they've gotten better! So not before long I'll have some decent players here… Hopefully that is.

  • Christian K at 2015-01-30

    Well I am very happy that you joined the site :) Dots and Boxes have not been that active lately (and I have not been either).

  • Sean_Hettenbach at 2015-01-30

    Thanks for the warm welcoming Christian! Maybe I should start another topic about this, but It sort of bugs me that the 5x5 board has been solved. Kind of takes away the motivation to get better at that board. If Dots-and-Boxes were to be as popular as say, chess in competitive board games, do you think the 7x7 board would be the better default? Or Possibly a 6x6, or 8x8 board for the possibility of there being a draw?

  • Loony at 2015-01-30

    Dots and Boxes 5x5 has only been weakly solved. That means Shark can win every game if he goes first. No one except this bot will be able to reproduce the algorithm. As long as he doesn't share the database 5x5 will remain “unsolved” for human play. We can't even learn something about openings from it because the first few moves don't make sense at all and are just there as a strategy to prove the first player win faster.

    Then we have some arguments against bigger board sizes. For example arising structures will most likely be larger, leading to less close games than in 5x5. Without those tricky endgames we already talked about, the game would lack an important part. Having said this, of course there can also be close games with many quads on bigger boards, they are just harder to build. So Dots could possibly reduce to a nim battle, pretty sad..

    Playing 7x7 would be just fine I suppose although I don't see any reason to switch boards as pointed out above. Even-sized boards would have the issue to invert the chain rule, so I wouldn't recommend 6x6 or 8x8. Besides I'm not sure if a draw option would be a benefit. They say chess is boring these days because of too many draws.. In my opinion the perfect game forecloses any draws but is at the same time complex enough to balance it in such a sense that both players have roughly equal chances to win. By the way, current 5x5 provides exactly these features. :)

  • Sean_Hettenbach at 2015-01-30

    Thanks for that explanation Loony. I had read something by wccanard which explained that the first x amount of moves could be played on a 7x7 board between a master and an amateur. and the amateur might actually be winning. Which is just random and bizarre. And you are exactly right about the closeness of the game. Those games where it's going to be 12-13 and you have to make sure you are going to be the one with the 13boxes. It's a nail-biter until the end! That's the excitement I'd always get from dots-and-boxes. those games where I knew it was going to be close, so I couldn't wait to finish the game and see if I had made the right calculations. Thanks again Loony! I'm much more motivated and excited about getting better at the 5x5 board, so that I can produce a challenge for you higher rated players, and bring another level of competition to the game of Dots-and-Boxes. “So simple a child can learn how to play, but complex enough to challenge an adult.”

  • Christian K at 2015-02-01

    If it was as popular as chess, I certainly think we would have to move to a larger board. There are no very serious dots and boxes players as far as I know. Still, I feel like te 5x5 board is almost aolved by the best players there are. With someone dedicating time to the game (like many do to chess) and more computer analysis, we would certainly need to move.

  • Sean_Hettenbach at 2015-02-01

    Well, I love the way Loony put it. There's a mass number of possibilities, as far as positions, on the boar. I think the real fun in it is the calculations, and the theories that apply to it. Yes, you can memorize certain positions as far as what moves to play next, but the important thing is that you know why the move's you make matter. Because when it all comes down to the end game, you have to have made the correct calculations to put yourself with the 1 more box that your opponent. So in the 7x7 or larger board… There would be no, 1 point games, because the game would be won on alone, the long chain battle. I think that competitive play as far as the larger boards would go would be to play a game on a 5x5 board, when that board is resolved, branch out the board to two more 5x5 boards from the original. How this would work is like this: Imagine the first y-axis column of dots were to branch out to the (-,+) region you would add another 5x5 grid to left (-,+ region) but using the original y-axis column of dots. The second board would then start using the original x-axis row of dots, into the (+,-) region. But no board would be created in the (-,-) region. The two players would then find themselves with two more boards to split the play on, but the winner of the first original board, would make the decision on which board to start the next series of moves on. Yet, if he plays in one region, the second player has the ability to play first in the opposite region. I don't know if this would work, or sounds interesting, but I just pondered that idea just now, and I think that would be quite the interesting game haha.

  • sghsal at 2015-02-03

    It may be foolish to assume there aren't any serious Dots and Boxes players. Christian, since you have the feeling 5x5 is almost solved by some humans, there is probably a reason.

    Beside that, I have to agree with Loony: The board is nothing like solved. If Dots and Boxes got more attention it would probably be the computers killing it but not by now.

    About big boards: Of course no one knows although there is this theory about the outcome being close even with increasing board size. I haven't played 7x7 thus can't confirm anything but it's perfectly possible a match would end 24-25. Maybe the best players will always find ways to make the game close no matter its size.

  • Sean_Hettenbach at 2015-02-03

    Good point sghsal. When it comes to computers solving boards, it then comes to the classic 'man vs machine'. Well, computers are just designed to that which man can do, but in a shorter time. Sure, if I were to start creating a database like the shark, with pencil and paper, and I was allowed to use that database, then yes the game would seem solved by me. That's why I like chess though. Computers might have 'solved' chess, but the computers aren't competing against the humans for world championships. There would be no entertainment in watching a computer beat a human flawlessly. The reason 'human vs human' is entertaining is the fact that humans aren't capable of perfection. The human will always make a mistake, or overlook something. Which then the other human will try to capitalize on. Other humans are artistic, creative, and they play with intents for interesting matches. They have unique play-styles. They themselves have characteristics. Where the computer is simply a calculator. Saying that dots could be boring because computers have solved it, is like say math is boring because the calculator solved all the problems.

  • Dryad at 2015-02-03

    5x5 is not anywhere near being solved… absolutely true, and yet a very “undeserved” way to put it. A game is solved by human players if there's one player who won't make a mistake. Ever. That is certainly not the case for 5x5 and it might never become a reality due to the various number of positions that are complex as hell. However, the way I see it is that 5x5 has become stale. Almost every single game I play seems redundant to me. I stopped playing actively for quite a while due to me thinking that I was bored of it trying to charge my battery and then last championship I returned hoping that this changed but over the course of ch 36 I noticed that it remained the same way — there's just no excitement anymore. Some people just grasped this board size, they just know what the best strategys and openings are and there's hardly anything yet to discover. I'm certainly done with 5x5 even though I still lose at times… I abandoned my accounts on various board game sites where I played 5x5 and don't intend going back to it in the next couple of years.

    With this being said it should be quite obvious that I support the idea of moving on to 7x7 and I want to contribute a little bit to your conversation since I've been playing 7x7 as well. My personal guess is that 7x7 is a second player win by 1 box… I feel that the first player should have a strong tendency to build 4 chains on 7x7 while the second player can use a more flexible playing style that is based on the 3 and the 5 chain options which provides player 2 with a slight advantage — once again, this is only a guess. Anyways, that one box difference seems to me to be on an entirely different “level” than the one box first player advantage on 5x5. A top-match on the 5x5 board strongly depends on who's going first and who's going second. I believe that who ever is winning on 7x7 before the first played line doesn't matter at all. In other words: contrasting to what you guys said I'm thinking that 7x7 is way more close than 5x5 for the simple reason that on 5x5 aiming for 2 chains is a huge advantage while on 7x7 it doesn't really matter what exactly your aim is, you have good chances either way. The argument of chains tending to be longer does of course make sense, however keep in mind that not only quads will appear more frequently but also that both players will try harder to actually win the chain battle and thus might tend to sacrifice more often upon other things. Another issue, and I don't mean to be disrespectful, but wccanard probably sucks on 7x7: My first moves are not random at all and my fear of losing to an amateur at 7x7 is not as strong as when I'm playing second on 5x5.

  • chickenlord123 at 2015-02-03

    Dryad 5x5 IS solved according to ur definition. The chickenlord does not lose any game thus does not make any mistakes XD tho still exciting, there are too many witty ways to beat players XD

  • Sean_Hettenbach at 2015-02-03

    Haha, thanks for the adds Dryad and Chickenlord. By the way Chickenlord, I love the person you have haha. Cracks me up every post you've made in the forums is just awesome. Especially the one that reads 'who is the best player on this site?' to which you responded 'I'! haha I freaking love it. Anyways. I'd be down to get better at the 7x7 board if that would be the board for the high level competitive play. I just want to know what the best board that would create for the most exciting and entertaining match. The goal is to find that board that most players have fun not only playing, but watching as well. Every game is a spectator sport, and the spectators need to be enticed as much as the player who's making the moves. Let me ask you this Dryad: What would bring back the excitement for you? 7x7 board, better players, more players, what would get you hyped to play dots and boxes?

  • Sean_Hettenbach at 2015-02-03

    Also let me note this: For me the 7x7 board would be interesting with sacrifices. having to decide to take all of a sacrificed chain or to double-cross depending on how much board there is to play on still, and if you can still threaten your based number of chains, without the double-cross. It seems like the 7x7 board would very much be a fun board to play on. I'll actually start a new topic on this so we can have a focus to my main questions! See you all on that topic!

  • diego44 at 2015-02-05

    Well guys, now that Dryad mentions it: I am going to leave littlegolem (resp. board gaming) as well.

    Just a few words about me:

    I started playing here when I was 14. My favourite game has always been Dots and Boxes, although I enjoyed many games here. Littlegolem certainly left a mark on me as I basically spent my youth here. It greatly helped me to discover my insatiable affection for abstracts, to improve my English, to realize there are people on this planet that share similar interests, and finally to find myself. I don't regret anything.

    Now is the time to say farewell. To every player on littlegolem, thank you ever so much for making this site the place it is and bringing joy to your fellows.

    I specially want to thank:

    Richard, for this site. The site is so awesome, I can't put into words…

    44monkey44, a classmate, for introducing me to the Dots and Boxes game. He is probably not aware and won't read but it's due to him that I discovered the passion of my life.

    _Astrid_, for learning the game together with me and been my sparring partner for years.

    wccanard, for his famous papers about Dots theory. Without him our understanding would be set several years back.

    Geoff Cameron, for continually providing a challenge and stay as a glimmer of hope throughout the years while every other Dots player stopped playing at some point.

    Christian K, for his video matches on Dots games and overall dedication.

    flipster, for really a lot of things, including being the most impressive player ever, for coming up with the revolutionary pro moves every good player is using until today not to mention his mathematical research, for trusting in me while even I wasn't, for preparing me to re-think my life and attitude and sowing the seed of self-awareness eventually resulting in my old me grown apart.

    Jeena (FairyTail etc.) for her imaginative devastating play and for her divisive posts. Every time she showed up was a diversifying relief.

    maraca, for teaching me TwixT (actually to anyone who is teaching a game to others, it's awesome to share knowledge that obligingly)

    Dryad. The one I should say the most about but I will cut it short and just say I'm so thankful to have you as a friend. No words could express my thoughts, our lasting friendship is supposed to stand the test of time, even beyond littlegolem.

    Everyone of you guys is sort of part of myself, you shall not be forgotten.

    I've always been sad about players quitting littlegolem and hoped for a return everyday, now I join the ranks of the vanished.

    http://w11.zetaboards.com/DromedaryBoard/index/ is dead by now although I left a short note about how to get in touch with me in case you want to revive it.

    Don't be sure I'll be back!

Return to forum

Reply to this topic