This is a thread concerning my challenge as discussed in General forum: When…, in particular Ingo Althofer's post where he states:

_What do you think of the following setup?

A computer-computer qualifying tournament in Havannah (on 10-boards) in the first half of 2012. The winner would get the right to challenge you

for the 10 games (to be played in the second half of 2012), for instance with one game every 2 weeks. The right of the first move should be switched

from game to game. In case of several “almost winners” in the computer

tournament (for instance: the tournament is played as a double round robin and the top three participants score 1-1 against each other) each of them may play some of the ten games (and I would guarantee the 1,000 Euro for you in case of your 10-0 win).

…

Would 3 hours in total for the whole game and each side be ok with you?

…

I think, indeed play via internet might be the best solution._

My answer is yes, I'd love to play, and I particularly appreciate Ingo's offer to put 1000 euro's at stake, should the computerprogram beat me even once in a ten game match. We argee on a base-10 board, alternating first move and no swap rule.

I don't need 3 hours per game. I suggest one hour per player for the first thirty moves. Many base-10 games have ended even before that. After 30 moves within the time limit, some usual regulation should take effect.

I don't need two weeks per game either. I'm playing 54 base-8 games right now, and occasionally look at a position longer than a few seconds. But only occasionally.

I think we all agree that there should be as much publicity as possible. If anyone has any suggestion which Games Manufacturer might be interested in producing the game alongside the event, please let me know. The original manufacturers, Ravensburger, weren't interested a couple of years ago.

At the first launch, in 1981, no-one knew how to play the game. That's different now, because there are quite a few strong players and the game has made its name and its claim to fame, especially in the light of a catchy question - the touch stone of game programming? - surrounding the event.

I'm still confident that I can win all ten games. As can be read in Johannes Waldmann's havannah site about the program featured there:

“It behaves rather stupid - so the challenge is: how often can you 'pass' (at the beginning) and still win?“

I don't fear the Monte-Carlo extension for reasons that I'm in no hurry to express right now.

My point is: I'm all for it! I think we can forget about AGM because they seem to have ceased to exist, on the web at least. But I would welcome any serious contribution in terms of publicity and/or organization.

christian freeling

Did you address Ingo's concerns that he'd spend hundreds if not thousands of man-hours on designing a program and then that you would pull out when it came to the crunch, citing some excuse, and he wouldn't get his money?

I didn't because that concern is unfouded. What possible motive could I have? I'm very interested in the advances in havannah programming and any publicity would be in the game's interest as well as mine. So rest assured: barring the grim reaper I'll be ready :)

“What possible motive could I have?”

Umm…fear of losing E1000?

There are rumours that there is at least one more team (besides Ingo and students) making a havannah playing program…

I will reply to Christian's original posting soon.

One question for the meamtime:

What is known about Havannah on boards

of base-4, base-5, base-6, and base-7?

Ingo.

Base-4 might not be to difficult a win for the first player, but I never made a serious attempt. In general, on odd-numered boards, the side-diagonal intersects the perpendicular main-diagonal in a cell, on even-numbered ones in between two cells.

This may give rise to a diffent kind of corner play resulting from usual openings, in particular where bridge threats are part of the equation.

christian

Hello Christian,

Christian Freeling in the original posting:

> …

> My answer is yes, I'd love to play, and I

> particularly appreciate Ingo's offer to put

> 1000 euro's at stake, should the computerprogram

> beat me even once in a ten game match.

Sorry, I did NOT make such a statement.

What I wrote (and mean) is the following:

Should the 10-game match happen not between you

and a single program, but instead between you

and a group of several programs (each of them playing

some of the 10 games) then I would guarantee that you

get 1,000 Euro in case of a 10-0 win by you.

(The reason for my proposal is to make sure that you

would not have to run around and collect multiples of

100 Euro from several participants.)

By the way: You did not say anything on my idea

that you might play against a team of programs.

> We agree on a base-10 board, alternating first move

> and no swap rule.

Right.

> I don't need 3 hours per game.

Nobody urges you to use all the three hours.

But for the computers it would definitely make

a difference to have 3 hours instead of 1 only.

A proposal for compromise might be:

2 hours for the first 30 moves for each side,

and one additional hour for the remaining moves.

> I don't need two weeks per game either. I'm

> playing 54 base-8 games right now, and occasionally

> look at a position longer than a few seconds. But

> only occasionally.

For a programming team, a slow rhythm would increase

the chances to learn something from a game and to improve

before the next game.

An advantage for you: a slow rhythm would keep the competition

and thus your game in the public for a longer period.

> I think we all agree that there should be as much publicity

