Dominion Strategy Forum

Please login or register.

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

Author Topic: DeepMind for Dominion  (Read 4497 times)

0 Members and 1 Guest are viewing this topic.

segura

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1230
  • Respect: +736
    • View Profile
DeepMind for Dominion
« on: April 24, 2020, 07:05:47 am »
0

I read yesterday that Google's self-learning AI project, which has been mainly known for excelling at chess and Go, is also pretty good at a RTS game like Starcraft.
My hunch is that this is far more complex than a turned based game like chess which features an average of 20 choices per turn and around 80 plies.

So if that AI is brillant at dealing with the giant decision space of a real time game with hidden information, shouldn't it be able to tackle a turn-based game with randomness like Dominion?

Is this feasible, is it likely that Google would be interested in that ... and would this hypothetical scenario ruin the game or actually imply a possible balancing tool for new cards (not that this is necessary)?
« Last Edit: April 24, 2020, 07:06:59 am by segura »
Logged

faust

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3028
  • Shuffle iT Username: faust
  • Respect: +4278
    • View Profile
Re: DeepMind for Dominion
« Reply #1 on: April 24, 2020, 09:41:06 am »
+3

I imagine you can train an AI to play a particular kingdom really well. The trouble comes from variability in the setup. Chess an Go always have the same moves available; I don't know much Starcraft, but I imagine that the pool of units is still significantly more limited than the pool of Dominion cards.

As neural networks have no way of "understanding" card texts, they could only "figure out" that two cards are similar through extensive training. Or I don't know, maybe you can write a more clever program that starts with a small number of cards, then checks new cards for similarities and uses its preexisting training to go on. So you could possibly do something, but it wouldn't be easy.
Logged
The quiet comprehending of the ending of it all

pubby

  • Minion
  • *****
  • Offline Offline
  • Posts: 534
  • Respect: +988
    • View Profile
Re: DeepMind for Dominion
« Reply #2 on: April 24, 2020, 08:37:49 pm »
+1

I'd assume machine learning could be used to estimate a general game plan (especially regarding attacks), but it wouldn't solve most of the problems with creating a Dominion AI. Mostly it'd just feed heuristics into traditional AI code. I think the more relevant problem is creating a fast way to estimate what a deck can do each turn, which AFAIK isn't a great fit for neural nets.

i imagine if they were going to do this for a card game, they'd use MtG since that's been shown to be NP-complete ("does the game end", i believe, was their qualifier problem), whereas dominion (for all non-trivial play examples, ie, player A, player B both draw and discard 5 cards, next turn) should be P, provided none of the truly unbounded vp cards (Monument, Plunder, Chariot Race) are present.

additionally, if they programmed their bot with the goal of "end the game while you have the most points" rather than "get the most points", Dominion should be solvable in P
Huh I think you mean "turing complete" instead of "NP-complete"?
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1046
  • Shuffle iT Username: heron
  • Respect: +1166
    • View Profile
Re: DeepMind for Dominion
« Reply #3 on: April 24, 2020, 09:15:51 pm »
0

i imagine if they were going to do this for a card game, they'd use MtG since that's been shown to be NP-complete ("does the game end", i believe, was their qualifier problem), whereas dominion (for all non-trivial play examples, ie, player A, player B both draw and discard 5 cards, next turn) should be P, provided none of the truly unbounded vp cards (Monument, Plunder, Chariot Race) are present.

additionally, if they programmed their bot with the goal of "end the game while you have the most points" rather than "get the most points", Dominion should be solvable in P
Huh I think you mean "turing complete" instead of "NP-complete"?

it's that too but given that each "knob" (whether the deck will run out, whether life will run out, etc) is unbounded (Gaea's Blessing, Lifelink, etc), you end up dealing with infinities, so given each deck is doing non-trivial things (draw a card, end your turn being the trivial play) it's impossible given two of all possible 60 card decks to say whether a game will end. ergo NP-complete.

This is not what NP-Complete means.
Perhaps you mean noncomputable? I don't really know anything about magic though.
Logged

ftl

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2056
  • Shuffle iT Username: ftl
  • Respect: +1342
    • View Profile
Re: DeepMind for Dominion
« Reply #4 on: April 24, 2020, 10:14:13 pm »
+2

