Where are the real bots?

Can someone please shed some light on why there are currently no real bots playing Havannah?

I can't say that I'm bothered by Ring of Fire, because a game against it takes as long as it takes to form a 7-stone ringframe.

But what's the point of entering a bot with a 1291 rating and a known bug, I wonder?

And what's the point of withdrawing all the real bots?

Christian,

you should not make such a comment.

Science sometimes is going strange ways,

and people from outside (like you) do not

understand the motivation.

Simply wait until late 2012: the bots

will pull off your undertrousers early

enough ;-)

Ingo.

Hi Ingo,

I'm not sure what you mean by 'such comment', presumably that I'm implying that RoF is not a real bot.

My apologies.

But to have me 'simply wait' lacks symmetry: the programmers can study my games, but I can't study their progression. Instead I'm confronted with a real bot that has a rating of 1291 and doesn't recognize simple ring threats. That's a fact. I hope I'm allowed to state facts here. I won't speculate on the motivation, unworthy as I am to understand the strange ways of science.

Hello Christian,

> to have me 'simply wait' lacks symmetry: the programmers

> can study my games, but I can't study their progression.

Right. But there is no reason why there has to be symmetry.

You made your offer (in 2002) that no bot will beat you in a

single game (out of ten games) within ten years.

No programmer - at any time - made a public announcement that

(s)he will give you sparring time before such a match.

Ingo

You're perfectly right. And I appreciate Ring of Fire being the exception.

christian

Let me try to briefly explain where Wanderer has been. I took Wanderer off line just before I was about to make some changes that I was "certain" would make him stronger. (I want to say I did that some time in September, but looking at the game records the last game I see is in June. Has Wanderer really been off line that long?) I figured I wanted to start the new Wanderer off with all new games.

I made those changes, started up some self test runs, and smugly sat back waiting to see the new Wanderer trounce the old. It didn't happen. I adjusted, fiddled, tweaked, rewrote, debugged and nothing I did improved Wanderer and many things that "should have" improved him actually made him worse.

It was just about this time that I took off for the Olympiad. (That's why I thought I took Wanderer off line in early September.) Hoping to get recharged with lots of new ideas from the Olympiad and the concurrent CG2010 conference I planned to get started on Wanderer again soon after my return in early October. But then my real job got in the way. I was behind in classes. Grading to catch up on. Lectures to prepare. And some ideas to try that were immediately applicable to my Amazons program, Invader, all put Wanderer on the back burner.

The semester is now winding down, I'm burning out on Invader ideas (don't ask how productive those were :( ) and I'm planning to get back to Wanderer very soon. If all goes well some version -- and hopefully an incrementally better one, but history indicates there is no guarantee there! -- will appear either before or slightly after the start of the New Year.

We're after you, Christian, and we've by no means given up. :)

-Richard

"We're after you, Christian, and we've by no means given up. :)"

Gladly accepted and I wasn't concerned so much about you or Timo. I was just wondering why only a crippled bot - if I'm allowed to say as much - was dwelling the premises, while all serious ones had disappeared.

Fortunately Castro is up and running and I'm anticipating playing against Wanderer. I'm so saddened by RoF because it seems to have been tampered down on purpose.

@Althofer

_"you should not make such a comment.

Science sometimes is going strange ways, and people from outside (like you) do not understand the motivation.

Simply wait until late 2012: the bots will pull off your undertrousers early enough" ;-)_

2010-12-12 SYSTEM Game #1274949 is finished. Castro_bot vs. christian freeling 0:2

2010-12-12 SYSTEM Game #1274947 is finished. christian freeling vs. Castro_bot 2:0

2010-12-12 SYSTEM Game #1274948 is finished. christian freeling vs. Castro_bot 2:0

2010-12-12 SYSTEM Game #1274946 is finished. Castro_bot vs. christian freeling 0:2

Castro is far better, strategically, than the German bots.

And please leave my undertrousers out of it. I've had posters from inside a university (like you), at another forum, proceed inside them to facilitate more explicit insults, and we don't want to go the downward slope here.

