Message from Timo:

“Hi Christian, I'm Timo, the author of Castro, the program that won the computer games tournament in Kanazawa two weeks ago. Castro is now accepting games on all board sizes under the name Castro_bot. I would post to the forums, but I haven't played enough games under either account. Please relay this message to the forum. It is using 2 minutes per move, but on a rather weak machine. Timo”

On a personal note: where do I find Casto if not here?

Main> List of players

Go to its profile page and click on [Send invitation]

Thanks :)

You can see Castro_bot's profile, here.

If you are really, really lazy, just Send an invitation to Castro_bot :)

I've played Castro during the Olympiads in Kanazawa and I found the playing level on size 8 impressive. Let's see how it fares against other players!

How would you player react to having bots participating to the Havannah championship ? I for one am not opposed to such a practice as long as the bot is recognized as such (“_bot” in the name + mention in the profile)

I have no objections to bots, on the contrary. Castro seems to invoke the three rules for playing Chess: carefully, carefully, carefully.

game base-8.

Thanks to Timo for letting castro play here.

Like experienced by Richard (the Wanderer) he

should later use the castro account also for

communicating here in the forum.

Ingo.

Welcome, Timo! Your bot is performing very well. (*)

That is, it gives me nice testcases for debugging Ring-of-Fire…

if I only had the time.

I hope to win the size-4 game but that does not really count:

the interesting criterion is performance on large boards.

I just increased the weight that R-o-F gives to static evaluation

(vs. playouts) - let's see how this works out.

I'm looking forward to many interesting games.

- Johannes.

(*) although naming it after a communist dictator seems somewhat questionable.

In the tradition of the Scheme(LISP) compiler named “Stalin” perhaps?

I can imagine people who don't think this is funny.

Those people might consider it funny if it loses :)

However, that might not be too frequent an occasion. The program is very good indeed and I enjoyed this game against is very much :)

@Christian:

I noticed you were implementing a windmill (around H4) on purpose,

so the game was never really dangerous for you?

Of course such play is still a bit above current bots' heads …

Of those whose names end in “ro”, Castro is arguably the most famous.

@Johannes

It let me. 14 i5 and 16 j3 weren't the best of moves. With 15 c3 I secured the left side, and that strategy would have worked if it hadn't allowed me the double ring threat that gave a forced a tactical win.

Dangerous? My position was precarious enough before 14 and 16. After that there was still ample room for mistakes. Judging from this game the programs performance is quite impressive!

Congratulations to Timo Ewalds, for the strong Havannah bot!

And a question: On which hardware is Castro running right now?

Ingo.

PS: When you are still not allowed to write here, you may put

the answer in Castro's profile.

Thanks!

Right now Castro is running single threaded on an Intel® Pentium® Dual CPU E2140 @ 1.60GHz, using 1gb of ram and 5 minutes per move.

Fantastic show by Taiwanese palyer “derjohng”

against Castro: showing a very effective way

to bet the bot (or evene bots in general?).

See here.

Congratulations to derjohng!

Ingo.

Yes, weak point generally. You can count on RoF missing almost every ring threat. Here Castro could still have won by playing 14 at any adjacent cell and cut the black ring from within.

A program with no consciousness of ring threats per se but only of fully formed rings would need a 12-ply lookahead to see derjohng's threat by move 14. I'm guessing 12 ply would be too much for an alpha-beta program at 5 minutes per move on a size 8 board, and I'm further guessing that Monte Carlo can miss the threat if its lookahead uses random moves. I conclude that some kind of static analysis is needed, noticing ring threats, not just rings.

This is completely speculative and I would welcome comments from anyone who knows what they're talking about.

12 ply lookahead would definitely be too much for alpha-beta. Even if 12 ply were doable for purely proving a win/loss, it would give no indication of which move to make in most cases. The static evaluation functions I've played with, and that Johan was using in Kanazawa are way too slow, and neither of ours take rings into account…

Monte carlo does have a better chance than alpha-beta, especially if it uses some heuristics or patterns. This is a tough case though, since it has no short term threats to guide it. Most of the time a win has short wins that can be blocked, that inevitably lead to a long win, but that let you know which area of the board to focus on. This case has only 1 single escape, 12 ply early…

Given 60 seconds on my laptop (so slower machine and less time), it can find the win if it's playing black with 3 moves left in the big ring, but doesn't find the loss if it's playing white with 3 moves left in the big ring.

Do any of the programs have consciousness of any (not just ring) threats more than 1 or 2 moves ahead? Given that there are multiple win conditions, none of the hex dead cell analysis works, and the virtual connection analysis doesn't work well. That analysis would have major trouble working on rings even if there was no conflict between the different win conditions. With these multiple win conditions it is often a good idea to give up one frame to gain a shorter one, so frames are misleading or fragile.

When making move 12, a human White would notice Black's ring threat. I think all that's needed is to recognize bridges.

