Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1] 2 3  All

Author Topic: Provincial: Cool looking Dominion AI  (Read 5300 times)

0 Members and 1 Guest are viewing this topic.

rrenaud

  • Administrator
  • *****
  • Offline Offline
  • Posts: 951
  • Isotropic username: rrenaud
  • Uncivilized Barbarian of Statistics
  • Respect: +1032
    • View Profile
    • CouncilRoom
Provincial: Cool looking Dominion AI
« on: February 21, 2013, 10:07:00 pm »
+6

Logged

Schneau

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1114
  • Goko username: Schneau
  • Isotropic username: Schneau
  • Respect: +1185
    • View Profile
    • Rainwave
Re: Provincial: Cool looking Dominion AI
« Reply #1 on: February 21, 2013, 10:18:28 pm »
0

That looks really cool! I remember seeing something similar here, but this new one looks more well-formed and explained. I haven't read the whole thing yet, but I'm excited to, since I do research in evolutionary algorithms.
Logged

timchen

  • Minion
  • *****
  • Offline Offline
  • Posts: 657
  • Isotropic username: allfail
  • Respect: +177
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #2 on: February 21, 2013, 11:29:36 pm »
+1

Looks pretty much like an automated Geronimoo's simulator.

The author is amazing however! So many interesting projects!
Logged

werothegreat

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2992
  • Goko username: werothegreat
  • Isotropic username: werothegreat
  • Prepare to be boarded!
  • Respect: +2990
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #3 on: February 21, 2013, 11:48:48 pm »
0

Glancing through, I'm rather staggered that the leading strategy in a kingdom with Goons, City and Nobles, is to buy all the Cities and all the Nobles, but only one Goons.  Now that's just a waste of Actions.
Logged
Check out this fantasy epic adventure novel I wrote, the Broken Globe!  http://www.amazon.com/Broken-Globe-Tyr-Chronicles-Book-ebook/dp/B00LR1SZAS/

dondon151

  • 2012 US Champion
  • *
  • Offline Offline
  • Posts: 2113
  • Respect: +1435
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #4 on: February 22, 2013, 12:22:47 am »
0

Glancing through, I'm rather staggered that the leading strategy in a kingdom with Goons, City and Nobles, is to buy all the Cities and all the Nobles, but only one Goons.  Now that's just a waste of Actions.

That's only the leading strategy at one point in the AI evolutionary process.
Logged

blueblimp

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1623
  • Goko username: blueblimp
  • Isotropic username: blueblimp
  • Respect: +915
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #5 on: February 22, 2013, 03:38:13 am »
+1

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find. The 3rd kingdom is complex, but the bot's strategy doesn't seem like one of the good options available.

I also wish the bot's isotropic name were given, so that I can see its rating.
Logged

meandering mercury

  • Ambassador
  • ***
  • Offline Offline
  • Posts: 33
  • Respect: +34
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #6 on: February 22, 2013, 03:52:19 am »
+1

I know of the author personally (although I probably only talked to him once or twice). He was something of a minor legend. His roommate was my TA for a class once and he told me that the author had some video game (Warcraft 3?) AI that would play against other humans and was ranked quite well on the leaderboard (better than most hobby players).

I have a feeling that there is an AI player rampaging on Isotropic, feeding on hapless human victims. You can download the executable and play against the AI using the built-in interface.

If you read over the documentation you'll find that there is some sophistication here, including the ability to know when to remodel Gold into Province or knowing what to Salvage. Also of note is that the fact that it sounds like the author is *capable* of writing more powerful ("classic" machine learning) AI engines but *chooses* not to in order to make the results useful to human players.

I'm a level 35 player. I played 3 games with the AI:

Game 1: Won 34 pts to 28 pts the first game: mostly a Bishop game that it seemed to play well.