At this point, with the number of different things AI's been made to do, I think it's highly likely that you could make an AI to do Dominion too.

"But at what cost" is the relevant question. A hobbyist tinkering at some code on the weekends - yeah, probably not. Google gives the project $50 million dollars and a team of AI PhDs? Sure, of course, I don't see why not.

I have no idea whether Google's "DeepMind" is the AI to do it or if you need a different one, I don't really have enough technical know-how about how exactly DeepMind works to judge how well it would fit Dominion.
Logged

crj

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1472
  • Respect: +1627
    • View Profile
Re: DeepMind for Dominion
« Reply #5 on: April 25, 2020, 12:43:30 pm »
0

Yeah, it feels like there are three separate AI challenges, here:
  • Learn the rules of the game
  • Learn how each card works
  • Learn to play well
You could sidestep the first two by baking the rules into the AI. Or you could bring in some natural-language-processing AI and feed it the rulebooks and card texts. Or you could have it figure them out by trial and error.

Baking in a strategy for playing well would clearly defeat the point of the exercise. And I'm assuming one would want it to figure out strategy by trial and error, rather than by knowing how to read the dominionstrategy wiki. (-8
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: DeepMind for Dominion
« Reply #6 on: April 27, 2020, 05:39:32 am »
0

I guess it comes down to what level of AI you expect. I think a hobby project could come up with an AI that is challenging to the average Dominion player, perhaps even to the average player on this forum.

Coming up with an AI that is challenging to the best players would be considerably harder and something of the level like AlphaZero (consistently better than the best professional players) is nothing you can do without professional support.

Furthermore, I think supervised learning might give you results faster, because you narrow the scope what an AI has to learn. You could e.g. have a categorizing AI judge whether an engine is viable and then have two separate AIs for Engine and Big Money. All these additional constraints will reduce the learning time, but also lead to a weaker AI because it can not explore the whole space of the game.

One final point: Because the Dominion ruleset still frequently changes, you need to be careful not to paint yourself in a corner. If a new Way to play the game is released, how do you ensure your AI can cope?
Logged

segura

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1230
  • Respect: +736
    • View Profile
Re: DeepMind for Dominion
« Reply #7 on: April 27, 2020, 09:25:36 am »
0

I wonder how the AI could deal with different setups. Starcraft has hidden information but the options are identical in all games. A self teaching AI might have a hard time to meta-learn (judge Kingdoms).
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: DeepMind for Dominion
« Reply #8 on: April 27, 2020, 03:39:52 pm »
0

Actually the decision whether to play engine or BM is probably easier than I thought. You just let the AI play a few games against each other and its instance which performs the best on average gets to decide. That still doesn't solve the problem how to come up with a good engine player in the first place.

I wonder how the AI could deal with different setups. Starcraft has hidden information but the options are identical in all games. A self teaching AI might have a hard time to meta-learn (judge Kingdoms).
Well ultimately every card is a source of a limited set of resources (Action, Card, Buy, $, VP, ...). So the AI just needs to learn what the expected gain of playing a certain card is and cards with similar expected gains can replace each other.

What I am most worried about would be play decisions like which card to topdeck with Harbringer or which Pawn choices you should take. The other thing that will be hard is exceptional cards that warp how the game is played (Tournament, Possession).
Logged

ftl

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2056
  • Shuffle iT Username: ftl
  • Respect: +1342
    • View Profile
Re: DeepMind for Dominion
« Reply #9 on: April 27, 2020, 10:49:29 pm »
+1

I guess it comes down to what level of AI you expect. I think a hobby project could come up with an AI that is challenging to the average Dominion player, perhaps even to the average player on this forum.

I think at this point, there's just so. many. cards. that even a halfway competent AI is beyond the scope of a hobby project. There's just a lot of weird interactions that aren't hard to program but take time. Just implementing the rules of all the cards - and getting them to work right - is nontrivial. It's even more work than it seems because they have to be implemented in a way that they can be manipulated and reasoned about, even for simple internal questions like "if I play this card, will it trigger a reshuffle".

There is a heck of a lot of work that would have to go into an AI where the "AI" part of it is absolutely minimal, just a bot that picks one BM+X strategy per board.

