New version of Knox Dots and Boxes
7 replies. Last post: 2004-12-15
Reply to this topic Return to forum-
Knox (Computer) at 2004-11-02
I’ve finished a new version of Knox, and just in time for the
championship! :-)
The new version has an opening strategy. I don’t know
yet if it plays any better but at least it doesn’t seem
to do any worse. I’ll add some more comments later.
I intend for this to be the final version — except for
any tweaks and corrections needed to fix any as of yet
unrevealed problems with its opening play. -
Knox (Computer) at 2004-11-08
I thought I’ld include a description of Knox’s opening
strategy since it’s the only dots and boxes program I
know of that has a real opening strategy.
In a nutshell, if Knox “thinks” it can divide up the board
into a number of regions of the right parity, then it will
try to do so. If Knox doesn’t “think” it can, then it tries
to apply a “heuristic” (a rule of thumb) to come up with a
move. The heuristics have been changed from the previous
version; the new assumption is that Knox is currently losing
the long chain fight instead of winning it. E.g. the
heuristic phase now likes moves that create 4-loops (“Quads”) or have a high potential to turn into a 4-loop. If Knox doesn’t think it can divide up the board favorably and can’t find any heuristic to apply, then it gives up and plays a random move. Surprisingly, this now happens infrequently. I’ve already seen it get through the opening
without playing a single completely random move (more than
once in fact). It’s opening play now looks much more
“human-like.” Previously, Knox would just randomly throw
moves all over the place whereas if you look at its'
recent openings, you would have a hard time telling just from the moves, which player was the human and which was
the computer program. In fact it looks a lot more human-like than I expected it to (a fact that I’m happy
about). -
Knox (Computer) at 2004-11-08
The previous message can be thought of as the "executive
summary" of its opening play.
This message concerns how it handles the complication
that arises when “small” regions that get cut off.
Some situations are easy to deal with. If there in an independent long chain, then divide up the remaining board and flip the desired parity. Regions containing only 1 or 2 boxes can be treated as though they are not part of the board any more; simply divide up the remaining board as before. Similarly, cycles can also be treated as being
"off the board."
The tricky cases are what to do about a small region (say four or five boxes) that may or may not result in a long chain. If the nimstring value of the region is 0 or 1, then the parity of the long chains is “determined.” By determined, I don’t mean that the long chains already exist or have been started; I mean that the parity can be
forced by one of the players. I’ve never seen this written down anywhere but if the nimstring value is 0 or 1, then the parity of the number of long chains equals the
parity of the number of strings minus the number of coins plus the nim value (or equivalently, ... equals the parity of the number of moves minus the number of boxes plus the nim value.) If the parity of the small region is odd, then you treat the region just like an independent chain — the region is “off the board,” divide up the remainder and flip the desired parity. If the parity of the small region is even, then treat the region as being “off the board” and divide up the remainder without flipping the desired parity. The last case is when the nimstring value of the region is not 0 nor 1 meaning that the parity has
not yet been “determined.” In this case, treat the region as "on the board" and it will simply become one the regions you are trying to divide the board up into. -
Knox (Computer) at 2004-11-08
More details on dividing up the board.
[Warning: this section may not be understandable unless you
are familiar with computer science, and Graph Theory
(vertices, and edges)]
To “judge” whether the board can be divided up into a number
of regions of the desired parity and to come up with a move when the judgement is yes, Knox searches (“I go here, you go there,...”) over a limited number of moves and countermoves.
To determine which moves to search over, Knox finds an approximate solution to the “Min-Weight Graph Partition” problem. It does this for every non-terminal position encountered in the search (at a terminal position, Knox stops searching and assigns a value to the position according to whether Knox estimates the position
as being favorable or unfavorable). In the most common
applications of Graph Partitioning, the partitions need to be the same size. But in dots and boxes, the partitions (regions of the board) do not need to be the same size. So as long as all the regions are “reasonably” large, then we are satisfied. The reason for the “Min-Weight” business is that in dots and boxes, some moves are “free” while others give away boxes. Hence, we assign weights to the edges so the free moves are the most desirable, then moves that give away a single box are the next most desirable, and moves
that give away two boxes are the least desirable. Also, the weights are chosen so that moves that open a long chain
will never be considered. The partitions found are not guaranteed to minimize the weights of the “edges crossing the cut” but instead they are approximately minimum. The reason for not solving it exactly is that (the decision version of) the Min-weight Graph Partitioning problem is “NP-Complete.” This is a technical term with a precise
mathematical definition. Speaking somewhat loosely this means that there are very strong reasons for believing that large-sized instances of this problem cannot be solved exactly by the world’s fastest computer in anything even remotely close to a reasonable amount of time (e.g. before the universe dies of old age). But we can find an approximate solution very quickly. Luckily, an approximate solution for a dots and boxes board of the sizes
people typically play is likely to be an exact solution!
Once the partitions are found, the moves entered into the search are the ones corresponding to the "cut edges." -
Knox (Computer) at 2004-11-08
So what are the weaknesses of Knox’s opening play. One is that the sets of moves it considers for each player during
the search are rather limited in more than one way. First, there could be several partitions with the same minimal? weight that might be chosen. The set of moves corresponding on one partition could be better than those of another, and Knox may choose a bad set. Also, the best moves might not correspond to any small weight partition!
From one move to the next, I’ve seen Knox switch back and forth between “I can” and “I can't” divide the board up as I would like. The restricted move sets it considers seems
a likely culprit. If that’s the case, then it seems as though for some of the moves, Knox will be playing to help the opponent! (I hope that’s not the case but I don’t
see why it wouldn’t be.).
Another weakness is that Knox doesn’t have a way to determine the parity of the long chains from any particular “largish” area of the board until after the fact.
So it could easily split up the board only to discover
that one of the regions won’t form a long chain resulting
in Knox having the wrong parity — sort of an oops, what
I just did with my last couple of moves wasn’t a good idea.
The biggest improvement stemming from Knox’s new opening play may be that game is much more likely to divide up into regions where Knox can then apply its nimstring
calculations where Knox should have an advantage over people.
Knox’s opening strategy is still the weakest part of its
overall play but that’s also true of people who have at
least some skill in the game. Thus, I don’t know how
well or whether people will be able to take advantage of
its weaknesses; to find out is a big reason for testing
Knox out against real people in real games.
After writing all this, I no longer feel bad about taking
so long to finish Knox. The opening phase includes such
elements as a search procedure, finding an approximate solution to an NP-complete graph theoretic problem, and nimstring calculations. From an algorithmic point of view, it’s quite complex. -
Dansgek at 2004-12-15
The Program plays nice, but it is beatable....is this the final version to play at little golem ??
I’m playing a nice game against it...13-12 it will be as far as i can see ;) -
Knox (Computer) at 2004-12-15
Yes this is the final version.
I agree that you have a 13-12 win (assuming you don’t
make a really stupid mistake). Scot and Michael have
also beaten the final version of Knox in the current championship (both games were also 13-12).
Ypercube also has a win against Knox in the current championship but it would be more correct to say that I lost
for Knox rather than saying that ypercube beat Knox. In the game, Ypercube had correctly sacrificed a single box. Now the first thing Knox does is take any free boxes. So Knox
printed out the move to take the box, then printed out a
few search stats, and then its final move (followed by the
updated board). I lazily clicked on its final move choice
at the end of the listing without paying attention to the fact that Knox had also taken a free box. (Dumb! Dumb!)
Well ypercube thankfully took the free box which changed
the result from a 13-12 Knox win into a 12-13 Knox loss!
Oh well, at least I’m glad there wasn’t any money riding
on the game. :-)