Game 2: Won 27 to 24, using Chapel, Bazaar, Courtyard, 1 Explorer + 1 Expand against a Courtyard/BM? strategy (hard to tell exactly what AI is doing because log isn't as pretty) -- felt pretty close though. I think I only won because I Expanded Province -> Province to deplete the pile, but then again because the UI is more clumsy I didn't realize I had overtrashed my deck until it was too late, and then had to spend some time rebuilding.

Game 3: Won 83 to 47 last game. Key cards: Throne Room, Gardens, Village, Monument, Council Room, Loan. I used a draw your deck + play zillions of Monuments strategy and beat the AI's BM-like strategy fairly solidly.

Overall, quite impressive for an AI although I don't expect it to beat good players on engine boards. I get the impression that the AI buys a province every time it has $8+ so it just isn't setup for megaturns. I think it would play BM-style boards quite well, however.
Logged

Dsell

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1014
  • Isotropic username: Dsell
  • Respect: +675
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #7 on: February 22, 2013, 04:06:09 am »
0

If I read correctly, it will basically always buy one of the most expensive cards it can afford, which is often going to be a mistake (unless this was just when testing optimal strategies for a particular kingdom). That would explain always buying Province with $8+.
Logged
"Quiet you, you'll lynch Dsell when I'm good and ready" - Insomniac

timchen

  • Minion
  • *****
  • Offline Offline
  • Posts: 657
  • Isotropic username: allfail
  • Respect: +177
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #8 on: February 22, 2013, 05:09:41 am »
+1

You didn't read it correctly.
Logged

lespeutere

  • 2012 German Champion
  • *
  • Offline Offline
  • Posts: 458
  • Goko username: LESPEUTERE
  • Isotropic username: lespeutere
  • Respect: +368
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #9 on: February 22, 2013, 06:53:56 am »
0

I was curious whether it was a f.ds member doing this stuff so I checked the forum member map and there is one guy based in Palo Alto: WrathOfGlod (presumably better known by his iso handle Michael Harris). So maybe.. ;-)
Logged

DG

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2730
  • Respect: +1202
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #10 on: February 22, 2013, 09:07:53 am »
0

This does seem to be an interesting AI since it is learning and evaluating before a game is played, in order to decide a purchasing strategy that it will execute in the coming game. So a limitation immediately arises that the predetermined strategy does not account for draws, the deck contents, and the opponent's strategy. It offers instead a purchasing strategy that has suited a variety of draws and decks in the past. The Goko bots seem to have an awareness of the game state but only a general purchasing strategy that applies to all kingdoms.

As with Geronimoo's simulator, the results seem heavily dependent upon good card play rules that are hard written into the software. Again big advantages can be gained over the Goko bots if these play rules exclude trashing golds with transmute, for example. The author states however that the buy and play rules are largely disconnected, and that good play strategies rarely understand long term behavior of the AI. This is true up to a point, but that point becomes a large barrier as the AI gets better. Good play should buy cards to support card play, card play that provides the right coins needed for purchasing.

If the author is reading this then I'd suggest running a lot of tests on Base set + Hinterlands kingdoms. These have a lot of treasure based decks with limited trashing that might suit AI analysis. The Goko bots can play this combination quite well (compared to other expansions). It would also be a good test of the learning process to see if the AI can find heavy investment in highways or fool's gold.
« Last Edit: February 22, 2013, 03:42:10 pm by DG »
Logged

dondon151

  • 2012 US Champion
  • *
  • Offline Offline
  • Posts: 2113
  • Respect: +1435
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #11 on: February 22, 2013, 01:58:35 pm »
0

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find.

I don't quite follow. I think its biggest problem is definitely prioritizing Bridge and FV over Chapel, but the rest of its buy strategy looks fit for a KC-Bridge megaturn.
Logged

techmatt

  • Pearl Diver
  • **
  • Offline Offline
  • Posts: 14
  • Respect: +22
    • View Profile
    • Matt's Webcorner
Re: Provincial: Cool looking Dominion AI
« Reply #12 on: February 22, 2013, 02:29:57 pm »
+10