> as possible.

From the programmers side: not necessarily. The first target

would be to get a fair chance for getting the prize.

No problem when you make big PR around such a match.

> If anyone has any suggestion which Games Manufacturer

> might be interested in producing the game alongside

> the event, please let me know.

I can understand that you are interested in that direction

and I wish you good luck - but a new production of “Havannah”

by a company should NOT directly be coupled with a 10-game match.

> … of a catchy question - the touch stone of game

> programming? - surrounding the event.

I do not like such a slogan. Havannah is a nice game

and is not easy to be programmed. But the most I would accept

is a term like “a touch stone of game programming”.

(So, “a” instead of “the”. Games like Go and Hex are more important

touch stones.)

> I'm still confident that I can win all ten games.

> As can be read in Johannes Waldmann's havannah site

> about the program featured there:

>

> “It behaves rather stupid - so the challenge is:

> how often can you 'pass' (at the beginning) and still win?”

That is at typical Waldmann comment.

> My point is: I'm all for it! I think we can forget

> about AGM because they seem to have ceased to exist,

Who is AGM, and why should AGM be related with a

10-games match? Have there been any contracts between them and you?

Ingo Althofer.

“Sorry, I did NOT make such a statement.“

I'm the one who should apologize here, I misread your offer.

_“What I wrote (and mean) is the following:

Should the 10-game match happen not between you

and a single program, but instead between you

and a group of several programs (each of them playing

some of the 10 games) then I would guarantee that you

get 1,000 Euro in case of a 10-0 win by you.“_

I appreciate it nevertheless :)

I don't care to play against more than one program anymore than to one or more opponent's (actually I prefer multiple human opponent's because of the different approaches).

_“A proposal for compromise might be:

2 hours for the first 30 moves for each side,

and one additional hour for the remaining moves.

…

For a programming team, a slow rhythm would increase

the chances to learn something from a game and to improve

before the next game.

An advantage for you: a slow rhythm would keep the competition

and thus your game in the public for a longer period.“_

That's true, please allow me some time to think about it.

“But a new production of “Havannah” by a company should NOT directly be coupled with a 10-game match.“

So there can be no sponsors for such an event?

_“But the most I would accept is a term like “a touch stone of game programming”.

(So, “a” instead of “the”. Games like Go and Hex are more important touch stones.)”

Well it was worth a try wasn't it :). I'm perfectly happy with “a touchstone”.

AGM are “Abstract Games Magazine”, (http://abstractgamesmagazine.com/) founded by Connie & Kerry Handscomb, but the server cannot be found anymore. The challenge was first published by them in the summer of 2002 and to be held under AGM auspices, but there had already been some gaps in the publication of the magazine before it disappeared altogether.

christian_

… in the light of a catchy question - the touch stone of game programming? - surrounding the event.

_I do not like such a slogan. Havannah is a nice game and is not easy to be programmed. But the most I would accept is a term like “a touch stone of game programming”.

(So, “a” instead of “the”. Games like Go and Hex are more important touch stones.)_

Just to clarify, I proposed it as a question, not as a statement. About Go and Hex - Go has 'territory' and 'capture' as handles to tackle evaluation, and Hex has, in a way, a 'general direction'. All of that is missing in havannah, doesn't that complicate evaluation?

christian

Go and Hex have monte carlo. Havannah doesn't have any such techniques (which are useful). So the question is a good one to ask.

doesn't have? or haven't been discovered yet?

quite a difference, imho.

Go concepts such as sente, atari, ladder, territory etc. can be applied, without much change, to evaluate Havannah board configurations. I don't see why Monte Carlo won't work for Havannah as well as Go on small boards.

About Monte Carlo: In Go, advantages for one side or the other 'shine through' in a set of say 100.000 random progressions from a certain evaluated position. That's because points can be scored locally all over the board. That's why MC gives a relatively high degree of reliability in Go.

In havannah local advantages don't add up because you cannot 'accumulate' them locally.

I had a long and very interesting game against Bill Collins:

http://www.littlegolem.net/jsp/game/game.jsp?gid=987970

Bill takes the lower right corner at move 24 and the bottom corner at move 40. I let him because I had other priorities, and could move these because I had worked out the narrowest of escapes.

Random progressions after move 40 would have rendered 98% wins for white because of a fast bridge. That would have been bad advice.

christian

Doesn't have them yet (edit).

The problem with Monte Carlo in havannah is that the other player can create a faster frame. Thus winning (even if you have a frame earlier then him).

I'm not saying it won't work. But it won't be as effective as MC Go.

I must correct the “98%” because that's very unlikely given the number of 'random closures' at the critical connection point after move 40. What I meant is that given the nature of these outcomes, the 'accidental bridge rate' would be suggestively high, and even seasoned human players like Bill 'take the bait'. So the move would be grossly overrated by MC methods.

christian

I don't believe in Monte Carlo's usefulness to havannah. I've read about MC approach in amazons - the results were unconvincing.

MC is great in stochastic games, I used it myself in scrabble program and it worked like a charm.

Maybe TD-learning might be used (like in TD-gammon) or evaluation function tuning with linear regression (see Logistello).

Perhaps in 2012 we will find out which method is better :-)

Go is not stochastic, but it is useful there. I think that's because computers in Go are good at narrowing down possible moves to those that are tactically sound but poor at choosing among those that are sound. The question is whether in Havannah a MC program will be able to narrow the set of possible moves enough.

“I've read about MC approach in amazons - the results were unconvincing.”

Well, given that a MC hybrid program won the 2008 computer olympiad in Amazons, I would say that's fairly convincing evidence of its usefulness.

http://www.grappa.univ-lille3.fr/icga/tournament.php?id=183

From Invader's page info page at ICGA: “MC/UCT hybrid version of old Invader”

The MC version is available for download, and from my attempts at playing against it, seems very strong - at least if given sufficient thinking time.

I would expect MC to be usefull in Amazons because, as in Go, the advantages sought are spread all over the board and accumulative. That's what allows them to 'shine through' in a massive set of random progressions from a certain eveluated position. No such accumulation in havannah: you cannot 'gain points' for advantages in local situations, you simply win or lose.

In havannah the evaluation functions have till now been far from impressive. Putting an MC method on top of them is not devoid of optimism, but I'm not sure about realism.

In Go, one either wins or loses, and the counting mechanism is explicit in the rules. In Amazons, one wither wins or loses and the counting mechanism is _not explicit in the rules, but is obvious. In chess, one either wins or loses and there's no inherently obvious counting of anything, but players have ascertained both material and other advantages that may be counted in the absence of a calculable forced win.

I see no reason to conclude that no such chess-like advantages will be discovered in Havannah, though the fact that they haven't been discovered yet may make Monte Carlo algorithms ineffective now,_ even if they eventurally prove useful.

1) i thought that Invader uses UCT mainly. i still think so. (its even mentioned on Lorentz' page. anyway, maybe i'm wrong :-)

