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.

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

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

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.

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.

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?

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.

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.

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

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

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.