The important thing to remember about the AI is that it is mostly focused on finding good purchasing strategies.  To keep training times reasonable, it only uses deterministic strategies when deciding how to play cards.  After it determines what its general buy strategies are, it *should* switch to a more advanced strategy for playing cards that resembles the techniques used for say, Chess and Go AIs, but I haven't implemented this yet.  Consequently, it will not be as effective at playing against humans as it could be.

I haven't really spent enough time generating interesting strategies.  In cases where there is a classic strategy such as king's court + bridge, it will typically converge to it; for example http://graphics.stanford.edu/~mdfisher/Images/Dominion/KCBridge.png
In cases where it doesn't, remember that sometimes the "megaturn" strategy is not always the best one.

The "greedily buy provinces" can be easily changed.  See for example http://graphics.stanford.edu/~mdfisher/Images/Dominion/ProvinceBuys.png where it buys a Wharf and two Gold before its first Province.  The only reason I don't default to this behavior is that it makes the visualizations even larger and consequently harder to read.

As far as playing on Isotropic goes, it is currently around level 23 but really hasn't played as many games as it needs to for this to be a good evaluation.  There are a lot of challenges to getting it to play well, and it is greatly hindered by the fact that it can't train for as long as it needs to, so converges to sub-optimal strategies.  I will focus more on this once I implement more adaptive card play behavior.

One of the hardest challenges for the AI is how to handle things that mix buy and play strategies.  Sometimes, in response to how you or your opponent's buys are going, it makes sense to change what you are purchasing.  For example, if you go through your 2nd shuffle without a 5-coin turn, you might re-evaluate what you are purchasing.  This is a very difficult behavior to encode.
Logged

Axxle

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1335
  • Isotropic username: Axxle
  • Most Valuable Serial Killer
  • Respect: +1611
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #13 on: February 22, 2013, 02:42:06 pm »
0

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find. The 3rd kingdom is complex, but the bot's strategy doesn't seem like one of the good options available.
Read again, I think it did find it: " For many kingdoms, the AI will have no trouble capturing "classic" strategies in a reasonable number of generations. For example, the canonical "king's court + bridge" game: "
Logged
We might be from all over the world, but "we all talk this one language  : +1 card + 1 action +1 buy , gain , discard, trash... " - RTT

"And logic disappeared in a puff of Ozle." - qmech

WrathOfGlod

  • Navigator
  • ****
  • Offline Offline
  • Posts: 72
  • Goko username: Mike Harris.0001
  • Isotropic username: Michael Harris
  • Respect: +23
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #14 on: February 22, 2013, 02:53:47 pm »
0

I was curious whether it was a f.ds member doing this stuff so I checked the forum member map and there is one guy based in Palo Alto: WrathOfGlod (presumably better known by his iso handle Michael Harris). So maybe.. ;-)
Lol, not me. I wish I was this gosu
Logged

Axxle

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1335
  • Isotropic username: Axxle
  • Most Valuable Serial Killer
  • Respect: +1611
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #15 on: February 22, 2013, 03:04:17 pm »
0

One of the hardest challenges for the AI is how to handle things that mix buy and play strategies.  Sometimes, in response to how you or your opponent's buys are going, it makes sense to change what you are purchasing.  For example, if you go through your 2nd shuffle without a 5-coin turn, you might re-evaluate what you are purchasing.  This is a very difficult behavior to encode.
My first thought is that it sounds like what it needs is a feel for "how long is this game going to last" and adapt strategy that way.  It does sound like a very hard problem to solve though.
Logged
We might be from all over the world, but "we all talk this one language  : +1 card + 1 action +1 buy , gain , discard, trash... " - RTT

"And logic disappeared in a puff of Ozle." - qmech

techmatt

  • Pearl Diver
  • **
  • Offline Offline
  • Posts: 14
  • Respect: +22
    • View Profile
    • Matt's Webcorner
