Dominion Strategy Forum

Please login or register.

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

Author Topic: Turing Machine from Dominion Cards and Mechanics  (Read 5798 times)

0 Members and 1 Guest are viewing this topic.

Commodore Chuckles

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1284
  • Shuffle iT Username: Commodore Chuckles
  • Respect: +1971
    • View Profile
Turing Machine from Dominion Cards and Mechanics
« on: August 15, 2018, 09:51:28 pm »
+2

Thoughts:

player 1's deck could be used for memory; Silvers for on bits and Coppers for off bits, since those are the biggest piles in the game.

Player 2's deck would store the instructions. Masquerade can be used to flip bits by switching out Silvers and Coppers from Player 1's hand.

Something like Shanty Town would be used for decision making; I'm not sure how exactly that could work. There also has to be a way to jump to any part of Player 2's deck so that instructions can be executed; I'm also not sure about that.

Player 2 would have to manipulate Player 1's hand so that memory can be read. Hands in Dominion are unordered, but this can be fudged a bit by saying the bit read/written is the last card drawn. Governor can draw Player 1's cards. The Fear Hex can force them to top deck (We'll say they have to top deck in reverse order they drew, to keep things in order) but the randomness factor of the Hexes would also have to be fudged somehow.
Logged

silvern

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 126
  • Respect: +170
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #1 on: August 17, 2018, 05:42:56 pm »
0

This sounds really cool, but I need someone to help explain turing machines to me for the third time  ;)
Logged

ConMan

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1400
  • Respect: +1705
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #2 on: August 19, 2018, 08:54:37 pm »
+1

This sounds really cool, but I need someone to help explain turing machines to me for the third time  ;)
A Turing machine is an abstracted version of a computer with (a) infinite storage and (b) no human intervention after setting up the initial input and pressing "go".

One common Turing machine set-up (there are a few variations but they can be proven to be equivalent to each other) is that you have an infinitely long strip of paper (or "tape") that is split into squares that can each hold one "bit" of information, where a bit is a single character from some kind of alphabet (the obvious choice is the binary set {0, 1} but you could make it the English alphabet or whatever you like, as long as there are a finite number of choices).

You also have a machine that points at a square on the tape and is able to (a) read the character on the square, (b) change that character to another one, and (c) move one square either left or right on the tape. The machine decides how to do this based on a bunch of instructions it has, which are stored in a variety of "states" - think of it like a Choose Your Own Adventure book where every page just has a set of rules like this:

  • If the character is "A", then write "B", move one square left and turn to page 1184.
  • If the character is "B", then write "A", move one square right and turn to page 578.
  • If the character is "C", then STOP.
  • ...
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #3 on: August 20, 2018, 07:36:41 am »
+1

Some of the decisions in Dominion are made by the player, e.g. which card to play, buy, or gain. What rules should we make regarding these decisions? Below I will outline a basic Touring machine in Dominion, where these choices are dictated by a set of instructions, i.e., not rooted in the rules of Dominion.

The basic idea is to use the deck and the hand of the player as storage (Copper and Silver as 0 and 1, and Gold as blank). Keeping track of the order in which you drew the cards to decide which one is currently active (the last one you drew). The underlying method to work on the storage uses the following algorithm:

Kingdom: Overlord, Crown, Mandarin, Watchtower, Ambassador, Smuggler, Lurker, Treasure Map, Smithy, Pawn
Setup: Mandarin in trash, Watchtower and 6 Overlords (OL) in hand, in the previous turn, I gained a Copper, Silver, and Gold

OL1 as Crown
... OL2 as Crown
... ... OL3 as Crown
... ... ... OL4 as Crown
... ... ... ... OL5 as Crown
... ... ... ... ... OL6 as Treasure Map, trash OL6
... ... ... ... ... OL6 as Lurker, gain/trash Mandarin, put OL1-5 on deck
... ... ... ... OL5 as Lurker, gain OL6 on deck
... ... ... OL4 as Smithy, draw OL1-3
... ... OL3 as Smithy, draw OL4-6
... OL2 as X

