A new Amazons playing bot

Arrow2_bot, developed by our research group at the University of Alberta, is now available for games.

See

http://www.littlegolem.net/jsp/info/player.jsp?plid=25696

We have no good idea how strong it is. Please challenge it!

Please post any comments you have in this thread.

Thank you

Gabe and Martin for the Arrow2 team

Ah, I remember your Amazons paper in MGONC. I'll play a couple of games with Arrow2.

I actually have an Amazons bot on here that I wrote a long time ago... I'll have it play with your bot as well. I'm sure yours plays much better than mine, but if nothing else maybe the contest will make you smile. :)

I may be wrong, but it looks to me that NataliaBot gave game 1380572 away with 75.j3-h3/j3. NataliaBot could have beaten Arrow2_bot with 75.j3-i3/j3, then along h3, g2, f3, e3, f2, e1, d1 to 91.d1-c2/d1, sending the arrow in each step to the just-vacated cell.

It makes me wonder what algorithms the bots use in the end game to plan a path through undisputed territory.

At move 50 the territories were already separated, and with Natalia to move the territories were equal... so Arrow would have won. I'm guessing that Arrow would have played optimally if Natalia had too. Natalia isn't too smart about the endgame; the only thing it does is try to form corridors and stay at the end of them. Usually this is good enough. A smarter thing to try would be to find a hamiltonian path through the territory and play in that order, but I didn't attempt that. Anyway, people have told me that Natalia has trouble with the opening more so than the endgame, so that's where I spent the most time.

Hello Tommah,

will your bots participate in the Olympiad in Tilburg?

> ..hamiltonian path..

Yeah, I've heard those things are hard to find. :)

OK, now I get it. It was move 39.f4-f3/f4 that separated the two sides' reachable free cell sets. Arrow2_bot had a won game from sometime before that. Arrow2_bot's "error" at 84.c8-c9/d10 came after NataliaBot's move 75, still leaving Arrow2_bot with a won game.

> Arrow2_bot's "error" at 84.c8-c9/d10 came after NataliaBot's move 75,

> still leaving Arrow2_bot with a won game.

In man's eye this may look like an error, but it is a feature.

Almost all bots on Monte Carlo base try to win by the smallest possible

margin. Come to Tilburg and watch Johan de Koning (the programmer of the

strongest non-Monte-Carlo bot in Amazons) losing in this way...

I'm not going to be at the Olympiad. Programming these bots is just a hobby for me; I do it for fun for a while, leave it, and come back a few months later. I'm not really knowledgeable in the new AI techniques they use today, so for the hard-to-tackle games, I can't really compete.

The hamiltonian path problem is of course too difficult in general, but I think in Amazons a few simple cases would go a long way. In Natalia's game that we were talking about, I think she could have just walked around the perimeter of her territory.

> try to win by the smallest possible margin

Is that really it, or is it that the selection among winning moves is made arbitrarily or randomly, ignoring the winning margin they lead to? Earlier this year there was a forum topic about go-playing bot (using an MC variant IIRC) that was winning by a tiny little margin according to the Chinese scoring rules it used internally, but lost the game when it was scored by LG's Japanese scoring rules.

> Hamiltonian path

Hmm. It's not really a Hamiltonian path problem, or at least not one where the nodes are the board cells, because a queen can travel along an "edge" between two cells A and B that are not next-door neighbors, and an arrow to an intermediate cell would wipe out such an edge without the queen having visited A or B.

I would hope there'd be an algorithm that could handle, say, a few tens of Amazon cells in a reasonable time. There are a few region shapes that can't be fully exploited, but not many.

I just meant moving one cell at a time and then shooting an arrow onto the square we just left. This seems as if it would work most of the time, as long as we can get to a good starting point beforehand.

Tommah wrote:

> I'm not going to be at the Olympiad. Programming these bots is just a hobby

> for me; I do it for fun for a while, leave it, and come back a few months

> later. I'm not really knowledgeable in the new AI techniques they use today,

> so for the hard-to-tackle games, I can't really compete.