And that stuff is "table stakes", so to speak. Price of entry, before you actually get to the interesting questions.
Logged

ftl

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2056
  • Shuffle iT Username: ftl
  • Respect: +1342
    • View Profile
Re: DeepMind for Dominion
« Reply #10 on: April 27, 2020, 11:04:21 pm »
+3

By the way, this thread led me down a rabbit hole of reading about how AlphaGo and AlphaZero work. I don't really know what resources are the best, but it was fun to google and read about, I would recommend anyone who thinks thinking about AI is cool go down that rabbit hole for a bit.

Really puts into perspective that for a real AI, questions like how to decide "BM or Engine" or "What card to topdeck with Harbinger" just aren't the sort of questions the AI designer is going to be thinking about, it's all about how to set up the problem so that ML techniques can be applied to learn the answer to *all* those decisions in the same way.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: DeepMind for Dominion
« Reply #11 on: April 28, 2020, 04:15:56 am »
0

I think at this point, there's just so. many. cards. that even a halfway competent AI is beyond the scope of a hobby project. There's just a lot of weird interactions that aren't hard to program but take time. Just implementing the rules of all the cards - and getting them to work right - is nontrivial. It's even more work than it seems because they have to be implemented in a way that they can be manipulated and reasoned about, even for simple internal questions like "if I play this card, will it trigger a reshuffle".
Sorry, I have not been clear. I was only talking about the AI part. Implementing all of Dominion would be a much longer task. If I were to attempt something like a Dominion AI, I would do a proof of principle with a selected set of cards (probably you want to some events or landmarks, too). Then you might want to talk to Stef to see if you can realize the same with the actual game.

By the way, this thread led me down a rabbit hole of reading about how AlphaGo and AlphaZero work. I don't really know what resources are the best, but it was fun to google and read about, I would recommend anyone who thinks thinking about AI is cool go down that rabbit hole for a bit.

Really puts into perspective that for a real AI, questions like how to decide "BM or Engine" or "What card to topdeck with Harbinger" just aren't the sort of questions the AI designer is going to be thinking about, it's all about how to set up the problem so that ML techniques can be applied to learn the answer to *all* those decisions in the same way.
Well there is also the aspect that they wanted to show that it can be done without any guidance. I don't know if in general the approach to supply no input at all is the best. Of course, games are also the best case scenario, because the evaluation function is well defined (you either win or you don't).

At first I wanted to add something about how the state of a Dominion game is much more difficult to describe than that of Go, but I'm not so sure anymore. There are around 200 cards in any given game and you need 4~5 bits to store where a card is. In addition ~100 bits to store the kingdom information. For Go you have a 19*19 board with 3 bits per field (empty, white, black). So I would get 900~1100 bits for Dominion and ~720 for Go.
But then the decision space of Dominion is much smaller. For every given game state there are probably less than ~30 possible choices whereas for Go you start of with 361 choices.

It is probably still harder to learn than Go though, because one bit flip in the game state (say replacing Pawn with Chapel) seems to have a much more severe impact than replacing one stone on the Go board (full disclosure, I did not play Go enough to check that this is true).
Logged

Sauter

  • Pawn
  • **
  • Offline Offline
  • Posts: 3
  • Respect: 0
    • View Profile
Re: DeepMind for Dominion
« Reply #12 on: April 28, 2020, 04:55:46 pm »
0

It is probably still harder to learn than Go though, because one bit flip in the game state...seems to have a much more severe impact than replacing one stone on the Go board

Hi, Go player of six years here. I get the point of what you're saying, but there are tons of times in an average game of Go where flipping a bit would change the outcome of the game. (I guess you can compare it to skipping someone's turn in a game of chess, since each non-empty space in Go was someone's turn).

As a human, I will say that Go has the steepest learning curve of any game, hands down. At the same time, I can see why learning to generalize to any given Dominion board would be hell for an AI.
« Last Edit: April 28, 2020, 05:02:00 pm by Sauter »
Logged

marksim

  • Ambassador
  • ***
  • Offline Offline
  • Posts: 34
  • Respect: +21
    • View Profile
Re: DeepMind for Dominion
« Reply #13 on: April 28, 2020, 09:05:23 pm »
+1