> 2010-12-12 SYSTEM Game #1274949 is finished. Castro_bot vs. christian freeling 0:2

> 2010-12-12 SYSTEM Game #1274947 is finished. christian freeling vs. Castro_bot 2:0

> 2010-12-12 SYSTEM Game #1274948 is finished. christian freeling vs. Castro_bot 2:0

> 2010-12-12 SYSTEM Game #1274946 is finished. Castro_bot vs. christian freeling 0:2

Ok, four free sparring units. Thanks for them.

Ingo.

PS: Would "overtrousers" be fine?

Hi Christian,

> Castro is far better, strategically, than the German bots.

One more explanations on this. You are likely speaking

about the Leipzig bots. Of course, Leipzig is in Germany.

But more concrete, it is in Saxonia. There are other regions

in our country where harder bots are breeded.

Ingo.

"There are other regions in our country where harder bots are breeded."

Jawohl, hart wie Krupp stahl!

"You are likely speaking about the Leipzig bots."

'Ring von Fehler'? No, I consider that a parody.

Whoa guys, take it easy.

Indeed I am changing Ring-von-Fehler (nice idea for a name, thanks Christian)

sporadically (because I don't have much time) and drastically (see below),

and I'm glad that Castro is available for testing.

Of course I could test against other R-o-F versions,

but having an independent opponent seems much better.

The changes are basically in the direction of using UCT, but not MC

(no playouts, just static evaluation) but obviously it's not quite working

at the moment. Ingo says it, science is going strange ways.

The motivation is that a paper that describes a new or radical approach

is (hopefully) more likely to get considered/accepted for publication

than a paper that just describes fine-tuning of well-known approaches

(no matter how hard that fine-tuning actually is).

Gambler has been away for a while as well, and I had similar reasons for it as the other Richard: Too busy with other things, in my case my chess program (The Baron). I don't have a spare machine for playing here, so whenever I need the computer for other purposes I have to stop playing Havannah games.

Currently I'm working through my todo-list for The Baron and considering the length of that list (which includes rewriting major parts of it), it will probably take until february or so before I'm taking up Gambler again.

Just like Johannes I (independent from him) decided to drop the MC playouts in favor of a static evaluation but it is clear that a lot of work needs to be done in making the evaluation more efficient making more use of the gathered knowledge in pre-weighting the moves in the search nodes (much like the acceleration of scoring that RAVE does, but based on evaluation findings).

In addition to that: Rings were never a strength of programs (except for the compact multiple ring threats) but it seems Gambler and RoF are (due to the reduced search depth reached) more vulnerable to this than plain MCTS programs. That is something that needs to be fixed (obviously) as well.

So in short: I'm not hiding Gambler from anyone, there has just not been any progress and I needed the computer it is running on for other purposes. But it will be back, although it may take a couple of months before it does...

Hmm, I'm glad I ruffled some feathers. Turning away from MC is a trend I hadn't noticed, but you wouldn't do it if MC was all halleluja, so it obviously isn't. I still saw it as a last rope and last hope.

My interest is what humans do when they play havannah just as much as what they do when catching a ball. It must be calculation, but it's fast and effortless and it certainly doesn't feel like calculating (at least not with the ball, and most of the time not with havannah either).

Eventually bots will probably beat humans at havannah (though nothing is certain nowadays, we may have ceased to extist 'eventually'). The only interesting question would seem whether this sheds new light on the workings of the human mind.

In my opinion, what humans do is an evaluation of the current position, determining the correct strategy to follow. Then a move is selected (perhaps 2 or 3) that will support the strategy and a deep and (very) narrow search is done to verify the validity of the plan. When satisfactory, the move is played, otherwise another plan/move is selected.

In MCTS there is no evaluation to guide selecting a move. Instead all kinds of moves are tried in a more or less random way to find a move that seems to promise more than another, but the algorithm does not present you with a why. In my experience this method is very weak in finding forced moves, especially when that move is part of a sequence of moves (like the 6 stone ring pseudo-frames). Programs have been enhanced to detect the simple forced moves (immediate win/loss threats), but when the forced line is more than a few moves deep, MCTS based programs will have difficulty in finding this line and are likely to play a different move that will e.g. pose a tactical threat (small ring) or continues building on a bridge or fork. Also the pointless attacking of frames is part of the nature of MCTS as there is a chance that the opponent will not defend the frame ...

In order to move to the human style of playing these games (assessing the position, then develop a plan with one or a few candidate moves) first a method for evaluation of the position must be found. So by using leaf-evaluation instead of MC playouts I'm trying to do the first step towards thinking like a human again. The next step, as I pointed out in my previous post, is to use/extend the knowledge of the game in the program so that it can be used to select which moves to look at (preferably less than 5, but any reduction in the amount of moves to look at is welcome), and which moves are moot.

"So by using leaf-evaluation instead of MC playouts I'm trying to do the first step towards thinking like a human again. "

Right, that's what I was implying when I said that the only interesting question would seem whether strong programs would shed new light on the workings of the human mind.

I'm not sure if MC evaluation does or not.

Anyway, if it's just the winning that counts, then it's probably just a matter of time. I'm much more interested in why humans recognize havannah patterns so easily, but have such a hard time implementing what they recognize, while the human mind is gets so easily lost in an equally simple game like Explocus (just try it), that is "gefundenes Fressen" for computers.

It's not just the nature of the mind, but also the nature of the game. That's why creating a Chess bot with a 3000 rating in itself means little more than that you're very good at Chess programming, and that Chess is a game with a stucture that accidentally allows you to be good at it.

So why does human pattern recognition have affinity which certain abstract patterns, and none with other abstract patterns? And what are the basic differences between such patterns that leads to this difference in perception?

That's my context.

Keeping developments regarding programming secret to the point of taking bots offline, just to win at havannah is a different context.

I'm fine with it dr. Althofer, but don't expect my sympathy.

I'll agree except for the 3000-rating Chess program making part.

"I'll agree except for the 3000-rating Chess program making part."

Well, in a manner of speaking. Chess happens to be at a convenient crosspoint of massive interest, massive investment, and a grandmaster rating as a reachable target.

The latter quality is not the same for every (type of) game, but comparisons are difficult, because there are few games worldwide that have recognized grandmasters in significant numbers.

Go, Shogi and International Draughts sping to mind, and all must do with less advanced bots than Chess. But since the investments in programming these games may also be less, a comparison remains difficult.

Humans and computers differ in parallelism. The machines on which Havannah is implemented have at most, what, 4, 8 maybe 16 processors, if that? The most I've heard of is 256 for Deep Blue.

The human brain is probably using thousands, maybe millions of much slower and less capable processors to play. So it's not surprising if the best computer algorithm for playing differs markedly from the best approach for humans.

The computers are also held back because they have to wait for a programmer to find or tune a good algorithm.

Then there's the pool. The best human players are those at the top of a much larger pool of Havannah players than the half-dozen Havannah programs.

I did make another set of (again, drastic) changes to Ring von Fehler,

and it seems to be somewhat of an improvement - it even resembles

locally reasonable play. Globally, it's still strange as it absolutely refuses to believe in knight's moves, but perhaps it has a point.

Here's an example: this positions looks hopeless for black:

[game;id:1296202;move:10] but look at the result: Game #1296202

Impressive, and a very dangerous black configuration at the start, obviously, on this boardsize. At 24 it is lost because b6 instead of a7 is already too slow. So the white defense at c7 came too late. Probably 6.i3 should have been played at c6 already.

What changes lead to these impressive playing improvements?

basically, returning to lighter playouts, so I can do a lot more of them.

I was removing all code that deals with static evaluation: it was just stealing time, without giving useful results. During playouts, I still check for forced moves (that achieve or prevent an immediate win), and I follow ladders.

Hi Johannes,

congrats to the recent impreovements of your bot!

Perhaps, you may call it now

""Ring von Fehler quick bot" ?!

Ingo.

Johannes:

On which hardware and at which thinking

times is "Ring von Fehler" running right now?

Ingo.

PS. Congrats to the surprise win on board-10 over Castro!

hardware: Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz

time: currently 10 minutes per move

I use multi-threading (8 cores) only for the playouts

in the fresh leaf nodes, the tree itself is built/visited sequentially.

@Ingo:

game 1296905 ? well, I consider this just a freak accident.

I like that one better:

game 1296117 Still an accident, but...

Hi Johannes,

> @Ingo:

> game 1296905 ? well, I consider this just a freak accident.

My comment was meant as a sort of joke.

With "the bots" currently almost everything

can happen on very large bots.

Ingo.

That happened for 2 reasons: Castro is partially blind to rings, especially on bigger board, and you're using far more compute power. While Castro is fully multi-threaded, it is running single threaded on a fairly old machine (Intel Pentium E2140 @ 1.60GHz) using boardsize minutes per move (ie 4 minutes on size 4, 10 minutes on size 10).

OK, I switched to "boardsize minutes per move" as well.

I'm not familiar with UCT, but my impression is that one node is added to a tree for every playout game. How many playouts do Castro, Gambler, Ring and Wanderer do in 4 minutes or 10 minutes? Do they keep track of that many nodes?

If the C.Freeling challenge games are to be played on LG, I would expect the bots to be using a lot more than 10 minutes per move, up to 36 hours or more. Would that make Space a problem?

I'm not sure anyone implements it as one node added for each playout, but that is a decent approximation. I add all the children of a node when my player reaches a node with no children but at least one rollout. This leads to many or most simulations running through newly expanded nodes that have no previous rollouts, so it approximates to one node expansion per simulation. If something like dynamic widening or low first play urgency is used, then the nodes expanded might be significantly higher.

Running for 4-10 minutes at a time (or even 30 seconds with 8 threads on a fast machine), castro can chew through all available memory multiple times. This is mitigated by garbage collection, where it simply discards all children of solved nodes or children of nodes with less than some amount of rollouts (I start at 5, but it goes up as needed). When that little experience is available, 0 vs 1 experience for a node is completely irrelevant, so it's no loss in playing strength. Most of those nodes won't get reexpanded anyway.

I'm not sure the rules of the game against C Freeling, but I doubt we'll have 36 hours per move. Even if we did, we'll choose big machines (I'd likely use machines with 32gb of ram, and maybe even try to use a cluster with more), and the rest is up to decent garbage collection. The important parts of the tree will still remain, even after 36 hours of thinking on a single move.

Regarding next year's challenge, the games should be played in real time of course. The games club 'Fanatic' at the University of Twente has volunteered to accomodate a game room and the proper connections.

@MarleysGhost: "one node is added to a tree for every playout game"

When I expand a leaf node (= that has no children), then I do a lot of playouts

from there (e.g., 1000) and then I add all children (= new leaf nodes),

with their values set to their AMAF values. (That last part I learnt from Deep

Fork.)

In total, for board size 10 this means 3 .. 4 playouts per node,

so yes, it is a decent approximation.

Dear Ring,

I found AMAF=all moves as first, a term I had never heard of. Does it mean after the 1000 playouts, each child as assigned its win rate from a pre-existing table of AMAF values, so those playouts affect the win rate of the expanding node and its parents but not the fresh children?

If you get good enough will you change your name to "Frei von Fehler"?

AMAF (as I understand it, and I always confuse it with RAVE):

for each empty position q, the conditional probability,

over all playouts from a fixed situation (with P to move):

if q was played by P (during playouts), was the playout a win for P.

This is then used as the value of child p.

So, all moves q are considered "as a first move", hence the name.

Actually I use some decreasing weight function

because I don't trust long playouts.

PS: "frei von fehler" - that's never gonna happen ...