21–30 of 194 posts
Does it actually make sense to say that something that is non-computable is most complex? That seems like a contradiction.
"In this work, we solve this problem by reformulating the construction to exclusively use cards with mandatory effects."
So it's more a of a subset of MTG's rules. Still, there are commercial video games out beyond MTG and they've been out for some time. Why has the game theory field not kept up with them?
It should be retitled as 'MTG is the most complex game we've played'. I would counter that other card driven games like Android Netrunner, Terraforming Mars, Lisboa, Hanabi, etc are just as or even more complex.
MTG has ways to return to a previously seen play state, technically allowing a game to continue infinitely, depending on your deck, of course.
Eh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".
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…
> "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable."
It's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the result of some arbitrarily complex computation.
Imagine we play a "game" where I win if there's a nontrivial zero of the Riemann zeta function with real part not equal to one half, otherwise you win. Neither of us has any decisions to make in this game. It's still very difficult to determine who's going to win.
- 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.
Eh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".
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.