I don't know about Havannah programs, but Hex programs recognize “virtual connections” defined as connections between two chains of already connected stones that cannot be prevented even if the defender makes the first move in the area in question. The bridge is the simplest template.

Some of the Hex templates don't work in Havannah when the defender's blocking move can be made simultaneously a ring threat.

In Hex, virtual connections are guaranteed connections, assuming you choose to defend them, but there is never any reason to not defend them. In Havannah, they are not guaranteed. Frames are often broken, like in the game against Christian Freeling, or could be broken like in this game. A frame that can't be broken is also not necessarily a winning formation, since it could be too slow. It's also not obvious how to use a partial frame, since it could be used in many different ways but with different speeds or certainties.

There are several examples of games where the opponent had a guaranteed win in 2 while Castro was about 10 moves away from a win and without a good frame, but Castro still won by using 9 forcing moves.

Castro does recognize the bridge virtual connection, and is encouraged to maintain them, both in the tree and in the rollouts. It can't be forced to maintain them though, since there may be more important moves elsewhere, like if this virtual connection is now in a dead area. Even when it is encouraged to maintain the virtual connection and when there is a frame, it is tough to see it since the frame may not succeed in a rollout because some other winning formation could happen first. Finding the specific move to refute the frame is even harder given random rollouts.

The current size-4 tournament is a nice source of income (rating points) for the bots, no? (e.g., R-o-F is at 1400 again, whoo-hoo) Which in turn can boost human player's ratings (just avoid the size-4 tournament, and play the bots on size-8 or larger…)

Christian is absolutely right: “You can count on RoF missing almost every ring threat.” I find it hard to come up with a global ring threat detection.

(While it's easy to detect bridges/forks by computing some shortest paths.)

Even if we had all the information, it is hard to combine it,

for reasons that Timo mentioned above. Still I think that's where

Combinatory Game Theory should be applied. (The value of a threat

is not just a number (you cannot easily add or subtract or compare)

but it sure should fulfill some axioms (computational laws),

and there should be a more efficient representation than the full game tree.

The problem is that CGT is mostly built around the concept of “disjoint sum”,

(and if you win/lose one sub-game, you continue to play in another).

In connection games, we have a different kind of sum

(if you win/lose one sub-game, the effect is global).

Are there any suggestions on how CGT might treat this?

This looks nice (just judging by the title) “Global threats

in Combinatorial Games” but I don't really see how to apply it:

http://library.msri.org/books/Book42/files/maeser.pdf

Anyway I don't really have time to work on that now.

I keep R-o-F running and try to make the occasional patch.

Since it's currently easy to beat on larger boards,

I might withdraw it from rated games. (I don't care,

but other players might think it skews ratings of its opponents.

But then, if your rating is high, you don't get much out of

beating a weak bot.) Is there a way to find out whether an incoming challenge

is for a rated game or not?

Best - Johannes.

> … Christian is absolutely right: “You can count on RoF missing

> almost every ring threat.”

Hi Johannes,

when you realize a version better on rings, you may call

it “RingsOnFire” ;-) (or “RingsUnderFire”)

Ingo.

Has anyone tried using Lambda Search? It seems to be a generalized search for threats, which is fundamentally what a frame is.

I have no idea whether it is useful. I looked at it once and while trying to understand it,

i wrote the article about it at senseis.xmp.net. For improving the strength of your program you need to

somehow “focus” your search.

But if this is the right way, i don't know - its usefulness *may* be limited to some endgame situations

or for use in a solver (i.e. not for general game-play).

On the other hand it can read ladders, which is definitely useful earlier in the game (but you can implement that in a simpler way).

About null-moves i don't know so much, i guess Richard Pijl is the expert here (chess engines) …

I was doing some experiments with following ladders

inside the playouts. Looked promising, but since I was

changing a lot of things in the program at the same time

(yes, one should never do that), I cannot be sure.

I will re-activate the ladder code (re-compiling as we speak …).

A “ladder” is just a triangle of pairwise adjacent stones,

two of the same colour, and a “ladder extension” is a move

of the other colour that completes it to a rhomboid.

I am using null moves: in each (fresh) node, do a pass move

and then some playouts and evaluate them for AMAF

(where would the other player want to play).

Yes, I have not forgotten to open-source R-o-F.

I even started to clean up the mess of C code it contains.

One of the strengths of Castro is that it does solve the game position as it goes. In the early stages this is only useful for avoiding blunders, but in the late game it really does help dominate. If I can make the solver stronger during the early game it helps avoid more blunders, focusing my search on the parts of the tree that are actually relevant.

One thing I'm trying to figure out is if I can use something similar to lambda search to find frames. If I can solve a position after a null move or two as a loss, then I better play somewhere that either makes me win quicker or helps me avoid that loss. Lambda search seems to be the way to do that for Go (and Chess?) but I'm not sure how to apply it here.