2) i believe that top LG players would beat Invader easily. (i could be wrong…)

3) i'll write havannah program and compare different approaches, and say something more conclusive. now its the subject of speculation.

@ P.D:

> 1) i thought that Invader uses UCT mainly. i still think so.

> (its even mentioned on Lorentz' page. anyway, maybe i'm wrong :-)

You are indeed wrong. Details of MC-Invader are given for instance

in the paper of the Lorentz group at CG-2008.

> 2) i believe that top LG players would beat Invader easily.

> (i could be wrong…)

You should be wrong for “over the board conditions”, for instance

with 60 minutes for the whole game.

> 3) i'll write havannah program and compare different approaches,

Very good plan.

One proposal: Concentrate on small boards (side lengths 4, 5, 6),

until your best approaches are really strong there.

Ingo.

“1) i thought that Invader uses UCT mainly. i still think so. (its even mentioned on Lorentz' page. anyway, maybe i'm wrong :-)”

… UCT (“Upper Confidence Bounds Applied to Trees”) is a form of MCTS (“Monte Carlo Tree Search”) - Monte Carlo simulations are an integral part of using UCT. If you want more details, I would suggest the Go pages at http://senseis.xmp.net/?MonteCarlo as a good starting point, and with much more information available in the Computer Go mailing list archives http://computer-go.org/pipermail/computer-go/

As for how strong it is - if any of the top LG players would like to, I would be happy to run Invader at long thinking times in an unrated game against him/her, and we could see how it goes.

(My apologies to Christian Freeling for derailing this thread - perhaps we should start a new thread in the Amazons forum if we want to continue this discussion about MC/UCT applied to Amazons and the strength of Invader / setting up a match against a top player.)

I don't think you're derailing the thread because the idea is to apply MC to havannah and I for one am curious about that. Being no expert I welcome all contributions that benefit the little insight I have in the matter :)

I've set up an open Amazon challenge in the waiting room - so if any strong Amazon player want to try it out, please go ahead :)

Call me a fool, but i was lost here when 'monte carlo' came up. What's that mean?

http://en.wikipedia.org/wiki/Monte_carlo

;-)