My favorite notion re: AI is to petition dominion.games / @stef to allow a simple DSL to be created that gives rules for how to play the game given the presence of certain cards.  Then those scripts get loaded up and bots select them based on the cards present and the current win rates.  Every win from a bot based on the script gives a small (small!) ranking bonus to the uploader.  Losses do not give dings, so you are encouraged to try things out and upload strategies to play against, but also improve them over time.  Overall this improves bots AND improves players as they have to come up with nuanced rules and ways of systematically thinking about cards and how to win.

I think that's the only way you're ever going to actually see an AI develop is if it has thousands of games as samples and thus the cooperation of dominion.games.
Logged

ftl

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2056
  • Shuffle iT Username: ftl
  • Respect: +1342
    • View Profile
Re: DeepMind for Dominion
« Reply #14 on: April 28, 2020, 11:00:58 pm »
0

It is probably still harder to learn than Go though, because one bit flip in the game state...seems to have a much more severe impact than replacing one stone on the Go board

Hi, Go player of six years here. I get the point of what you're saying, but there are tons of times in an average game of Go where flipping a bit would change the outcome of the game. (I guess you can compare it to skipping someone's turn in a game of chess, since each non-empty space in Go was someone's turn).

I don't know Go at all, but in chess it's pretty easy to see that "changing a bit" (the color of one piece) could trivially make the game change completely (change a black queen to a white queen!) ...or moving a piece by one square in one direction can pretty obviously make the difference between a clear win and a clear loss. I'm completely unsurprised that it's like that in Go too.

I think the fact that those sort of subtleties matter is pretty universal among interesting games. If they didn't, those games would quickly stop being interesting and would quickly become solved!
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: DeepMind for Dominion
« Reply #15 on: April 29, 2020, 03:51:00 am »
0

