Computer Dots and Boxes Dots and Boxes

11 replies. Last post: 2004-05-30

Reply to this topic Return to forum

Computer Dots and Boxes
  • Knox (Computer) at 2004-05-25


    I'm writing a computer Dots and Boxes program. To test

    the quality of its play, I'm making the latest version available for play at littlegolem. I could enter it in

    the championship but I'm not sure how people would feel

    about that. You can let me know whether you think it is

    OK or not by sending me email at

    I'll respect the wishes of the majority.

  • Marius Halsor at 2004-05-25

    My very personal view on this matter is that I think it's ok for an AI to enter MC or RT, but not the championship. And the name should state clearly that it is an AI.

    However, if it becomes clear that the AI is superior to almost every human player (like WZebra is in reversi), then the AI should probably be withdrawn altogether…


  • michael at 2004-05-25

    How can i play this program? I'd like to test it…

  • Knox (Computer) at 2004-05-25

    You can play the program on littlegolem by issuing an


    I just realized that I need a version that can store a partially played game and restart it from the stored moves, but this should be easy to add.

    If you are on UNIX system, I can email you an executable

    that you can play at your leisure (I don't want to make the

    source code available just yet). The user interface is just

    plain ascii text. I won't be adding a graphical interface

    until after finishing all the AI stuff.

  • Knox (Computer) at 2004-05-25

    Also, I don't know how good the quality of its play is.

    It beats me but I'm by no means an expert player.

    Considering Michael's impressive record, for him

    the program is likely to be just another victim but

    for the rest of us …?

    The program's most obvious weakness is that it has no real

    strategy for the early part of the game (approx. the first

    35% of the moves). It will try to avoid 4-loops and try to extend long chains, under the optimistic assumption that it will eventually be able to take control. But other than that, its early moves are just random.

    I suspect that a player like Michael can get the program in a hopeless position before the program has an even a clue as to what is happening. But against someone like me, the

    early essentially random play is no weakness at all because I don't have any early strategy either! What exactly

    should you try to do during the early part of the game other than just play random moves?

    There is a sharp boundary in the quality of its play.

    After the random phase, it will play two or three reasonably

    good moves and then all of the sudden it will play virtually

    perfect! If you are not in good shape after about the

    first 1/2 of the total moves, then you get creamed.

  • ©|-|®!§ at 2004-05-26

    A program like that is very interesting. As a programmer, i was wondering how you went about making the algorithm for it? While i was making a game of dots i was thinking about how i was going to make it check if boxes were made. I'm not sure i could make a game that played on it's own that was smart, i've only just started programming about a year ago. I had an idea that i could do something like a Tree, make the computer go at random a couple hundred times while recording in the tree whether the moves are good or bad. Then make it read from the tree so it knows if the rout it's going in would be a victory or a loss. Obviously this wouldn't work as much for Dots as it would for a small game like Tic-Tac-Toe. But because i am stupid, i couldn't figure it out and ended up taking the long way with 25 different If statements (6x6 board). What language do you program in?

  • Knox (Computer) at 2004-05-26

    The most common game playing algorithm is “mini-max”

    search with “alpha-beta pruning.” (you also need to

    use a hash table to get an efficient search).

    The problem with that approach in dots and boxes is that

    it almost impossible to come up with an “evaluation function” that gives a reasonable numeric evaluation

    of how good or bad a position is. In chess, for example,

    you can assign say 100 points for a pawn, maybe 320 for

    a bishop, 500 for a rook, etc. Then you can assign values

    to various position factors such as mobility and king-safety. But how on earth do you come up with a

    reasonable numeric evaluation of an arbitrary dots and

    boxes position?

    Knox does have a “loony endgame” (see refs. at bottom)

    evaluator so it doesn't have to search all the way to

    the end in order to play well. A technique that can

    be used in dots and boxes is “nim” values from “nimstring.”

    This can used to get the right “parity.” It's really

    only effective when the board is divided up into disjoint

    regions. If the position consists of a single connected

    region, then the nimstring evaluation is too computationally

    expensive to do in anything approaching a reasonable amount

    of time until you get so close to the end that you can

    ignore nimstring and figure out what to do just by brute force search.

    I haven't finished the nimstring stuff which I will

    add to the program whenever I do finish it. Anyway

    the program is written in C++.


    [these will define such things as “loony endgame”

    and “nimstring”]

    “The Dots and Boxes Game: Sophisticated Child's Play”

    by Elwyn R. Berlekamp [you can order this online

    at many sites like amazon, barnes and noble, etc.]

    “Winning Ways (for your mathematical plays)”

    by Elwyn Berlekamp, John Conway, and Richard Guy.

    [This is a two-volume out of print text on combinatorial

    game theory that contains a special chapter just on

    dots and boxes. There is a lot of overlap between this

    chapter and Berlekamp's thin book above. This seminal

    work on combinatorial game theory is being re-printed

    in four volumes. Volumes 1 and 2 are out which cover the

    old volume one – the theory of combinatorial games.

    The specific games are covered in old volume 2. You

    may be able to find the old versions in the library;

    it's a great book.]

    “Forcing Your Opponent to Stay in Control of a Loony

    Dots-and-Boxes Endgame,” by Elwyn Berlekamp and Katherine Scott at

    This is a nice paper which among other things demonstrates

    that even loony endgames can be extraordinarily difficult.

  • Ronald Lokers at 2004-05-27

    Obviously I'm not opposed to a program entering a tournament, as I am doing the same with loco-ai, my Streetsoccer program. On that forum, I asked the same thing but in the end only 2 or 3 people protested, the rest didn't mind. And even those 2 or 3 people were not really opposed, they just prefered playing a human opponent. Now dots (like chess) is a completely abstract game where Streetsoccer still has a big random factor (the dice rolls) so there is the main difference. I wouldn't like to play against an opponent that always finds the perfect move and just can't be beaten. Unless the opponent is human: a person might be willing to tell me what I'm doing wrong while playing, or give me tips on how to improve my play.

  • javerberg at 2004-05-27

    How does the program perform against dabble? Is there any “easy” leavels for us mortal?

  • ©|-|®!§ at 2004-05-28

    I'm only just learning how to program in C++ so obviously something like this is a little too complicated for me. The only things i can do in C++ are the basics. I am a quick learner though and i have a very good memory, so if i see how to do something i remember. I am very good at programming with Visual Basic 6, although a program like this is probably much harder in VB than in C++. I still don't understand how you made “Knox” know where to go and about nims and chains or whatever. This kind of stuff has always interested me and i would like to learn a little more. And i definately do not mind your program entering tournaments, i'm always up for a challenge (even though i suck).

  • Knox (Computer) at 2004-05-30

    The program is definitely beatable. E.g. see the other

    thread about an analysis (by Michael) of an unrated game

    in which he beat Knox (Knox's only complete game on

    littlegolem so far!). In fact, it is not even known who

    wins on the 6 dots by 6 dots board; the largest sizes that

    have been completely determined by computer are 5 x 5 and

    4 x 6.

    The current version of Knox hasn't yet been tested against

    Dabble. J.P. Grossman tested the previous version against

    Dabble in a 10 game match which Knox won 6-4. The current

    version is only slightly different (it has a search

    refinement involving an addition use of the hash table).

    As of yet there are no “levels” of play.

Return to forum

Reply to this topic