A neat little multiplayer nim problem
Mar. 25th, 2021 12:49 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyThis problem is pretty easy, but I was thinking about it recently and I wanted to state it if other people want to try it. It's this:
Imagine an m-player variant of nim, with m-1 rounds. Each round i (numbered from m down to 2; these are the number of players playing in that round) has an associate pile of ni objects. The game starts witht the m-player round; one player is designated as going first, and then players take turns in a specified rotation removing either 1 or 2 objects from the pile. If it's your turn and there's nothing to remove, you're eliminated, and the game moves on to the m-1 player round, with the player after you going first in that round (and the rotation continuing but skipping over you). This repeats until only one player is left. That player gets 1st place; the player eliminated in the 2-player round gets 2nd place; and so on. You are trying to place as well as possible. The problem then is to figure out a fairly-explicit description of how to determine the optimal strategy (and what the results will be if everyone plays optimally) from any give position.
(If you want to turn the problem into something which has one definite answer, how about this: Given i, determine the smallest modulus Mi such that ni only matters up to modulo Mi when determining the optimal strategy and final result.)
Why was I thinking about this problem? Well, uh, I was watching some people play Mario Party on the internet, and it's a minigame in that. :P Well, sort of -- the actual Mario Party version differs in a few ways, some of which make the solution to the problem as stated above largely useless!
Specifically:
1. You can't actually see the size of each round; you can only see the next 13 objects (where the delimiter between rounds counts as an object). So if you're in the 4-player round, you might just see, say, that there are 6 objects left in the 4-player round, then the delimiter, and then there are at least 6 objects in the 3-player round, but who knows how many after that.
2. What place you come in doesn't really matter, only whether you achieve 1st or not (1st place is worth 10 coins, the other places are worth 0). This I had to change because the problem is ill-defined otherwise; you end up with kingmaker situations where there's no defined optimal strategy.
3. OK, also, since it's just a minigame in a broader game, you might also have preferences for who wins other than just that you most prefer yourself to win, but I didn't want to think about that.
4. ...also some of the objects are themselves coins and taking them gets you a coin whether you win or not. Yeah obviously trying to include that is just ridiculous.
Still, I thought it was kind of neat so I thought I'd state it here.
Imagine an m-player variant of nim, with m-1 rounds. Each round i (numbered from m down to 2; these are the number of players playing in that round) has an associate pile of ni objects. The game starts witht the m-player round; one player is designated as going first, and then players take turns in a specified rotation removing either 1 or 2 objects from the pile. If it's your turn and there's nothing to remove, you're eliminated, and the game moves on to the m-1 player round, with the player after you going first in that round (and the rotation continuing but skipping over you). This repeats until only one player is left. That player gets 1st place; the player eliminated in the 2-player round gets 2nd place; and so on. You are trying to place as well as possible. The problem then is to figure out a fairly-explicit description of how to determine the optimal strategy (and what the results will be if everyone plays optimally) from any give position.
(If you want to turn the problem into something which has one definite answer, how about this: Given i, determine the smallest modulus Mi such that ni only matters up to modulo Mi when determining the optimal strategy and final result.)
Why was I thinking about this problem? Well, uh, I was watching some people play Mario Party on the internet, and it's a minigame in that. :P Well, sort of -- the actual Mario Party version differs in a few ways, some of which make the solution to the problem as stated above largely useless!
Specifically:
1. You can't actually see the size of each round; you can only see the next 13 objects (where the delimiter between rounds counts as an object). So if you're in the 4-player round, you might just see, say, that there are 6 objects left in the 4-player round, then the delimiter, and then there are at least 6 objects in the 3-player round, but who knows how many after that.
2. What place you come in doesn't really matter, only whether you achieve 1st or not (1st place is worth 10 coins, the other places are worth 0). This I had to change because the problem is ill-defined otherwise; you end up with kingmaker situations where there's no defined optimal strategy.
3. OK, also, since it's just a minigame in a broader game, you might also have preferences for who wins other than just that you most prefer yourself to win, but I didn't want to think about that.
4. ...also some of the objects are themselves coins and taking them gets you a coin whether you win or not. Yeah obviously trying to include that is just ridiculous.
Still, I thought it was kind of neat so I thought I'd state it here.