I guess I fell for the psychological fallacy that you consider the things you know more about as having more depth than things you know less about (relevant xkcd https://xkcd.com/915/). Of course there are also boring bit flips in Dominion (Copper in-the-trash or not-bought).
Logged

() | (_) ^/

  • Minion
  • *****
  • Offline Offline
  • Posts: 632
  • Shuffle iT Username: p4ddy0d00rs
  • Nemo dat quod non habet.
  • Respect: +521
    • View Profile
    • BGG profile
Re: DeepMind for Dominion
« Reply #16 on: April 29, 2020, 08:33:34 am »
0

I guess I fell for the psychological fallacy that you consider the things you know more about as having more depth than things you know less about (relevant xkcd https://xkcd.com/915/). Of course there are also boring bit flips in Dominion (Copper in-the-trash or not-bought).

Oh, an interesting interpretation of that xkcd! I always took its meaning to be “everything is deep.”
Logged

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2850
    • View Profile
Re: DeepMind for Dominion
« Reply #17 on: May 24, 2020, 08:53:41 am »
+1

I think people are vastly underestimating (or rather, perhaps not estimating at all and "bypassing") the number of "calculator friendly" handicaps available to a hypothetical Dominion AI.  Stuff that it's just better to have a machine do.  The machine makes railroad better than John Henry because it runs on coal.

In Jeopardy, the advantage was buzzer pressing, for the demo they let the AI get the full advantage of seeing the permission light and reacting in .0001 seconds instead of the standard 0.7 seconds and always got first crack at a question so it could answer lots of questions wrong and still win.  In Starcraft, there was infinite micro, which would be the second greatest benefit that I'm aware of, the ability to spend essentially no time telling an individual unit to do something different from its peers.  Starcraft was a balance between exploiting that advantage and having a similar "god there's so many things for your grade school teacher to cover" dimension similar to Dominion. 
In an FPS with reduced character size it'd be so trivial to exploit those kinds of advantages that people don't write AIs to do it because it's too boring and easy.  The handicap is too huge.  That's assuming the design of the FPS is such that expert players miss a little bit or have to slow down to take their shots, of course, but with very much of either it becomes so huge.

Chess's AI friendly task is checkmate puzzle solving.  But the way chess works, the really hard part happens before that even comes up, one player generates strong advantage before mating puzzles start to really be presented. So mostly chess was a matter of making the AI smart enough to win, with no calculator based advantages at all.  I don't know go well but I expect it's a pretty similar story.  I think it's possibly kind of true that the amount of time the AI had to not lose before it could start checkmate-puzzling off of information advantages is more generous in chess than in go, that is possibly the meaningful way of looking at it.  It could just be that Go midgames are flat out harder, though.

What Dominion is gonna have is greening phase and I think that should be appreciated.  The decision to start buying provinces, or to buy a final gold knowing exactly how many times you'll draw it if you really sit down and think about it, the exact probabilities involved in Duchy dancing (with perfect deck tracking.  I'm sure our highest tier players have a vague idea of what's likely soon towards the end of a dominion game, but don't think they can recite their opponent's remaining 8 cards before next reshuffle and their own consistently.  And it's almost totally about knowing what the next hands look like and not any of the big brain strategy of needing just one village mixed in with Ironmonger on X board because an expert intuits which drawing terminals are going to be the right purchases at the right time when hitting 5 - it's just stuff like "yeah if you actually counted up every single card, there's only a 87% chance your opponent can end Duchy dance prematurely not 92%, therefore you -should- actually buy that spice merchant and expect to nuts topdeck it for a province-duchy turn, or whatever, stuff like that.

And those kinds of advantages are going to be pretty big in a probablistic game where the players should be expected to trade wins anyway, even just off brutish data gluttony on the timings of village genus cards and smithy genus cards and woodcutter genus cards at certain times on certain boards from reading tons of logs.

So, my expectation is, using that handicap, beating every single human should be -easier- than go (i don't want to say chess) because a significant subsidy exists, and the difficulty in memory based card counting + essentially discovering new game specific texas-hold-em odds for endgames exists.  It's still a jillions and jillions of dollars thing though.

tl;dr if you are up a knight in chess I don't think you need a ti84 to checkmate without throwing away your win 15% of the time, if you played more correctly enough to have a similar strength deck to your opponent but with a 5$ where he has a 4$ there's a brutish way even a ti 84 would give you an appreciable winrate bump, and I think that could be considered.  It overrides the subtle difference between what ironworks and smugglers truly mean I would think.  I could see how you might think there are just so many cards that can be classified in so many ways that maybe it would take forever and ever to program the AI to where it's never hardthrowing entire games over things like, "Oh, this board has transmute on it and that's a way to gain action cards, so the principle that Graverobber generally counts as a +buy has force in this kingdom".  But I think with the millions of dollars and as many people working on it as worked on chess, you eventually knock every single one of those bowling pins over, then you get into the range where the computer is like 5% worse than Stef and largely mirroring him, but doing perfect deck tracking stuff on the ends of games and winning 17 game series consistently.
« Last Edit: May 24, 2020, 08:58:25 am by popsofctown »
Logged

segura

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1230
  • Respect: +736
    • View Profile
Re: DeepMind for Dominion
« Reply #18 on: May 24, 2020, 09:15:01 am »
0

Chess's AI friendly task is checkmate puzzle solving.  But the way chess works, the really hard part happens before that even comes up, one player generates strong advantage before mating puzzles start to really be presented. So mostly chess was a matter of making the AI smart enough to win, with no calculator based advantages at all.  I don't know go well but I expect it's a pretty similar story.  I think it's possibly kind of true that the amount of time the AI had to not lose before it could start checkmate-puzzling off of information advantages is more generous in chess than in go, that is possibly the meaningful way of looking at it.  It could just be that Go midgames are flat out harder, though.
I don't think that this is how chess engines works. They have mainly become better due to the increase of speed of calculation and only partially due to the better design of the evaluation function. That's where humans are still far better.

The impressive thing about AlphaZero is that the machine tought itself how to play chess well without any human guidance and the resulting play is more human (e.g. less materialistic, sacrificing material for long-terman positionala advantages that are hard to evaluate and impossible to calculate to the end) than that of an ordinary chess engine.

Dominion seems far more tricky than a deterministic abstract like chess to me. It has stochastic elements, there are far more "pieces" and every game is different. I guess that DeepMind would have to play one Kingdom a zillion times over before it could move to the next one. Then it would have to learn to evaluate how the strength of a card changes during a game, partly depending on what the opponents do, and the "metagame", i.e. how the strength of a card varies among Kingdoms.
I guess it is possible but this seems like something a human mind can learn much faster, albeit less perfectly.
Logged

Wizard_Amul

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 150
  • Respect: +158
    • View Profile
Re: DeepMind for Dominion
« Reply #19 on: May 24, 2020, 01:06:03 pm »
0

We're one more step closer to possibly using Deep Mind for Dominion; the DeepMind team has been working on incorporating a time horizon into the AI, allowing it to put more weight towards a longer term payoff.

DeepMind blog about Agent 57 AI: https://deepmind.com/blog/article/Agent57-Outperforming-the-human-Atari-benchmark
Video by someone else discussing the Agent 57 AI:

From the blog:
"We introduced the notion of a meta-controller that adapts the exploration-exploitation trade-off, as well as a time horizon that can be adjusted for games requiring longer temporal credit assignment."

"Time horizon: Some tasks will require long time horizons (e.g. Skiing, Solaris), where valuing rewards that will be earned in the far future might be important for eventually learning a good exploitative policy, or even to learn a good policy at all. At the same time, other tasks may be slow and unstable to learn if future rewards are overly weighted. This trade-off is commonly controlled by the discount factor in reinforcement learning, where a higher discount factor enables learning from longer time horizons."
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: DeepMind for Dominion
« Reply #20 on: May 25, 2020, 10:11:47 am »
+1

I think people are vastly underestimating (or rather, perhaps not estimating at all and "bypassing") the number of "calculator friendly" handicaps available to a hypothetical Dominion AI.  Stuff that it's just better to have a machine do.  The machine makes railroad better than John Henry because it runs on coal.
[...]
What you are referring to is also implemented for Chess and Go. You run the game for a few steps with your current evaluation function and then assess where you stand. I would not dare to say whether this gives you more benefit in Dominion as compare to the other two games.

Dominion seems far more tricky than a deterministic abstract like chess to me. It has stochastic elements, there are far more "pieces" and every game is different. I guess that DeepMind would have to play one Kingdom a zillion times over before it could move to the next one.
In the end you have a function to project from a game state onto a given set of actions. I don't believe that there is a huge qualitative difference between the space of Dominion and the space of Go. Chess might be indeed a bit smaller.
Logged

Umadin

  • Steward
  • ***
  • Offline Offline
  • Posts: 28
  • Respect: +19
    • View Profile
Re: DeepMind for Dominion
« Reply #21 on: May 21, 2021, 03:25:29 am »
0

Dominion in complexity is simple when compared to something like Alphastar.  The complexity of the game learning and strategy in real time  far exceeds what you see in dominion.  I would love to see an AI engine for dominion.
Logged

Honkeyfresh

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 245
  • Respect: +95
    • View Profile
Re: DeepMind for Dominion
« Reply #22 on: May 23, 2021, 02:45:10 pm »
+1

I read yesterday that Google's self-learning AI project, which has been mainly known for excelling at chess and Go, is also pretty good at a RTS game like Starcraft.
My hunch is that this is far more complex than a turned based game like chess which features an average of 20 choices per turn and around 80 plies.

So if that AI is brillant at dealing with the giant decision space of a real time game with hidden information, shouldn't it be able to tackle a turn-based game with randomness like Dominion?

Is this feasible, is it likely that Google would be interested in that ... and would this hypothetical scenario ruin the game or actually imply a possible balancing tool for new cards (not that this is necessary)?

Go is more complex that Dominion.  Starcraft too (as AI can still only just crack the top 99.8 of players) But Go is (was) known as the most complex game in the world with the most possible changes in strategies and permutations.  However, due to its RIDICULOUSLY intricate set of rules Magic The gathering has recently passed Go as the most complex game in the world. 

https://www.technologyreview.com/2019/05/07/135482/magic-the-gathering-is-officially-the-worlds-most-complex-game/

Quote
“Magic: The Gathering” is officially the world’s most complex game
A new proof with important implications for game theory shows that no algorithm can possibly determine the winner.

Magic: The Gathering is a card game in which wizards cast spells, summon creatures, and exploit magic objects to defeat their opponents.

In the game, two or more players each assemble a deck of 60 cards with varying powers. They choose these decks from a pool of some 20,000 cards created as the game evolved. Though similar to role-playing fantasy games such as Dungeons and Dragons, it has significantly more cards and more complex rules than other card games.

And that raises an interesting question: among real-world games (those that people actually play, as opposed to the hypothetical ones game theorists usually consider), where does Magic fall in complexity?

Today we get an answer thanks to the work of Alex Churchill, an independent researcher and  board game designer in Cambridge, UK; Stella Biderman at the Georgia Institute of Technology; and Austin Herrick at the University of Pennsylvania.

His team has measured the computational complexity of the game for the first time by encoding it in a way that can be played by a computer or Turing machine. “This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” they say.

First, some background. An important task in computer science is to determine whether a problem can be solved in principle. For example, deciding whether two numbers are relatively prime (in other words , whether their largest common divisor is greater than 1) is a task that can be done in a finite number of well-defined steps and so is computable.

In an ordinary game of chess, deciding whether white has a winning strategy is also computable. The process involves testing every possible sequence of moves to see whether white can force a win.

But while both these problems are computable, the resources required to solve them are vastly different.

This is where the notion of computational complexity comes in. This is a ranking based on the resources required to solve the problems.

In this case, deciding whether two numbers are relatively prime can be solved in a number of steps that is proportional to a polynomial function of the input numbers. If the input is x, the most important term in a polynomial function is of the form Cxn, where C and n are constants.  This falls into a class known as P, where P stands for polynomial time.

By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. If the input is x, the most important term in an exponential function is of the form Cnx, where C and n are constants. And as x increases, this becomes bigger much faster than Cxn. So this falls into a category of greater complexity called EXP, or exponential time.

Beyond this, there are various other categories of varying complexity, and even problems for which there are no algorithms to solve them. These are called non-computable.

Working out which complexity class games fall into is a tricky business. Most real-world games have finite limits on their complexity, such as the size of a game board. And this makes many of them trivial from a complexity point of view. “Most research in algorithmic game theory of real-world games has primarily looked at generalisations of commonly played games rather than the real-world versions of the games,” say Churchill and co.

So only a few real-world games are known to have non-trivial complexity. These include Dots-and-Boxes, Jenga, and Tetris. “We believe that no real-world game is known to be harder than NP previous to this work,” says Churchill and co.

The new work shows that Magic: the Gathering is significantly more complex. The method is straightforward in principle. Churchill and co begin by translating the powers and properties of each card into a set of steps that can be encoded.

They then play out a game between two players in which the play unfolds in a Turing machine.  And finally they show that determining whether one player has a winning strategy is equivalent to the famous halting problem in computer science.

This is the problem of deciding whether a computer program with a specific input will finish running or continue forever. In 1936, Alan Turing proved that no algorithm can determine the answer. In other words, the problem is non-computable.

So Churchill and co’s key result is that determining the outcome of a game of Magic is non-computable. “This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable,” they say.

That’s interesting work that raises important foundational questions for game theory. For example, Churchill and co say the leading formal theory of games assumes that any game must be computable. “Magic: The Gathering does not fit assumptions commonly made by computer scientists while modelling games,” they say.

That suggests computer scientists need to rethink their ideas about games, particularly if they hope to produce a unified computational theory of games. Clearly, Magic represents a fly in the enchanted ointment as far as this is concerned.

Ref: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete
« Last Edit: May 23, 2021, 02:46:41 pm by Honkeyfresh »
Logged

Jack Rudd

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1248
  • Shuffle iT Username: Jack Rudd
  • Respect: +1239
    • View Profile
Re: DeepMind for Dominion
« Reply #23 on: May 23, 2021, 09:40:43 pm »
0

Alex Churchill, huh. I used to play Diplomacy with him.
Logged
Centuries later, archaeologists discover the remains of your ancient civilization.

Evidence of thriving towns, Pottery, roads, and a centralized government amaze the startled scientists.

Finally, they come upon a stone tablet, which contains but one mysterious phrase!

'ISOTROPIC WILL RETURN!'

crj

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1472
  • Respect: +1627
    • View Profile
Re: DeepMind for Dominion
« Reply #24 on: May 24, 2021, 08:01:47 am »
0

Alex Churchill, huh, I do play Dominion with him. (-8
Logged
Pages: [1] 2  All
 

Page created in 0.099 seconds with 22 queries.