Havannah: Man vs Machine on size-8-board?

Hello,

more than 2 years ago I had announced that there would be

a Havannah-8 event between strong human(s) and strong bot(s)

in Fall 2015 - during the Long Night of Science in Jena.

Now I learnt that there will not be such a long night in 2015.

Nevertheless I intend to organize the Havannah event if there

are players and programmers willing to participate.

So, please show up.

Cheers, Ingo.

PS. In Summer the next Computer Olympiad will take place

in Leiden (NL), from June 30 und July 04, 2015. Havannah might

be one of the disciplines, if enough programmers show interest.

Thanks Ingo,

I'll announce the Leiden event at mindsports and I'll try to visit the event myself on Saturday the 4th.

I will probably be there, too. Please be sure to track me down if you come!

Sounds interesting!

Still here are some numbers to think about: On last 50 size 8 games Castro makes rating about 1900, and Wanderer and Lajkonik about 1700. Even worse for computers some of us 2000+ players have practiced against Castro at home and are immune against Castro's cluster bombing.

What about size 5 match instead? For instance Peter Koning has scored 10/22 against the three strongest bots (3/6 against Castro, 1/6 against Lajkonik, and  6/10 against Wanderer) on size 5.

@ Richard: I've put it up at mindsports.nl and sure, I'll try to track you and Ingo down :) .

I doubt I (Timo) will be there in person, but I may be able to play remotely, or let someone play Castro in person on my behalf.

Hi TImo,

> I doubt I (Timo) will be there in person, but I may be able to play

> remotely, or let someone play Castro in person on my behalf.

do you mean the  size-8 event in Jena or the Olympiad?

Concerning Jena, I would organize a local operator for Castro.

Cheers, Ingo.

Hi CHristian,

> I’ll announce the Leiden event at mindsports and I’ll try

> to visit the event myself on Saturday the 4th.

thanks for your engagement.

I am not sure if I will be in Leiden still on July 4 (likely

I have to leave already on July 3...).

Anyway, I wouldlike to meet you.

Cheers, Ingo.

Hi Kokosz,

> What about size 5 match instead?

I understand your reasoning. But ...

(i) The size-8 event was announced (by me) years ago.

And I do not want to change horses in the middle of a plan.

(ii) Remember the 2012 Havannah Challenge: Before, almost everybody

was convinced that Christian would win without much effort.  And then

it turned out that the bots had made leaps of progress.

I expect something similar for the size-8 event.

Ingo.

No problem 8 size you go.

One day, two days? How many games do you think?

Okay Timo you've better have some improvements coming, otherwise Castro might get nervous watching this game rocords:

http://www.littlegolem.net/jsp/info/player_game_list.jsp?gtid=havannah&plid=36971

 ;-)

Hi,

I hope to get Mirko Rahn playing for the human side.

If he agrees in principle, Mirko will also be involved in

the details of planning.

Ingo.

Would it not be optimal with say 3 against 3 players? I say 3 because Castro, Lajkonik and Wanderer seem to have a significant lead on the other programs. On human side there could at least be Mirko (reigning champ), Christian (Mr. Havannah him self), and perhaps me or any other 2000+ player.

> Would it not be optimal with say 3 against 3 players? I say 3 because Castro, Lajkonik and

> Wanderer seem to have a significant lead on the other programs.

I am not sure.

I do not want to see an event where the bots have remained on their 2012-levels.

If Havannah will be played in the Computer Olympiad (on 8-board)

we would see how strong they are in the meantime.

And if there will be three (or four) strong programs in the Olympiads

I am willing to allow three (or four) bots in the Jena event.

Ingo.

 I do not want to see an event where the bots have remained on their 2012-levels.

FWIW, Wanderer is already quite different from the 2012 version. Not necessarily better, though.We're trying a somewhat different approach and working under the assumption that sometimes a couple of steps backwards are necessary to ultimately move forward. I think we're still in the moving backwards stage, but are optimistic that we will soon be moving forward again. Just need to find the time....

Some revolution is needed for AI in Havannah. I am currently beating Castro 10/10 on size 8 without much effort (1 minute on each move), and faster time controls are paradoxically beneficial for human players (!!) in opposition to most other games including Hex where I believe many 2000+ players would find it unpleasant playing MoHEx or Wolve with low time controls.

As I mentioned earlier I even believe that humans could match bots on size 5 in live play given proper preparation. What is certain is that for instance Castro has a tendency to play to low on size 5, and Wanderer and Lajkonik have other weaknesses. At least I bet Wanderer quit fast in our last size 5 game.

I've got a few ideas on how to improve Castro, but I've mainly been trying to make Castro (or now Morat) game independent, so it also plays Hex and Y, and potentially other games in the future as well. This has meant taking out some of the havannah specific things I used to do. At some point I might get around to adding some game independent techniques, like patterns, that work well in other games, but I doubt I'll be focusing too much on havannah specifically.

Possibly off topic, but how many people here actually play against castro (or others) not on LG?

Here are my personal opinions on the state of computer Havannah:

• In academia, game research is cultivated in a few universities only, and there are hotter games than Havannah.
  

• The pool of human players is small and so would be the fame of a new bot. A smartphone app based say on Castro could popularize the game. Any volunteers?

