Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[sudgy]

I've heard of this proposed for a few other games, so I was wondering if anybody has even had the idea for this.  Has anybody thought of making an AI for dominion that would learn better strategy just playing the game?  for instance, it would go for a bad strategy, realize it was bad, and not do it again.

[DG]

http://forum.dominionstrategy.com/index.php?topic=870.0.

[Ozle]

DONT DO IT!! (Link)

[ftl]

Because of all the variety in dominion, this is a very, very hard problem.

[sudgy]

Because of all the variety in dominion, this is a very, very hard problem.

I know that, I was just curious...

[DStu]

I think the problem is that you can't just let bot play somehow, tell it "that was bad, try something else" and expect that to work.  That may work if the possible things to try are very limited, and in an stable environment.  But even then it's not very efficient in how well it learns, maybe only in how fast this can be programmed.

But we are in neither of these situations, and that means you need some good model first.  We have quite good models on how to play BigMoney. On these you could quite easily put some learning to find out how to play them optimal (without considering the opponent), and maybe also which to play on which boards.
But that's also pretty uninteresting.

Also some of the other board types (combos, slogs), we either have the bots, or they could be implemented quite easily.  Here also you could maybe do some machine learning, but already the number of variables grow quite high (which type to play against which deck, what does the opponent do, support cards, how to play optimally given board/opponent)


But the point is, that is not what it is about.  The fun things are the engines, and we (at least I) have basically now idea on how to have 1 (or maybe 2-3) generic bots that on a random board, can decide if there is an engine in it or build it.  Not even in the form of "OK, here is the model with 20 free parameters per card in Dominion, now find some good values for these and then chances are good that you have some decent engine-bot".
And I think nobody is really interested in putting all the work in some machine-learning on what we have if in the end this bot can't play engines.


Edit: Also, I think the motivation to build a bit more with the bots would be a lot higher if there would be an API to let them play on goko;

[blueblimp]

This would be cool and is hard hard hard. I speculate PhD thesis-worthy hard, or harder.

The reason is the sheer amount of variety in Dominion, and somehow the learning AI should be able to smoothly integrate it all. As DStu points out, there are many kinds of games: combos, slogs, engines, etc. Tactics and strategy are both important, and fairly different. There is randomness, so brute-force search can't give the AI much help, yet tactics and endgame play rely on precise calculation. There is hidden information, since you don't know what's in your opponent's hand.

In addition to that, the magnitude of the task is huge because there are so many kingdom cards. Each one is going to need some degree of special-casing and many present unique challenges. For example, games dominated by Possession are dramatically different than normal games.

Edit: That all said, I'm pretty sure it's possible with today's technology to create a Dominion AI that outplays top humans. But it would be a TON of work and cleverness. It might be best to attempt it with a team instead of just one person.

Ultimately, I think the main barrier is that there simply isn't enough reward for the work required. In the case of games like Chess, Go, Poker, etc., that have received and/or are receiving research effort, they have been around for hundreds of years, are very popular, and have rules than are simpler than Dominion's.

[WanderingWinder]

Trying to do it just learning like this, there's way too big a sample space - every board is a complex game in its own right; change one card and you're in a ditch; you could probably get this to work pretty well off of a fixed kingdom, for the whole pool, it will be exponentially more complex.

[theTrueMikeBrown]

I wrote a genetic algorithm that could learn how to play fairly well (better than a reasonable big money bot at least) on one given kingdom. It would take hundreds of games (about a minute or two) to come up with a good strategy (about 80% win rate against BM most of the time). Once you pit that bot against a big money bot on any other board it has to start from square one all over again.

My program had only cards from Dominion and Intrigue, and the results that it came up with were always fairly simple (no crazy combos, usually just BM+1 card) Sometimes it would come up with an entire deck draw engine, but nothing that a good player couldn't beat the pants off of.

I decided to let it run against random kingdoms to see if it could come up with a good general strategy. I let it run for weeks on a computer that I wasn't using. It never came up with anything. The problem is just way too complex. With all of the kingdom cards out there (in just the first two sets alone) the game is still too hard for a simple genetic algorithm to figure out. It would take some crazy computation to come up with a general strategy since the game is always compartmentalized by the number of possible cards in the game.

