Dominion > Puzzles and Challenges

Turing Machine from Dominion Cards and Mechanics

(1/4) > >>

Commodore Chuckles:
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.

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

ConMan:

--- Quote from: silvern on August 17, 2018, 05:42:56 pm ---This sounds really cool, but I need someone to help explain turing machines to me for the third time  ;)

--- End quote ---
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.
* ...

ghostofmars:
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.

paulfc:
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.

Navigation

[0] Message Index

[#] Next page