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

    Hi,

    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 rhoads@paul.rutgers.edu
    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...

    Marius

  • 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
    invitation.

    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++.

    References:
    [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
    http://math.berkeley.edu/~berlek/papers/forcing.ps

    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 × 5 and
    4 × 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




Include game board: [game;id:123456] or [game;id:123456;move:20] or [game;id:123456;move:20;title:some text]