Also, look at http://en.wikipedia.org/wiki/Computer_Go - that has a section on monte carlo as applied to Go. Excerpts:

“One major alternative to using hand-coded knowledge and searches is the use of Monte-Carlo methods. This is done by generating a list of potential moves, and for each move playing out thousands of games at random on the resulting board. The move which leads to the best set of random games for the current player is chosen as the best move.

[…]

The result of this are programs which are strong in an overall strategic sense, but are weak tactically.

[…]

In 2006, a new search technique, upper confidence bounds applied to trees (UCT), was developed and applied to many 9x9 Monte-Carlo Go programs with excellent results. UCT uses the results of the play outs collected so far to guide the search along the more successful lines of play, while still allowing alternative lines to be explored.”

so… 'try out, see what works'?

Here's my understanding of the idea. One way to write a computer program to play a game is like this: you first choose a good “evaluation function”, i.e. a function which, given a position, returns a number, and a the bigger the number is, the better that we *think* the position is for you. And now here's how you could play a game, we could look at every single position that the board is in after, say, 5 moves have been played, and then work out the numbers for each of these positions, and then try to figure out how to steer best towards the big numbers and avoid the small ones. This procedure is called “minimax” and it's a very common way to play.

The problem with minimax is that, for a nice complicated game, an evaluation function that can be worked out very quickly, might not give a very accurate result (it might return a big number in a position that is lousy, because the programmer placed too much importance on some aspect of the position that turns out not to be the important aspect). On the other hand, writing a really really good evaluation function (for example the function which just plays all possibilities for the rest of the game and works out who has won) might, in practice, run much too slowly to be useful. The art in this situation is to get a good quick evaluation function. Sometimes it's hard to even think of an evaluation function, because perhaps a human has a “feeling”, but a computer needs an *algorithm*.

But here's a completely different approach: after each of your possible moves, just play the rest of the game *completely randomly* and work out who won. A computer should be able to do this _really quickly_. So, try it a million times. If we win 900,000 of them, then **in some sense** this line has a “90 percent chance of winning”, so that's another way of suggesting a good move. For *some* games this method might work much better than the minimax idea. But for others it won't work as well. It's a rather subtle question to say which is the best thing to do. minimax depends to a large extent on how good the evaluation function is. But monte-carlo will depend on in some sense the underlying nature of the game. For example if a computer is considering a move for which a human can spot the unique winning reply easily, and the unique winning reply easily wins for the human in all lines, and all other moves easily win for the computer in all lines, then monte-carlo will get confused because “on average” this move looks like it's good for the computer, but it's not.

wccanard wrote:

> But here's a completely different approach: after

> each of your possible moves, just play the rest of

> the game *completely randomly* and work out who won.

Hello wccanard,

thx for your very nice explanations on Monte-Carlo (within

the framework of computer game tree search).

Let me add some more bits:

\* Doing “completely random” playouts is only one possible

branch in Monte-Carlo evaluations of game positions.

Already in the very first technical report (by B.Bruegmann,

1993) playouts driven by heuristics were used.

\* My view is that “Monte Carlo” is one possible case of

“indirect evaluations”. These can be done (as said) by

- completely random playouts

- playouts driven by (probabilistic) heuristics

- semi-playouts (so only half a game or even only some moves are

generated; good examples for these are Sheppards Scrabble

programs Richard Lorentz' Invader in Amazons)

- others (for instance also mixtures of minimax and Monte-Carlo).

Alreay in the late 1980's I had been investigating “incremental

algorithms” theoretically; there exists a paper in

Artificial Intelligence Journal 43 (1990), 57-65; entitled

“An Incremental Negamax Algorithm”. Later I generalized that

procedure to trees (not only game trees) with arbitrary recursive values).

I expect more indirect methods of evaluation in game trees to come

in the forseeable future.

Ingo.

I'm very grateful for clarification about UCT.

Can anyone here have access to “Amazons Discover Monte-Carlo” paper? I'd really appreciate if someone could send it to me(drochom@gmail.com).

BTW I'm working on amazons program and hope to participate in Pamplona (computer olympiad) this year. I haven't chosen searching technic yet (I prefer simple k-selective search [try best k moves]). I'm focused on tuning the evaluation function mainly.

Speaking about computer olympiads, havannah isn't listed there. But could be. It would be really exciting to fight against other programs during such an event. :-)

“It would be really exciting to fight against other programs during such an event. :-)”

Not to mention hilarious ;-)

@Przemek

http://www.springerlink.com/index/r633g77g37287750.pdf

Good luck!

@Przemek:

\\\* On Amazons ***

