A new Amazons playing bot Amazons forum

27 replies. Last post: 2012-03-22

Reply to this topic Return to forum

A new Amazons playing bot
  • Martin Mueller at 2011-10-06

    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

  • Tommah at 2011-10-06

    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. :)

  • MarleysGhost at 2011-10-07

    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.

  • Tommah at 2011-10-07

    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.

  • Ingo Althofer at 2011-10-07

    Hello Tommah,

    will your bots participate in the Olympiad in Tilburg?

  • MarleysGhost at 2011-10-07

    > ..hamiltonian path..

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

  • MarleysGhost at 2011-10-07

    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.

  • Ingo Althofer at 2011-10-07

    > 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...

  • Tommah at 2011-10-07

    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.

  • MarleysGhost at 2011-10-07

    > 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.

  • Tommah at 2011-10-07

    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.

  • Ingo Althofer at 2011-10-08

    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.

  • MarleysGhost at 2011-10-08

    > smaller search tree or proof tree

    Aha. LG is really educational.

  • Ingo Althofer at 2011-10-08

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

  • MarleysGhost at 2011-10-08

    Genau

  • Richard Lorentz at 2011-10-08

    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.

  • Martin Mueller at 2011-10-08

    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.

  • pedropajarito at 2011-10-11

    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).

  • Martin Mueller at 2011-10-14

    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?

  • pedropajarito at 2011-10-15

    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.

  • pedropajarito at 2011-10-15

    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

  • pedropajarito at 2011-10-25

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

  • Martin Mueller at 2011-10-26

    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.

  • Arrow2_bot at 2011-12-15

    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

  • pedropajarito at 2012-01-01

    Let’s see what it can do.

  • pedropajarito at 2012-03-22

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

  • darse at 2012-03-22


    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.]

Return to forum

Reply to this topic




Include game board: [game;id:123456] or [game;id:123456;move:20] or [game;id:123456;move:20;title:some text]