• Since the Havannah Challenge, the incentive to develop Havannah bots has diminished a lot. Lajkonik almost has not changed since 2012. Once I submit my small bug fixes, I will open-source it (yes, I know I have been repeating this for years). It would be nice if somebody with more time in their hands took it over. But even Castro attracts no contributors.

• Like Kokosz said, the Monte Carlo Tree Search paradigm appears to have reached the limits of its capabilities. Lajkonik's younger brother Antares might prove that an evaluation function is useful in playing Havannah. But Antares is half-done only, and given my other responsibilities I cannot say if and when it will be ready to play.

I am actually preparing a Havannah paper which I will make available on internet. It will cointain some annotaited Havannah games and thoughts of how you should play "correct" Havannah. I think my goal of reaching 2000 rating within 1 year would not be possible in 4 months without my game training against Castro and Lajkonik. In the beginning I lost heavily against Castro because I was outplayed tactically by its rings. Castro strenghtened my ring play very much, not only am I able to defend properly against bigger ring threats, but my understanding of the ring aspects in the game is much bigger.

It is a paradox that the strongest engine Castro (1900 strengh on size 8) is the engine which plays most distant from humans(!) Often Havannah programmers rely on the assumption that consentrating pieces is very beneficial, and starting new groups is risky at best. Allthough surely practical while implementing the heristics this assumption is, at least in the opening play, contrary to what I believe should be a proper play. Distribute your pieces was already the message of Chinese Go player Huan Tan (ca 50 AD), and if you look through the games of the highly sophisticated player - Maciej Celuch you see how much he distributes his stones in the beginning. For example watch game between Celuch and Halsør: 1009053.

Even on size 5 same principles seems to apply, and you can't play to low either. The following game between Peter Koning and Castro is beatiful: 1275064.

I get the feeling that you (Kokosz) think I (Timo) and the other game programmers are as passionate about Havannah as you and some of the others here are, or that we're invested in the style of play that our programs play. If you want to see castro play completely differently, just run the command 'player_params -G 5' and it will form less rings. If you bump that up even higher and it will almost completely ignore them, though it will become quite vulnerable to ring threats too. If you want castro to play more like wanderer, do 'player_params -e 1 -f 200 -d 0' and it will probably play similarly (though to be clear, I don't know much about the internals of wanderer and haven't actually tested that). The version of castro that plays on LG plays with different parameters than the ones built in to the open source distro.

Overall though, I, and I assume the others too, care more about the more general algorithm than the specific style. Much of my later work was on solving the game, and on making it less interested in rings. Marcin's later work was on playing better random rollouts through pattern matching. As such, I don't actually care whether it plays ring bombs, as long as it plays well. If ring bombs are bad play because they're strategically bad and tacticly neutral, then I should figure out why it does that. It turns out the reason is because RAVE very much favors moves that do well in random rollouts, and rings, while easy to block with good moves, are hard to block with random moves, and they're much easier to form than the other win conditions, especially on larger boards. Marcin tackled this by writing patterns that encourage lajkonik to make better moves (block rings earlier, or generally make other good moves), while I tackled it by claiming rings without a certain number of non-random pieces are not winning in random games. I may someday get around to adding better patterns or even learning patterns. I certainly won't mourn castro's playing style changing, and its playing style is not a reflection of what I think is the best playing style. It is merely the style that won most consistently in self-play against mildly different versions of itself.

You don't care about the bombs Castro is producing but they have actually caused much harm in here, even to strong players. If your program do not get any major role in the Lord of Rings I will be heavily disappointed! :P But of course I am talking generally, and think adding heuristics (patterns) will be important with or without MCTS. I also agree that probably MCTS with many patterns is the way to go in the long run.

I have of course tried out the -G params and I am also familiar with your -G statistics: where roughly -G 4 is best up to size 8, -G 3 is best for size 9, and -G 2 is best for size 10.

I think it is also right to say the your program has enriched both the strategical and tactical understanding of the game. At least I have applied Castro inspired cluster bombing in some games (most notably in 1656535 against Fritzd), and emulated its corner oriented approach on smaller boards.

Why does White win in that game?

Sorry, I refer to the game against Fritzd, and am thinking of the following sort of  line n6 n7 d2 e2 c1 b1 a2

Instead of 34. n7 try 34. k7, with a double ring threat.

Thanks. Now what I'm wondering about...does 31. k7 work for Black?

To answer an earlier question, I do not play against bots off of LG, though I vaguely want to.

It seems it does. White would then need to reach the top in one move (subtracting the ring threats) in order to be ahead, but as far as I can tell cannot do better than two moves and is thus doomed.

Hyperape and Eobllor (1656535 game comments): You are correct that black is winning after 31.k7! For instance: 32.n4 33.m4 34.n6 35.m7 36.m8 37.n7 38.n8 39.d2 40.e2 41.b1 42.c1 43.a2 44.o7 45.o6 46.n9 47.j4 48.n2 49.k1 and black forks one move ahead of white. This game have little value other than cluster bombing emulation which proved to make the game complicated for black (who had initially a winning position).

More strategically interesting game between me and Fritzd is 1670755 where I am successful with play a la Maciej Celuch/Tony against Fritzd's more center oriented approach.