You should simply contact Richard Lorentz via email.

He is happy about everyone joining the Computer Amazons

tournament scene.

\\\* On Havannah ***

I think there would be a good chance that Havannah is

included in the Computer Olympiads when there are at least

three programs who intend to participate.

It should not be a problem at all when 2010 is intended for a start.

But even 2009 (Pamplona) might be possible when a trio (or more)

contacts the main organizer (Prof. Jaap van den Herik) soon.

My proposal, concerning board size: start with something small -

like sidelength 6 - to get at least some “beautiful” moments.

Ingo.

It would be wonderful to see Jaap van den Herik involved! I hope there's a sufficient number of entries.

@Ingo

Thanks. I'll contact him.

@Ingo

How about two hours each for the first 40 moves?

I've contacted the games club Fanaat (Fanatic) at the University of Twente, where the game was first introduced in the late seventies, to facilitate the match at my side with a room and a video link. The executive committee will consider the matter at their next meeting.

The university is at some 3 miles from where I live, which is ideal, considering I can't leave my animals in the care of others.

There's now a provisional agreement with the executive committe to have Fanaat facilitate the 2012 event at my side.

Christian, what sorts of animals do you keep?

Four raccoon dogs, a white couple - Max & Misty - and two sons, Woolfie & Timur. Here I am with Timur.

Then I've got a twelve-foot burmese python, a husky and a cat.

P.S. The burmese in the Max & Misty site is not Kobus.

This is Kobus.

On 2009-01-20 Hansson suggested: “As for how strong it is - if any of the top LG players would like to, I would be happy to run Invader at long thinking times in an unrated game against him/her, and we could see how it goes.” Did such a game ever take place? I'd like to hear how it turned out. If not, I'd also be happy to do it. When preparing for the CG2008 conference I joined an Amazons ladder on ItsYourTurn and had Invader make all the moves for me. I would let it think for about 15 minutes per move (about how long it would take to chew up about a gig of RAM) and ended up playing around 10 games. Invader won every game and wound up at the top of the ladder.

http://www.littlegolem.net/jsp/game/game.jsp?gid=990067 is the game in question… it is progressing a bit slowly as I am currently travelling, but Invader thinks it has a very clear advantage.

Admittedly less far off topic than burmese pythons :)

Ola, why didn't you make a new account for Invader?

It would be easier for us to know which games are yours and which are Invader's.

You could also set her (him, it?) play at rated games so she can face more strong opponents.

ypercube: Because I wasn't planning on doing more than one or two games. Setting up a new account and playing enough rated games for Invader to reach its correct rating level would take up too much time for me. If I were to spend time running a bot account, I'd rather do it for a bot I've programmed myself - I am considering writing one for Breakthrough.

@Ola Mikael

Why not Havannah? That's what this thread is supposed to be about.

There are no good havannah programs yet.

MartinR's Bot plays quite well.

Invader is really strong in amazon, somehow I still believe that top humans would beat it rather effortlessly.

I think MartinR's bot is not yet a bot, but a player learning the game to EVENTUALLY make a bot, but I could be wrong…

I have to admit, shamefully, that I have lost a game to Martin's (not yet) bot…

I edited my profile pays. So no-one gets confused anymore. My real bot only plays random moves. This week I'll work in it again.

pays -> page

If there is interest I could create an Invader account and keep a couple of games going.

yes

To post something that actually relates to the subject of this thread, a paper on havannah programming will be presented at the 12th Advances in Computer Games Conference, chaired by Prof. Jaap van den Herik. The paper will be presented by Prof. Dr. Johannes Waldmann (here announced with his permission), who places havannah 'between Hex and Go':

_“This game combines the themes of connection and capture (surrounding

> territory), thus it is somewhere between Hex and Go.“_

(Well, the paper will be submitted to this conference.

Whether it will be accepted and presented

depends on the decision made by the program committee.

This is the usual procedure.)

Back on topic -

Havannah's similarity to Hex is “connection” and “sudden death”,

but the difference is “capture”, which links Havannah to Go.

But we still have “sudden death” so it is rather like

“atari Go” (the player who captures first - wins.

That is, you have to answer all atari moves, hence the name.

Sometimes this is used when teaching Go to absolute beginners.)

So, “sudden death” is an interesting challenge for applying the MC method.

(BTW, are there any publications on MC programs for “sudden death” games?)

Does anyone know if there's a similar bet for TwixT bots?

Nope, I've never read of anything about any kind of a challenge or a bet for the first person to write a decent Twixt bot.

You're probably aware that Alex Randolph, the inventor of TwixT, died several years ago.