Dominion Strategy Forum

Please login or register.

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

Author Topic: Problem about AI problems  (Read 3204 times)

0 Members and 1 Guest are viewing this topic.

DG

  • Governor
  • *****
  • Offline Offline
  • Posts: 4074
  • Respect: +2624
    • View Profile
Problem about AI problems
« on: June 13, 2013, 08:14:08 am »
+1

Here's a open ended quiz for everyone who thinks that Dominion AI isn't that difficult. Let's look at a kingdom of chapel, menagerie, woodcutter, scheme, bridge, ironworks, quarry, worker's village, jester, hoard. What potential problems would an AI find in playing/analyzing this kingdom?

You can reveal any problem an AI might find even if does not apply to all AIs. It can apply to card play rules, purchasing rules, creating candidate AIs, testing potential AIs against each other, etc.
« Last Edit: June 13, 2013, 08:15:18 am by DG »
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1184
    • View Profile
Re: Problem about AI problems
« Reply #1 on: June 13, 2013, 04:59:21 pm »
+3

I think that AI/ragingduckd could play this kingdom quite well.

That said, a bot may have trouble with the following (disclaimer: I don't really know what I'm talking about)

-Scheme+Menagerie; I bet that the goko bots don't know that scheming three menageries is a poor play. Although it would be weird to get that many schemes at all.
-It might buy a quarry which it doesn't need on this board.
-The bot would need to watch out for a three-pile.
-Wrong play order with menagerie.
Logged

ftl

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2056
  • Shuffle iT Username: ftl
  • Respect: +1345
    • View Profile
Re: Problem about AI problems
« Reply #2 on: June 13, 2013, 05:58:08 pm »
0

Jester is probably a very difficult card for an AI to get right. Because, fundamentally, AIs are much easier to program if you make them modular - for example, make "what card do I play next" a separate decision from "what will I buy at the end of the turn". Of course, in dominion, all of these decisions are intertwined, but some time you can perhaps try to handwave some interaction away when making particular decisions. With Jester, you can't do that at all.

In order to decide whether to buy Jester, presumably the AI would need to have some idea of what Jester will do for its deck or for its opponents deck.

But what Jester does for you depends *entirely* on your opponent's deck and, in this set, on your deck too. It could be a reliable curser if you've built an engine that plays Fortune Teller+Jester each turn and your opponent still has green (but to do that, the AI needs to know to play Fortune Teller before Jester!) or it could be a gainer, where what cards you get depends on what your opponent is doing.

So it creates very detailed dependencies in what the AI needs to know to make decisions. To decide whether to buy Jester, it needs to know how it will play Jester, and to know how to play Jester it needs to know something about its opponents deck state AND information about its own current deck, and getting a reasonable guess at what the opponent will have in their deck by the time it plays Jester requires a good guess at what a reasonable strategy for the opponent is.

Makes it very hard to split up decisions without getting recursive dependencies among them.
« Last Edit: June 13, 2013, 06:01:49 pm by ftl »
Logged

eHalcyon

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8689
  • Respect: +9187
    • View Profile
Re: Problem about AI problems
« Reply #3 on: June 13, 2013, 06:15:10 pm »
0

This looks like a huge engine board to me, opening IW-Chapel, picking up another IW and then piledriving WV and Bridge while trashing everything else.  With just $3, buy Menagerie or Scheme.  If a mirror, Jester can be good especially with more than 2p.  Actually, not much more than 4 Bridges are needed.  WV is more important so that Bridges can be played as well as IW for Province.

Cost reduction in Bridge (and Quarry) will make it difficult for an AI to evaluate many things: its own buying power, the buying power of the opponent's deck, the potential for 3 pile endings, even the value of Worker's Village and Ironworks.  I think a competent human player will often be able to suddenly end the game while the AI doesn't ever expect it.

IW is often a mediocre card but it is killer here.  It is killer because of the confluence of several features of the kingdom -- quick trashing in Chapel, multiple desirable $4 cards, cost reduction so that IW can gain Province.  How does the AI recognize and associate all these factors to "IW is good"?  How does it determine which features of the kingdom don't matter wrt IW?  How does it take that lesson and apply it when just one or two factors are missing?
Logged

Warfreak2

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1149
  • KC->KC->[Scavenger, Scavenger, Lookout]
  • Respect: +1324
    • View Profile
    • Music what I do
Re: Problem about AI problems
« Reply #4 on: June 13, 2013, 06:20:15 pm »
0

A lot of this discussion seems predicated on the AI being written as an "expert system"; that is, a set of rules about what to do in what situations, designed to capture as much human insight into Dominion strategy as possible. I think a genetic algorithm to decide a buy order, combined with Monte Carlo Tree Search for play decisions (and in the short term, deciding whether to deviate from the buy order), would find the IW/Bridge engine without any problem, and probably play it a lot better than me.
Logged
If the only engine on the board is Procession->Conspirator, I will play it.

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Problem about AI problems
« Reply #5 on: June 14, 2013, 04:46:57 am »
+1

Somebody wrote one of those for optimising buy orders, but they used pre-set play rules.
Logged

DG

  • Governor
  • *****
  • Offline Offline
  • Posts: 4074
  • Respect: +2624
    • View Profile
Re: Problem about AI problems
« Reply #6 on: June 15, 2013, 05:05:18 pm »
0

If anyone wants to look further into this, look at the link to the Provincial AI http://graphics.stanford.edu/~mdfisher/DominionAI.html and try manually creating a set of purchasing rules for this kingdom in the format used by Provincial.
Logged

ragingduckd

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1059
  • Respect: +3527
    • View Profile
Re: Problem about AI problems
« Reply #7 on: June 15, 2013, 08:36:11 pm »
0

I'd expect the hardest cards for an AI are the ones that introduce a lot of different options (KC, Misfits), trade-off dissimilar values (Upgrade, Apprentice), or have mostly long-term benefits (Pirate Ship).

Sweet! 33 VP in only 28 turns: http://dom.retrobox.eu/?/20130615/log.5101a6c4e4b02b7235c3860f.1371342486483.txt
Logged
Salvager Extension | Isotropish Leaderboard | Game Data | Log Search & other toys | Salvager Bug Reports

Salvager not working for me at all today. ... Please help! I can't go back to playing without it like an animal!

Warfreak2

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1149
  • KC->KC->[Scavenger, Scavenger, Lookout]
  • Respect: +1324
    • View Profile
    • Music what I do
Re: Problem about AI problems
« Reply #8 on: June 16, 2013, 06:24:55 am »
+5

Quote
Banker Bot   plays King's Court
Banker Bot   plays Band of Misfits
Banker Bot   chooses Feast
Banker Bot   plays Feast
Banker Bot   trashes Feast
Banker Bot   gains Feast
Banker Bot   plays Band of Misfits
Banker Bot   plays Feast
Banker Bot   trashes Feast
Banker Bot   gains Remake
Banker Bot   plays Band of Misfits
Banker Bot   plays Feast
Banker Bot   trashes Feast
Banker Bot   gains Estate
I don't think Banker Bot should be our baseline for this thread.
Logged
If the only engine on the board is Procession->Conspirator, I will play it.
Pages: [1]
 

Page created in 0.062 seconds with 20 queries.