41–50 of 194 posts
I'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.
I'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.
https://i.redd.it/wyn3d22evs011.jpg
This is not the worst I've seen, simply what I was able to turn-up on short notice.
EDIT: To clarify (the UI isn't great), what you see above is a selection of the "cards" (creatures/tokens) in play, more are off screen.
"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. " What is this input? Board size?
In reality, the number of possible moves is not constant and depends on the current position.
Does it actually make sense to say that something that is non-computable is most complex? That seems like a contradiction.
I think you are misunderstanding the article. The point is that when the game is considered as a computation, the problem of figuring out who is going to win is not computable. Like every discussion of the halting problem, this is about whether or not a program exists that can calculate how some other specific program will behave.
I'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.
Why are you making “strong” claims in a field you admittedly are not an expert in? This is not how polite nor useful conversations happen.
MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large. EDIT: This from the real abstract sounds very strange: "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows…
No, you can recycle resources and there are cards that remove termination conditions of the game. For example Platinum Angel or Lich's Mastery.
I'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic
While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account.
From an AI perspective Magic is also very hard because it is:
* Non-deterministic
* Partially observable
* AntagonisticSo it seems perfectly possible (and in fact highly likely) that this result does not hold if players play optimally, especially if deck selection is included in the strategy.