Re: Provincial: Cool looking Dominion AI
« Reply #16 on: February 22, 2013, 03:55:36 pm »
+2

Quote
My first thought is that it sounds like what it needs is a feel for "how long is this game going to last" and adapt strategy that way.  It does sound like a very hard problem to solve though.

Predicting the end of the game is pretty easy.  It's just a supervised learning problem that can be solved with fairly standard techniques such as a support vector machine: http://en.wikipedia.org/wiki/Support_vector_machine

The more challenging problem is changing what you're going to purchase in response to an event besides the end of the game.  For example, consider a kingdom with Witch.  The naive thing to do, which is what the AI is currently doing, is to say you want to buy either 0, 1, or 2 witches.  But this is pretty poor play in some situations.  If you got unlucky in your 2nd shuffle and got no 5-coin turns, you won't be able to buy a Witch until fairly late in the game.  In this case, you might not want to buy a 2nd witch because the curses might be essentially depleted before you get to play it.  Likewise, your opponent might want to take advantage of your unluckiness and make sure to get a 2nd witch.  In either case, the players are adapting their buy strategy to an event besides the end of the game (in this case, the # of curses remaining).  It's possible to try and encode all these features, but there are such a huge # of situations this isn't likely to be feasible or effective.
Logged

DG

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2730
  • Respect: +1202
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #17 on: February 22, 2013, 04:05:00 pm »
0

Has the AI separate purchasing rules for 3/4 and 5/2 starts? Quite often an initial purchase of a terminal action on turns 3 or 4 will dictate the nature of a deck. For example a 4/3 start might suggest a militia but if you have a 5/2 start you can look to skip militia entirely (and buy goons later, say).
Logged

rrenaud

  • Administrator
  • *****
  • Offline Offline
  • Posts: 951
  • Isotropic username: rrenaud
  • Uncivilized Barbarian of Statistics
  • Respect: +1032
    • View Profile
    • CouncilRoom
Re: Provincial: Cool looking Dominion AI
« Reply #18 on: February 22, 2013, 04:53:05 pm »
+1

Have you considered hard coding some of the human learned rspeer/gerinomoo bots as competitors?  Presumably playing against a better baseline would help speed up the learning.
Logged

techmatt

  • Pearl Diver
  • **
  • Offline Offline
  • Posts: 14
  • Respect: +22
    • View Profile
    • Matt's Webcorner
Re: Provincial: Cool looking Dominion AI
« Reply #19 on: February 22, 2013, 05:39:02 pm »
+2

Quote
For example a 4/3 start might suggest a militia but if you have a 5/2 start you can look to skip militia entirely (and buy goons later, say).
The AI does condition its build on 2-5 vs. 3-4 splits.  See for example http://graphics.stanford.edu/~mdfisher/Images/Dominion/Game34vs25.png
The top line for each game shows whether it's training on a 3-4 or 2-5 split.  In this case it skips Militia in the 2-5 game.

Quote
Have you considered hard coding some of the human learned rspeer/gerinomoo bots as competitors?  Presumably playing against a better baseline would help speed up the learning.
I did do some brief tests for this.  There is pretty high variance; naturally, everything depends on the kingdom, and Dominion has a high variance game, but unless a specific combination of cards has been encoded into rspeer's AI, the kingdom-specific trained builds will do significantly better (typically somewhere between 70-30 on most kingdoms).
At first glance it would seem like a good idea to train against a strong baseline.  This would definitely help with the initial generations when the AI is proposing a lot of very random and consequently terrible builds until it finds a plausible one.  The problem with training against a stronger baseline is that it tends to bias the AI towards taking advantage of the weaknesses in the baseline.  For example, the baseline might always purchase 2 militias, causing the AI to bias itself towards getting extra libraries.  This might work well versus the baseline but result in poor performance once played against humans or un-biased AIs that don't make the same mistakes the baseline does.
Logged

rrenaud

  • Administrator
  • *****
  • Offline Offline
  • Posts: 951
  • Isotropic username: rrenaud
  • Uncivilized Barbarian of Statistics
  • Respect: +1032
    • View Profile
    • CouncilRoom
Re: Provincial: Cool looking Dominion AI
« Reply #20 on: February 22, 2013, 06:29:40 pm »
0

Shouldn't the hard coded strategies eventually get out competed, and then fall out of the opponent pool?

Do you have a measure of how many distinct kingdom cards dominant strategies tend to use?

If it tends to be low, you could imagine saving dominant strategies into a database, and then finding historical dominant strategies as initial candidates for a given set.  If it's not low, you can imagine optimizing to prune cards out of a strategy so that it uses only 3 distinct and still maximizes its chances against the full strategies.  These would then be good initial candidate strategies to any applicable sets.
Logged

blueblimp

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1623
  • Goko username: blueblimp
  • Isotropic username: blueblimp
  • Respect: +915
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #21 on: February 22, 2013, 07:22:30 pm »
0

Interesting, but the example strategies in the write-up aren't convincing. The 2nd kingdom obviously wants a KC-Bridge megaturn, which the AI didn't find.

I don't quite follow. I think its biggest problem is definitely prioritizing Bridge and FV over Chapel, but the rest of its buy strategy looks fit for a KC-Bridge megaturn.
Whoops, I got my kingdom numbering off and actually meant the kingdom with KC + Rabble + Bridge, where the bot only buys 1 each of KC and Bridge (and prefers Silver over Lighthouse), and I'm pretty sure early greening sans-Lighthouse will be absolutely crushed by KC-Rabble into megaturn.
Logged

techmatt

  • Pearl Diver
  • **
  • Offline Offline
  • Posts: 14
  • Respect: +22
    • View Profile
    • Matt's Webcorner
Re: Provincial: Cool looking Dominion AI
« Reply #22 on: February 22, 2013, 09:29:22 pm »
+2

Quote
Whoops, I got my kingdom numbering off and actually meant the kingdom with KC + Rabble + Bridge, where the bot only buys 1 each of KC and Bridge (and prefers Silver over Lighthouse), and I'm pretty sure early greening sans-Lighthouse will be absolutely crushed by KC-Rabble into megaturn.

It's true that this is probably an inferior strategy, as the image you're talking about is just showing the chain of strategies the AI goes through.  In the case of this particular kingdom, the AI hasn't converged yet since it takes a while to discover the KC+Bridge strategy.  If you let the AI run for longer it will converge to something close to the mega-turn strategy:
http://graphics.stanford.edu/~mdfisher/Images/Dominion/KCBridge.png
Logged

DG

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2730
  • Respect: +1202
    • View Profile
Re: Provincial: Cool looking Dominion AI
« Reply #23 on: February 22, 2013, 10:16:47 pm »
0

Of course if you let other people play with it they are bound to find bugs - throned cards are not being cleaned up at end of turn and I'm not convinced they are correctly applied either. I don't know if this applies to the AI generally or just the human player.
Logged

techmatt

  • Pearl Diver
  • **
  • Offline Offline
  • Posts: 14
  • Respect: +22
    • View Profile
    • Matt's Webcorner
Re: Provincial: Cool looking Dominion AI
« Reply #24 on: February 22, 2013, 10:33:05 pm »
+1

Quote
throned cards are not being cleaned up at end of turn

Most of this is a problem with visualizing the cards, although it's possible the internal state machine used by the AI is also wrong in this regard.  The user interface is not really meant for anything more than basic testing of the AI; ideally people would just be playing through a Goko or Isotropic interface instead as those are better tested and more user-friendly.  I'll look into the throned card problem; there are also any manner of fairly bizarre corner cases involving KC -> TR -> duration cards.
Logged
Pages: [1] 2 3  All
 

Page created in 0.156 seconds with 21 queries.