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)

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.

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 non-credible 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.

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.htwk-leipzig.de/~waldmann/draft/havannah/

Although the paper focuses on simulations.

(That's a nice excuse for my bot playing so bad…)

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.

Perhaps this helps:

Global Threats in Combinatorial Games: A Computation Model with Applications to Chess Endgames, by Fabian Mäser, 137-149

MSRI Publications – Volume 42.,

More Games of No Chance,

Edited by Richard J. Nowakowski

http://www.msri.org/publications/books/Book42/files/maeser.pdf

thanks for the comments …

i think it is possible to prove it without other theories,

which i will try, and post it here

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

… 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 last-player-to-move 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)

> 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 CGT-number =

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.galois-theorie.de/glb/

and (shameless plug) my lecture notes

http://www.imn.htwk-leipzig.de/~waldmann/edu/ancient/ws01/kst/

anyways … this would be my proof:

see http://senseis.xmp.net/?Havannah

(section Havannah / subgames)