The important part of this algorithm is that it keeps the hand unmodified and allows to play one action X every cycle. To implement the Turing machine, we can modify the currently active card using X = Pawn or X = Mandarin by adding another card to our hand or putting the active one back on the deck. Overwriting the storage depends on the cards used to store the information. Writing is a combination of returning the old card with X = Ambassador, gaining a new card with X = Smuggler, watchtowering it on top of the deck, and then drawing it with X = Pawn.
Logged

paulfc

  • Pawn
  • **
  • Offline Offline
  • Posts: 1
  • Respect: +3
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #4 on: September 04, 2018, 12:43:11 am »
+3

I think the right version of this question is: is there a computable way of translating a program into a dominion game state, such that player 1 has a winning strategy iff the program halts? This is what it would usually mean when we say that a game is Turing complete.

I think it's a good question. Probably the answer is yes, but I don't think that any of the mechanisms suggested so far will work.

You would almost certainly need to make the piles infinite.

One way to approach it is to implement a two-stack automata, a state machine that is allowed to push and pop from either of two stacks (which is Turing complete). For example, one stack could be implemented with the top of the deck and the other can be implemented as a chain of throne rooms / processions. I think this would be incredibly complex and challenging.
Logged

King Leon

  • Witch
  • *****
  • Offline Offline
  • Posts: 478
  • Respect: +406
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #5 on: October 10, 2018, 02:06:29 am »
+1

Villagers and Coffers are infinite, you can save two slots of arbitrary data in a Dominion game. Loops with Lurker, Graverobber or Rogue allow you to have infinite operations. It is easy to build a two-stack push down automaton. That proves, that Dominion is Turing-complete.
Logged

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 22
  • Respect: +37
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #6 on: October 10, 2018, 04:35:37 pm »
0

Villagers and Coffers are infinite, you can save two slots of arbitrary data in a Dominion game. Loops with Lurker, Graverobber or Rogue allow you to have infinite operations. It is easy to build a two-stack push down automaton. That proves, that Dominion is Turing-complete.

Yes, I agree, all you need is to have these two piles which you can control freely. One non-trivial issue, though, is input encoding. You would need to show that your TM/2-counter/stack machine encoding (two piles + trash-gainer + deterministic player decisions) does the same as the respective machine on any input. Now there are infinitely many inputs and you need to encode them with the rest of Dominion. I think this could be done by assuming no randomness and to predetermine card order after shuffling based on what input should be encoded.

So the general question whether some game state can be reached is undecidable. It would also be interesting what other questions are undecidable as well, especially if you factor in randomness again. And it might be interesting where the boundary between decidability/undecidability lies. For instance, it is probably possible to reason about expected outcomes of competing Big Money strategies (assuming that you find suitable definition), but are all questions concerning Big Money decidable?
Logged

ConMan

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1400
  • Respect: +1705
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #7 on: October 10, 2018, 06:25:16 pm »
0

Villagers and Coffers are infinite, you can save two slots of arbitrary data in a Dominion game. Loops with Lurker, Graverobber or Rogue allow you to have infinite operations. It is easy to build a two-stack push down automaton. That proves, that Dominion is Turing-complete.

Yes, I agree, all you need is to have these two piles which you can control freely. One non-trivial issue, though, is input encoding. You would need to show that your TM/2-counter/stack machine encoding (two piles + trash-gainer + deterministic player decisions) does the same as the respective machine on any input. Now there are infinitely many inputs and you need to encode them with the rest of Dominion. I think this could be done by assuming no randomness and to predetermine card order after shuffling based on what input should be encoded.
The top of your deck is essentially a stack, and top-decking/drawing are your push-pop actions. So as long as you control how much you can draw (or you assume some kind of infinite deck), you never have to worry about shuffling.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #8 on: October 11, 2018, 03:51:02 pm »
+1

I think there may be two separate questions going on in this thread at the same time.

The first question I'd describe as something like:
1) Can you make an encoding of a Turing machine's program and state as Dominion states, where if the Turing machine can perform a step, the Dominion state can perform the same step using legal game actions?

Most of the posts seem to be concerned with this question, and I think the answer is very likely yes. However, this question is different from these questions:
2a) Can a computer program determine if a starting Dominion state A can reach another Dominion state B?
2b) Can a computer program determine if, from a starting Dominion state A, it is possible for player 1 have more points than player 2 at the end of this turn?

