Havannah / subgames Hex, Havannah
11 replies. Last post: 20090404
Reply to this topic Return to forum
ab at 20090401
Suppose i have an algorithm to separate the board into two (or more) independent areas (subgames),
and solve each (using tree search), for each of the players playing first locally, how much
information do i need to determine the overall winner of the game?
_I_ think it should be enough to have a number for each subgame (actually two: one if white plays
first, one if black plays first in the subgame) that specifies how many moves it takes
for the player playing first to win the subgame (winning connection)
(for the calculation of the number, the opponent passes usually, unless he must answer
a threat locally > then the number of times he passes is subtracted)
There is something like Combinatorial Game Theory, i looked at it again, but it is too complicated
for me :( … However the question is: is it really (not?) necessary here, i.e. is my simple theory
above “enough”?
E.g. i remember from playing, that sometimes it happens one player has to play threats
in a specific order (in the endgame), because when he plays them in the wrong order they
would not work anymore (opponent in other part of the board is already faster). Hmmm …
i think that would not matter … ?!
(see also http://senseis.xmp.net/?Havannah, i added a section about that)

Marius Halsor at 20090401
Are you talking about solving the endgame/race here, where a fork exists for both sides, they just have to be “filled in”?
Regarding order of threats: I think one should always play the credible threat that requires most moves first. And a threat is only credible if it requires less moves than it would take you to complete the fork. So if your fork needs 7 moves before it's completed, and you have 3 threats that require 8, 6 and 3 moves to win, respectively, play the “6” threat first, then the “3” threat, and forget the “8” threat. If you play the “3” threat first, your fork now only needs 6 moves to win (assuming this threat reduces the number of moves in the fork by one), and the “6” threat is no longer credible.

Marius Halsor at 20090401
Looking at it again, I suppose a good opponent could see that the “3” threat would reduce the number of moves required for the fork later, and thus consider the “6” threat noncredible in the first place. I think playing the longest threat first is still a good idea, and I'm pretty sure I've had games where it HAS been decisive  possibly for some other reason.

Johannes Waldmann at 20090401
Yes. I also think that analyzing subgames (e.g. by MC/UCT)
and then combining the results (by some form of CGT) is the way to go.
(UCT alone definitely is not.) See Section 10 of this draft paper:
http://www.imn.htwkleipzig.de/~waldmann/draft/havannah/
Although the paper focuses on simulations.
(That's a nice excuse for my bot playing so bad…)

ab at 20090401
yes, endgame races, but it would apply to any subgame (which ends with a win of the whole game).
for simplification you can think of it as incomplete forks with some ring threats, but there is no difference for generalization.
if a player can not win in a subgame (when he plays first), the number for him playing first in the subgame is infinity.
For n subgames, i have 2*n numbers (white / black playing first in each subgame).
For the player to move (white), i know he is winning, if the lowest of his numbers for the subgames
is smaller than or equal all numbers for black moving first in one of the other subgames.

Johannes Waldmann at 20090403
Perhaps this helps:
Global Threats in Combinatorial Games: A Computation Model with Applications to Chess Endgames, by Fabian MÃ¤ser, 137149
MSRI Publications – Volume 42.,
More Games of No Chance,
Edited by Richard J. Nowakowski
http://www.msri.org/publications/books/Book42/files/maeser.pdf

ab at 20090403
thanks for the comments …
i think it is possible to prove it without other theories,
which i will try, and post it here

wccanard at 20090403
@ab: I'm not sure combinatorial game theory can help you here: the majority of the theory (in particular the part which attaches numbers to games) is to do with games like amazon where the winner is the last person who can play a legal move on the board (e.g. amazon would be a good example). You are trying to see who wins a race, which is somehow different: those positions are “hot” and combinatorial game theory says less about them. CGT in some sense works best when neither player particularly wants to play anywhere but has to play somewhere.

ab at 20090403
… those positions are “hot” and combinatorial game theory says less about them
CGT in some sense works best when neither player particularly wants to play
anywhere but has to play somewhere.
ahh, that's interesting
i already presumed it is not exactly the right thing for this purpose, and would
not give me answers here; CGT (or one part of it) seems to have been invented
for go endgames (where scores add up), and like you say, zugzwang positions
(one player forced to move) or lastplayertomove loses/wins kind of games.
but anyways it might have been the case, that somebody recognized the simple
theory above as a special case, which can fit into some more general theory
and it would be obvious …
i don't want to read into cgt  and also don't think it's necessary,
(i will try without other theories)

Johannes Waldmann at 20090404
> the majority of the theory
> (in particular the part which attaches numbers to games)
there is no other part of CGT. It *is* the theory of
attaching numbers to games. Of course “numbers” meaning
something more general that integers. Let's say CGTnumber =
symbolic representation (a.k.a. normal form) for a class
of equivalent game positions, where “equivalent” means
“can be replaced in a disjoint sum of games, without changing the outcome”.
The real question in whether CGT can be applied to Havannah
is whether this equivalence relation makes sense
(is the board really a disjoint sum).
At zeroeth sight, yes, because you can play in different parts
of the board. At first sight, no, because it does not look
like a disjoint sum: a win/loss in one part of the game
implies a total win/loss. Taking a closer look, e.g.
in Winning Ways Vol. 2 Chap. 12, this situation can be
sort of modelled by loopy/loony games, where the basic idea is
that if one part of a sum is infinite, then it dominates the finite parts.
I thought MÃ¤ser's paper (cited above) nicely illustrates that.
For a light introduction to CGT (in German),
see some chapters in
Bewersdorff's book: http://www.galoistheorie.de/glb/
and (shameless plug) my lecture notes
http://www.imn.htwkleipzig.de/~waldmann/edu/ancient/ws01/kst/

ab at 20090404
anyways … this would be my proof:
see http://senseis.xmp.net/?Havannah
(section Havannah / subgames)