It is not necessary to be fully competitive. Simply participating means already

a lot of fun (and watching those who almost get heart attacks when they get only

silver instead of gold is another special experience).

For instance, Hanfried will be almost chanceless in the Ewn competition.

(However, when the dice help us ....)

\*\*\***************

MarleysGhost wrote:

> try to win by the smallest possible margin

> Is that really it, or is it that the selection among winning moves is made

> arbitrarily or randomly, ignoring the winning margin they lead to?

It is a complicated topic. In principle many MC-bots simply count all wins

(by whatever margin) as being of same value. But ... when a certain move leads

to a smaller search tree or proof tree this move may be preferred. Suboptimal

moves often force this side to play very precise in the sequel, leading to

smaller tree.

Ingo.

> smaller search tree or proof tree

Aha. LG is really educational.

You mean "part of the forum of LG is really educational" ?!

Genau

MarleysGhost wrote:

> try to win by the smallest possible margin

> Is that really it, or is it that the selection among winning moves is made

> arbitrarily or randomly, ignoring the winning margin they lead to?

and Ingo replied:

> It is a complicated topic. In principle many MC-bots simply count all

> wins (by whatever margin) as being of same value. But ... when a certain

> move leads to a smaller search tree or proof tree this move may be

> preferred. Suboptimal moves often force this side to play very precise

> in the sequel, leading to smaller tree.

Another factor is that MC-bots usually select moves that are most likely to win, which can be at odds with making the "biggest" move.

Another issue is proven wins in the game tree. Arrow2 uses the Fuego game-independent Monte Carlo engine, which can back up proven wins and losses by using the minimax rule. A quiet move that lets both sides create large territories and wins by a narrow margin may be much quicker to prove than an aggressive invasion.

This feature is not yet well developed in Arrow2, but we have seen it work very well in other games.

About Arrow2:

It's level must be about 2000 solid. Somewhere in between natalia and invader. I must say I like its play style a lot, it feels very human. If you play against it, it is a good idea to play a closed game (in chess terminology).

Thank you for your interesting comments Pedro, and for playing many test games. I am not so clear by what you mean with "closed games". I think that in chess, it corresponds to structures where the pawns are blocked in the middle. What would be the equivalent in Amazons? Blocked Amazons? And what do you think are the weaknesses in Arrow2's play?

Yes, I call a closed game when center squares are occupied early in the game and the amazons have to maneuver more in horizontal o vertical. I think I am not good enough to give you good insights into it's weaknesses. You could kindly forward that question to TUMRAK, an excellent amazons player that might be able to help you.

If you make any changes to the engine it would be nice if you gave it another name "arrow2.1" or whatever, as I would like to keep arrow2 as a sparring partner.thx

perhaps it might be a god idea in completly closed endgames, for the bot to resign if the position is hopeless

Yes, definitely. I apologize that we have not set this properly yet. It should at least resign when it proves a loss. There is a bug with counting the safe territories that slows this down greatly. The alternative that we use e.g. in Go is to set a resign threshold for the search, if the winning probability is below say 0.05.

We do have some other improvements that we are working on. I agree with your suggestion of naming it 2.1. But the resign fix should go into 2.0 as well.

I have set up a new version of the bot -- Arrow2_1_bot

This one uses "partial moves" (see explanation) in the game tree and playouts. This translated to about 200 Elo gain in self play.

Partial moves in this case are where each move is split into 3 parts. First, select a queen, then select a destination square, then select an arrow destination. There are huge savings in the move generation with this method.

-Gabe

Let's see what it can do.

I think at the moment it is weaker than Arrow2_bot, it lets an amazon get caught easily in the opening.

To address the earlier question about the endgame: Michael Buro showed that filling an enclosed territory is indeed NP-complete (circa 2000?). However he also found that almost any reasonable algorithm will be nearly perfect in practice, since the tricky patterns with inefficiencies are quite rare. [I think i recall him saying that you could just use a Monte Carlo method, for example, and it would almost always converge quickly on an optimal fill.]