If there's no computer program that can solve 2a) or 2b), that would be the typical way of saying that it is undecidable/Turing complete to reason about Dominion.

Note that even if the answer to 1) is yes, it doesn't necessarily imply that 2a) or 2b) are impossible. To see this, consider the game Calvinball-Dominion, which is just like Dominion except that in your action phase, you also have the option to move a card from any zone to another as many times as you want, whenever you want. This game can certainly encode a Turing machine in its possible states by just moving stuff around arbitrarily. But it is also easy to reason about this game: given a starting state, you can basically reach any state that has the same cards in the kingdom.

If we're just trying to answer question 1), I think we're basically there. I have a bit to add that with opponent cooperation, you can make the top of their deck a stack as well: add to the top of their deck with Sea Hag (Curse) or gaining Embassy (Silver), with them topdecking with Watchtower for the silvers, and remove from the top of the deck with Jester.

Question 2) seems way harder to resolve and I'm not sure what the answer is.
Logged

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 22
  • Respect: +37
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #9 on: October 11, 2018, 05:23:23 pm »
0

Villagers and Coffers are infinite, you can save two slots of arbitrary data in a Dominion game. Loops with Lurker, Graverobber or Rogue allow you to have infinite operations. It is easy to build a two-stack push down automaton. That proves, that Dominion is Turing-complete.

Yes, I agree, all you need is to have these two piles which you can control freely. One non-trivial issue, though, is input encoding. You would need to show that your TM/2-counter/stack machine encoding (two piles + trash-gainer + deterministic player decisions) does the same as the respective machine on any input. Now there are infinitely many inputs and you need to encode them with the rest of Dominion. I think this could be done by assuming no randomness and to predetermine card order after shuffling based on what input should be encoded.
The top of your deck is essentially a stack, and top-decking/drawing are your push-pop actions. So as long as you control how much you can draw (or you assume some kind of infinite deck), you never have to worry about shuffling.

You are right, you can do that with some initialization. In that case, we would another form of input. The opponent could for instance pass "inputs" via Masquerade. Maybe that would even make more sense than using the deck for input encoding. However, the opponent would need to be non-random. 
Logged

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 22
  • Respect: +37
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #10 on: October 11, 2018, 05:47:17 pm »
0

I think there may be two separate questions going on in this thread at the same time.

The first question I'd describe as something like:
1) Can you make an encoding of a Turing machine's program and state as Dominion states, where if the Turing machine can perform a step, the Dominion state can perform the same step using legal game actions?

Most of the posts seem to be concerned with this question, and I think the answer is very likely yes. However, this question is different from these questions:
2a) Can a computer program determine if a starting Dominion state A can reach another Dominion state B?
2b) Can a computer program determine if, from a starting Dominion state A, it is possible for player 1 have more points than player 2 at the end of this turn?

If there's no computer program that can solve 2a) or 2b), that would be the typical way of saying that it is undecidable/Turing complete to reason about Dominion.

I agree, most likely you can encode a TM. As noted in previous posts, this is actually quite simply, because you do not need a lot more than two counters/stacks.
Regarding 2a and 2b, I think you should not confuse Turing completeness and undecidability. 2a (and maybe also 2b) follow from Turing completeness, but I guess the opposite does not hold.

Note that even if the answer to 1) is yes, it doesn't necessarily imply that 2a) or 2b) are impossible. To see this, consider the game Calvinball-Dominion, which is just like Dominion except that in your action phase, you also have the option to move a card from any zone to another as many times as you want, whenever you want. This game can certainly encode a Turing machine in its possible states by just moving stuff around arbitrarily. But it is also easy to reason about this game: given a starting state, you can basically reach any state that has the same cards in the kingdom.

If we're just trying to answer question 1), I think we're basically there. I have a bit to add that with opponent cooperation, you can make the top of their deck a stack as well: add to the top of their deck with Sea Hag (Curse) or gaining Embassy (Silver), with them topdecking with Watchtower for the silvers, and remove from the top of the deck with Jester.

Question 2) seems way harder to resolve and I'm not sure what the answer is.

That is where I was getting at in my post. Answering 2a for general boards without any restrictions on players' strategies is undecidable, but may be decidable in some scenarios.

