Computer Dots and Boxes Dots and Boxes
11 replies. Last post: 2004-05-30
Reply to this topic Return to forum-
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
-
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 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.