I still have the code (though I haven't looked at it in a few months) if anyone wants to take it farther, but I am done with it. It is way too hard.

[popsofctown]

You know, there's also the irreducible complexity issue.

[dpt]

http://forum.dominionstrategy.com/index.php?topic=7036.0

[PitzerMike]

You know, there's also the irreducible complexity issue.

I don't know, is there?

[Schlippy]

Why is it so complex? It would just be an implementation of an artificial neural network. Sure, it will take a few months to build a good database, but it should not be a problem of implementation.
I mean robots learn walking and flipping flapjacks "by themselves" with a relatively small amount of programming work involved, so why shouldn't it work for dominion? A Dominion game has a pretty low number of possible moves in a turn, because there are only 10 kingdom cards. It is not like Go where there are about 250 possible moves each turn which you have to evaluate. The number "real" of legal moves in Dominion is rather low most of the time, like in chess or in backgammon. "Real" means moves that actually make a difference. It doesn't make any difference if you play your Gold before your Silver or trash the first Copper in your hand instead of the second copper.

[WanderingWinder]

Why is it so complex? It would just be an implementation of an artificial neural network. Sure, it will take a few months to build a good database, but it should not be a problem of implementation.
I mean robots learn walking and flipping flapjacks "by themselves" with a relatively small amount of programming work involved, so why shouldn't it work for dominion? A Dominion game has a pretty low number of possible moves in a turn, because there are only 10 kingdom cards. It is not like Go where there are about 250 possible moves each turn which you have to evaluate. The number "real" of legal moves in Dominion is rather low most of the time, like in chess or in backgammon. "Real" means moves that actually make a difference. It doesn't make any difference if you play your Gold before your Silver or trash the first Copper in your hand instead of the second copper.

"There are only 10 possible kingdom cards" really implies an underestimation of the amount of complexity. There are all kinds of play decisions. I mean, okay, if you are playing just big money, maybe there aren't so many. But I have 4 actions - which order do I play them in? Sometimes it is obvious, a lot of times not quite, but the bigger issue is that the usually right rules most often have some exceptions, and this just kills you. Indeed, just whether or not to play a card to trigger a reshuffle can be pretty tricky.
Further, there are 10 kingdom cards, yes. But there are also 7 cards included in every game. And in a large percentage of games, there are other cards as well. So you are usually looking at 18ish different tings you could buy. Now, especially given that you often don't have the money to buy these, that's not so bad (it's a little simpler than most chess positions). But now I have two buys. Or three buys. Or seven buys. What do I do now? Not to mention ta the question of what to buy is dependent on *way* more than what is available, or what is available and what you can possibly do. What is in your deck? What is your opponent doing? What is going to be possible 5 turns from now?

But actually, the problem I think they're referring to is "Depends on the Kingdom". Yes, you can probably make an AI that learns one kingdom pretty well without *that* much work. But give it a new kingdom and it will be lost. Making one that can handle any kingdom is extraordinarily complex, and there are zany numbers of possible kingdoms.

[ragingduckd]

It is not like Go where there are about 250 possible moves each turn which you have to evaluate. The number "real" of legal moves in Dominion is rather low most of the time, like in chess or in backgammon.

There are "only" about 10^120 possible chess games, but solving that game tree is intractable beyond our wildest computational dreams.  Chess engines work by looking only modest number of moves into the future and choosing the best-looking intermediate outcome.

The lynchpin is deciding whether an intermediate outcome looks good or not.  It's relatively easy in chess, because differences in material are so important... losing your queen almost always matters more than the position on the rest of the board.  Robots that learn to walk use similarly simple heuristics... falling down is bad.

Assessing intermediate outcomes is harder in go because position often trumps material.  You can come out ahead by letting some stones get captured in exchange for a positional advantage elsewhere on the board.  Assessing positional strength is harder than counting queens, knights, and pawns, and go AIs are correspondingly weaker than chess AIs.

For all the reasons WW describes, assessing intermediate outcomes in Dominion is outrageously difficult.  Without that piece of the algorithm, Dominion AI's don't stand a chance.

[ftl]

I'd go the other way - I think you're understating the difficulty of Chess and Walking. They both seem easy because there've been countless, countless teams of people spending lots of time thinking and working on it for many years.

I would not be surprised that if you had a team of a few experienced programmers and/or Computer Science Ph.Ds spend a year or two working on it full-time, you would get a Dominion AI that plays as well as the best human players. But I don't think it's the sort of thing that a hobbyist would put together in their spare time over a couple of months.

[DG]

Don't be fooled by the existing bots. They generally make linear decisions. So if they play a warehouse they make all the decisions for the warehouse and discard the bad cards, only to find they don't have a copper in hand with a moneylender. As soon as you go beyond linear decisions it becomes very difficult very quickly. Even something simple like deciding to play a mandarin or goons as a terminal action can have a lot of consequences that a human player can analyze but a bot cannot.

Some of the learning AIs can substitute trial and error for logical decision making. For these AIs there is a difficulty in separating out the decision criteria that will be measured in each trial. So for the goons vs mandarin example, exactly what criteria will you measure by when deciding which card to play in each trial game?

[ragingduckd]

I'd go the other way - I think you're understating the difficulty of Chess and Walking. They both seem easy because there've been countless, countless teams of people spending lots of time thinking and working on it for many years.

I would not be surprised that if you had a team of a few experienced programmers and/or Computer Science Ph.Ds spend a year or two working on it full-time, you would get a Dominion AI that plays as well as the best human players. But I don't think it's the sort of thing that a hobbyist would put together in their spare time over a couple of months.

That's a reasonable-sounding story, but I don't think it's technically or historically accurate for chess.  To be fair, I don't actually know anything about teaching computers to walk.

Chess AIs were winning games against GMs in the late 70s using essentially the same algorithms that they use today (and which were invented in the 1950s).  Chess just happens to lend itself to evaluation using algorithms that were natural for humans to invent and for computers to implement.

Far more effort has gone into more useful areas of AI with far less success, and the same is true for AI in other popular games.  Go can't be addressed nearly as effectively with minimax search and AB pruning, and it's not hard to guess that these algorithms wouldn't do much for a Dominion AI either.

[blueblimp]

Why is it so complex? It would just be an implementation of an artificial neural network.

Neural networks aren't magic bullets. They need careful selection of inputs & outputs and fine-tuning. They are also not at all guaranteed to work for any particular problem, and are just one component of a solution anyway even when they do work.

[sudgy]

I've thought of something that miiiiiiiiiiiiiight work.  No promises, I'll try to program it and if it works say how it works.  Now, off I go to program the entire game first...

[ftl]

Good luck! I tried at one point, but it was just so much work I never really made any progress.

[Davio]

Doesn't the randomness of shuffling also make it a lot harder?
Every time you shuffle you're generating a new branch for our tree and in fact if you want to be exact you have to create a branch for every possible shuffle. You can cut back a bit by eliminating duplicates (Copper 1 is the same as Copper 2), but still, it gets to a very high number very fast.

So if we want to cut back on the number of branches, we have to do some pruning, but how do we do that? I guess the best way is to just create some random branches instead of a branch for every shuffle and evaluate the game state for each.

But how do we evaluate the game state? Counting VPs seems bad because of mega-turn engines. Average buying power then? Well, that's a bit shortsighted as we have to take our opponent and attacks into account. Attacks give us less buying power, but also limits that of our opponent.

And we can't even begin to try to do something with Goons or Monument, let alone Gardens.

[Warfreak2]

This sounds like a job for a Monte-Carlo tree search algorithm.

Your positional evaluation function would be, play out a large number of games from this point, following your buy order and some simple play rules, and count the proportion of them that you win. A similar thing has been very effective for Go AIs.

[sudgy]

I'm doing it in a COMPLETELY different way than you would think.  I will say, at the beginning it will always do random things.

But how do we evaluate the game state? Counting VPs seems bad because of mega-turn engines. Average buying power then? Well, that's a bit shortsighted as we have to take our opponent and attacks into account. Attacks give us less buying power, but also limits that of our opponent.

I have an idea for this, but this will be the hardest thing to do.

[sudgy]

Yay, the Cellar now works correctly!  This will take a while...  (If you notice, the Cellar is the first card in the card lists...)

EDIT: Cards are seeming to be easier now, just finished Chapel.  Worst problem was probably that it said I "trahed" a card...  (Also, I'm not going to say when I finish with every single card)