The observations regarding Turing-completeness imply that making a perfect bot is basically impossible.  Given specific restricted scenarios/board, the situation may be different.

I need to think a bit more about question 2, but probably simulation (combined with some form of optimisation) is the best tool to answer such questions.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #11 on: October 11, 2018, 06:48:47 pm »
+2

Next step: simulate Dominion in Dominion.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Jfrisch

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +166
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #12 on: October 25, 2018, 12:19:47 am »
+1

I've been asking (Math and CS) friends this question for a while now. In particular some variant of question 2.

Being able to embed a turing machine (which is not a totally well defined notion) doesn't seem to (necessarily) have any implication for the undecidability for the game.

Dominion with finite piles is really complicated (i.e. question 2 and variants i.e. winning in 1, getting from 1 state to another presumably these are all the same computability strength). . It seems that the win in turn one question is likely decidable (though proving this seems ferociously hard). But I have no idea about infinite pile dominion.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #13 on: October 25, 2018, 01:22:25 am »
0

I've been asking (Math and CS) friends this question for a while now. In particular some variant of question 2.

Being able to embed a turing machine (which is not a totally well defined notion) doesn't seem to (necessarily) have any implication for the undecidability for the game.

Dominion with finite piles is really complicated (i.e. question 2 and variants i.e. winning in 1, getting from 1 state to another presumably these are all the same computability strength). . It seems that the win in turn one question is likely decidable (though proving this seems ferociously hard). But I have no idea about infinite pile dominion.

Like we said before, there is still infinity in finite pile dominion: Coin Tokens, Villagers, and VP (and maybe more I'm forgetting).  You can probably embed as much information as you want into the Coin Tokens and Villagers.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Jfrisch

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 200
  • Respect: +166
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #14 on: October 25, 2018, 01:03:04 pm »
0

I'm aware you can embed infinity. Another more complicated way to do so wold be via the kc/throne room/procession stack. That doesn't imply any sort of undecidability though.
Logged

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 22
  • Respect: +37
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #15 on: October 25, 2018, 03:40:03 pm »
0

I'm aware you can embed infinity. Another more complicated way to do so wold be via the kc/throne room/procession stack. That doesn't imply any sort of undecidability though.

You are right, having arbitrarily large piles by itself does not imply undecidability. You need to factor in game strategies, which simulate TM logic. From that point of view, TM completeness is not extremely surprising.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #16 on: October 29, 2018, 04:31:22 am »
0

I've been asking (Math and CS) friends this question for a while now. In particular some variant of question 2.

Being able to embed a turing machine (which is not a totally well defined notion) doesn't seem to (necessarily) have any implication for the undecidability for the game.

Dominion with finite piles is really complicated (i.e. question 2 and variants i.e. winning in 1, getting from 1 state to another presumably these are all the same computability strength). . It seems that the win in turn one question is likely decidable (though proving this seems ferociously hard). But I have no idea about infinite pile dominion.
I've also talked about this question with some friends before; in fact, I suspect that we have some mutual friends. The simplest way of stating my question is: Is the decision problem "is there a way to get at least n points this turn?" decidable for any game state? I do not know the answer for finite piles OR infinite piles. In the case of infinite piles, game states must still have a finite description. My suspicion is that the answers are yes and no, respectively, but it's possible that new card could make the finite piles case undecidable as well. It's also possible that the infinite case is decidable; I do not have a proof
Logged

jonaskoelker

  • Explorer
  • *****
  • Offline Offline
  • Posts: 348
  • Grand Market = cantrip Woodcutter
  • Respect: +397
    • View Profile
Re: Turing Machine from Dominion Cards and Mechanics
« Reply #17 on: July 27, 2019, 07:06:08 pm »
0

In Robert Hearn's thesis (https://erikdemaine.org/theses/bhearn.pdf), he describes a game where the game state itself is finite, yet deciding who wins at optimal play is undecidable. I'd start reading on page 69, "undecidability".

Erik Demaine has taught a course on computational complexity in relation to puzzles and games; I think he covers the particular game in

The basic idea is that you make the players simulate a turing machine but essentially shunt off the unbounded memory into the player's heads.

I don't know if it's useful here, but it sounds potentially relevant.
Logged
Pages: [1]
 

Page created in 0.058 seconds with 21 queries.