Cyclic Partisan Nim Variant

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite
2












This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this player wins with score equal to the number of remaining objects. Other players lose with score equal to minus the number of objects they still own. Play consists of players cyclically taking turns, where (for the 2-player version) they choose to either:



  • Move the position marker forward to any non-empty heap they own, and remove exactly one object from that heap.

  • Reset the position marker back to the beginning, before any heaps. (Only valid if the previous player did not reset - this ensures the game is finite.)

What is the optimal strategy for each player in the 2-player version, given an arbitrary initial state?



A state can be specified by:



  • A sequence of (size, owner) integer pairs representing the heaps

  • A non-negative integer representing the position marker (with the sequence indexed starting from one)

  • An integer representing the player about to move

  • A Boolean representing whether the previous player chose to reset

So far I have noticed the maximal score seems to eventually follow an arithmetic progression under consistent patterns of adding to the heaps. However, there is a certain region of states with more unstable behaviour. The main problem is the position marker, since without it the game would become trivial.



Update: I have generated the maximum scores for player $0$ with the initial state



$$
left( beginarrayc
!!!& 3 & & x & & 5 & & y & !\
!!!& & 6 & & 9 & & 2 & & 4 !
endarray right)_textP0, top
$$



as $x$ and $y$ range from $1$ to $11$.
contour plot of maximum scores
Solid contours represent positive score and dashed contours represent negative score. Interestingly, it can be seen that the behaviour changes only near when two heaps have the same size.



Further, I am fairly confident this maximum score formula



$$
left( beginarrayc
!!!& h_1 & & h_3 !\
!!!& & h_2 & !
endarray right)_textP0, top
,to,
left{ beginarraylrrcr
h_2 - h_1 & textif & h_2 - h_1 < 0 & textand & h_3 - h_2 + 1 ge 0 \
h_2 - h_1 + 1 & textif & h_3 - h_1 + 1 ge 0 & textand & h_2 - h_1 ge 0 \
h_3 - h_1 + 1 & textif & h_3 - h_1 + 1 < 0 & textand & h_3 - h_2 + 1 < 0
endarray right.
$$



works for all values of $h_i > 0$, and also including when $h_3 = 0$ or $h_2 = h_3 = 0$. In general I think the function would have to be piecewise linear with coefficients in $ -1, 0, +1 $ and satisfy a heap merge invariance property, meaning for example that $M(h_1, 0, h_3) = M(h_1 + h_3, 0, 0) = M(0, 0, h_1 + h_3)$.




combinatorics discrete-mathematics algorithms puzzle combinatorial-game-theory




share|cite|improve this question





















  • what is the meaning of "optimal strategy" when there are more than two players ?
    – mercio
    Aug 3 at 10:52










  • @mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores.
    – D. G.
    Aug 3 at 11:11










  • By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker?
    – Jaap Scherphuis
    Aug 3 at 13:24










  • @JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and...
    – D. G.
    Aug 3 at 15:22










  • @JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient.
    – D. G.
    Aug 3 at 15:45














up vote
1
down vote

favorite
2












This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this player wins with score equal to the number of remaining objects. Other players lose with score equal to minus the number of objects they still own. Play consists of players cyclically taking turns, where (for the 2-player version) they choose to either:



  • Move the position marker forward to any non-empty heap they own, and remove exactly one object from that heap.

  • Reset the position marker back to the beginning, before any heaps. (Only valid if the previous player did not reset - this ensures the game is finite.)

What is the optimal strategy for each player in the 2-player version, given an arbitrary initial state?



A state can be specified by:



  • A sequence of (size, owner) integer pairs representing the heaps

  • A non-negative integer representing the position marker (with the sequence indexed starting from one)

  • An integer representing the player about to move

  • A Boolean representing whether the previous player chose to reset

So far I have noticed the maximal score seems to eventually follow an arithmetic progression under consistent patterns of adding to the heaps. However, there is a certain region of states with more unstable behaviour. The main problem is the position marker, since without it the game would become trivial.



Update: I have generated the maximum scores for player $0$ with the initial state



$$
left( beginarrayc
!!!& 3 & & x & & 5 & & y & !\
!!!& & 6 & & 9 & & 2 & & 4 !
endarray right)_textP0, top
$$



as $x$ and $y$ range from $1$ to $11$.
contour plot of maximum scores
Solid contours represent positive score and dashed contours represent negative score. Interestingly, it can be seen that the behaviour changes only near when two heaps have the same size.



Further, I am fairly confident this maximum score formula



$$
left( beginarrayc
!!!& h_1 & & h_3 !\
!!!& & h_2 & !
endarray right)_textP0, top
,to,
left{ beginarraylrrcr
h_2 - h_1 & textif & h_2 - h_1 < 0 & textand & h_3 - h_2 + 1 ge 0 \
h_2 - h_1 + 1 & textif & h_3 - h_1 + 1 ge 0 & textand & h_2 - h_1 ge 0 \
h_3 - h_1 + 1 & textif & h_3 - h_1 + 1 < 0 & textand & h_3 - h_2 + 1 < 0
endarray right.
$$



works for all values of $h_i > 0$, and also including when $h_3 = 0$ or $h_2 = h_3 = 0$. In general I think the function would have to be piecewise linear with coefficients in $ -1, 0, +1 $ and satisfy a heap merge invariance property, meaning for example that $M(h_1, 0, h_3) = M(h_1 + h_3, 0, 0) = M(0, 0, h_1 + h_3)$.




combinatorics discrete-mathematics algorithms puzzle combinatorial-game-theory




share|cite|improve this question





















  • what is the meaning of "optimal strategy" when there are more than two players ?
    – mercio
    Aug 3 at 10:52










  • @mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores.
    – D. G.
    Aug 3 at 11:11










  • By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker?
    – Jaap Scherphuis
    Aug 3 at 13:24










  • @JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and...
    – D. G.
    Aug 3 at 15:22










  • @JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient.
    – D. G.
    Aug 3 at 15:45












up vote
1
down vote

favorite
2









up vote
1
down vote

favorite
2






2





This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this player wins with score equal to the number of remaining objects. Other players lose with score equal to minus the number of objects they still own. Play consists of players cyclically taking turns, where (for the 2-player version) they choose to either:



  • Move the position marker forward to any non-empty heap they own, and remove exactly one object from that heap.

  • Reset the position marker back to the beginning, before any heaps. (Only valid if the previous player did not reset - this ensures the game is finite.)

What is the optimal strategy for each player in the 2-player version, given an arbitrary initial state?



A state can be specified by:



  • A sequence of (size, owner) integer pairs representing the heaps

  • A non-negative integer representing the position marker (with the sequence indexed starting from one)

  • An integer representing the player about to move

  • A Boolean representing whether the previous player chose to reset

So far I have noticed the maximal score seems to eventually follow an arithmetic progression under consistent patterns of adding to the heaps. However, there is a certain region of states with more unstable behaviour. The main problem is the position marker, since without it the game would become trivial.



Update: I have generated the maximum scores for player $0$ with the initial state



$$
left( beginarrayc
!!!& 3 & & x & & 5 & & y & !\
!!!& & 6 & & 9 & & 2 & & 4 !
endarray right)_textP0, top
$$



as $x$ and $y$ range from $1$ to $11$.
contour plot of maximum scores
Solid contours represent positive score and dashed contours represent negative score. Interestingly, it can be seen that the behaviour changes only near when two heaps have the same size.



Further, I am fairly confident this maximum score formula



$$
left( beginarrayc
!!!& h_1 & & h_3 !\
!!!& & h_2 & !
endarray right)_textP0, top
,to,
left{ beginarraylrrcr
h_2 - h_1 & textif & h_2 - h_1 < 0 & textand & h_3 - h_2 + 1 ge 0 \
h_2 - h_1 + 1 & textif & h_3 - h_1 + 1 ge 0 & textand & h_2 - h_1 ge 0 \
h_3 - h_1 + 1 & textif & h_3 - h_1 + 1 < 0 & textand & h_3 - h_2 + 1 < 0
endarray right.
$$



works for all values of $h_i > 0$, and also including when $h_3 = 0$ or $h_2 = h_3 = 0$. In general I think the function would have to be piecewise linear with coefficients in $ -1, 0, +1 $ and satisfy a heap merge invariance property, meaning for example that $M(h_1, 0, h_3) = M(h_1 + h_3, 0, 0) = M(0, 0, h_1 + h_3)$.




combinatorics discrete-mathematics algorithms puzzle combinatorial-game-theory




share|cite|improve this question













This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this player wins with score equal to the number of remaining objects. Other players lose with score equal to minus the number of objects they still own. Play consists of players cyclically taking turns, where (for the 2-player version) they choose to either:



  • Move the position marker forward to any non-empty heap they own, and remove exactly one object from that heap.

  • Reset the position marker back to the beginning, before any heaps. (Only valid if the previous player did not reset - this ensures the game is finite.)

What is the optimal strategy for each player in the 2-player version, given an arbitrary initial state?



A state can be specified by:



  • A sequence of (size, owner) integer pairs representing the heaps

  • A non-negative integer representing the position marker (with the sequence indexed starting from one)

  • An integer representing the player about to move

  • A Boolean representing whether the previous player chose to reset

So far I have noticed the maximal score seems to eventually follow an arithmetic progression under consistent patterns of adding to the heaps. However, there is a certain region of states with more unstable behaviour. The main problem is the position marker, since without it the game would become trivial.



Update: I have generated the maximum scores for player $0$ with the initial state



$$
left( beginarrayc
!!!& 3 & & x & & 5 & & y & !\
!!!& & 6 & & 9 & & 2 & & 4 !
endarray right)_textP0, top
$$



as $x$ and $y$ range from $1$ to $11$.
contour plot of maximum scores
Solid contours represent positive score and dashed contours represent negative score. Interestingly, it can be seen that the behaviour changes only near when two heaps have the same size.



Further, I am fairly confident this maximum score formula



$$
left( beginarrayc
!!!& h_1 & & h_3 !\
!!!& & h_2 & !
endarray right)_textP0, top
,to,
left{ beginarraylrrcr
h_2 - h_1 & textif & h_2 - h_1 < 0 & textand & h_3 - h_2 + 1 ge 0 \
h_2 - h_1 + 1 & textif & h_3 - h_1 + 1 ge 0 & textand & h_2 - h_1 ge 0 \
h_3 - h_1 + 1 & textif & h_3 - h_1 + 1 < 0 & textand & h_3 - h_2 + 1 < 0
endarray right.
$$



works for all values of $h_i > 0$, and also including when $h_3 = 0$ or $h_2 = h_3 = 0$. In general I think the function would have to be piecewise linear with coefficients in $ -1, 0, +1 $ and satisfy a heap merge invariance property, meaning for example that $M(h_1, 0, h_3) = M(h_1 + h_3, 0, 0) = M(0, 0, h_1 + h_3)$.





combinatorics discrete-mathematics algorithms puzzle combinatorial-game-theory





share|cite|improve this question












share|cite|improve this question




share|cite|improve this question








edited yesterday
























asked Aug 3 at 9:28









D. G.

484




484











  • what is the meaning of "optimal strategy" when there are more than two players ?
    – mercio
    Aug 3 at 10:52










  • @mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores.
    – D. G.
    Aug 3 at 11:11










  • By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker?
    – Jaap Scherphuis
    Aug 3 at 13:24










  • @JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and...
    – D. G.
    Aug 3 at 15:22










  • @JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient.
    – D. G.
    Aug 3 at 15:45
















  • what is the meaning of "optimal strategy" when there are more than two players ?
    – mercio
    Aug 3 at 10:52










  • @mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores.
    – D. G.
    Aug 3 at 11:11










  • By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker?
    – Jaap Scherphuis
    Aug 3 at 13:24










  • @JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and...
    – D. G.
    Aug 3 at 15:22










  • @JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient.
    – D. G.
    Aug 3 at 15:45















what is the meaning of "optimal strategy" when there are more than two players ?
– mercio
Aug 3 at 10:52




what is the meaning of "optimal strategy" when there are more than two players ?
– mercio
Aug 3 at 10:52












@mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores.
– D. G.
Aug 3 at 11:11




@mercio Sorry, I meant optimal strategy for two players. What are the options for more than two players? For a given player, it could be to maximise their score if a win is guaranteed, otherwise minimise the variance among the players' scores.
– D. G.
Aug 3 at 11:11












By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker?
– Jaap Scherphuis
Aug 3 at 13:24




By the way, the final Boolean in your state seems a bit redundant, since during play the position marker is before any heaps iff the previous player reset it. Or do you want to allow your arbitrary starting position to be inconsistent in this respect, so that a starting position may or may not allow a reset move regardless of the starting location of the marker?
– Jaap Scherphuis
Aug 3 at 13:24












@JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and...
– D. G.
Aug 3 at 15:22




@JaapScherphuis Yes it annoys me, but here is why I have left it there: 1) the special case exists either way, so may as well make it explicit; 2) it is only a Boolean in the 2-player case, in the n-player generalisation it can take on n values; and...
– D. G.
Aug 3 at 15:22












@JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient.
– D. G.
Aug 3 at 15:45




@JaapScherphuis 3) Whenever there is an empty heap, I delete it and merge the adjacent heaps to reduce complexity if possible (for 2 players this makes the heap ownership alternate). Thus if the first player deletes the first heap, then the second player will not know if they can reset the position marker, unless they have the Boolean. Then there are three options: leave empty heaps and no Boolean, remove empty heaps and add Boolean, or remove empty heaps and add a phantom empty heap at the beginning. The middle option seems to be the most convenient.
– D. G.
Aug 3 at 15:45















active

oldest

votes











Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);








 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870904%2fcyclic-partisan-nim-variant%23new-answer', 'question_page');

);

Post as a guest






















active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes










 

draft saved


draft discarded


























 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870904%2fcyclic-partisan-nim-variant%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

What is the equation of a 3D cone with generalised tilt?

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite What is the equation of a 3D cone with generalized tilt? I've noticed that in most equations given to represent a cone, there is no parameter which defines the tilt of the cone in 3D space and that most of them have their point at the origin $(0,0,0)$ - I was wondering if anyone could give me a more generalized cone equation for a cone in any position in 3D space 3d share | cite | improve this question edited Jul 25 '16 at 0:05 ervx 9,425 3 13 36 asked Jul 24 '16 at 15:38 Charlene 11 2 2 Welcome to Math.SE! Could you please explain a few things to help people give an answer useful to you: 1. What do you mean by "generalized tilt"? 2. Are you asking about a right circular cone? Does the angle at the vertex matter? 3. What form of answer (implicit, parametric...?) are you looking for? 4. If this is homework, what tools do you have available, an...
Read more

Color the edges and diagonals of a regular polygon

Image
Clash Royale CLAN TAG #URR8PPP up vote 5 down vote favorite 1 Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $dfracbinomn23$ colors, such that you use every color exactly three times and for every color the three segments (edges or diagonals) with that color form a triangle? Trivially $nequiv 0 text or 1 pmod3$. I can also prove that if the statement is true for $k$ than it is true for $3k$ as well. How to finish? Please help! Thanks combinatorial-geometry share | cite | improve this question edited Aug 6 at 21:57 alcana 118 4 asked Aug 6 at 21:15 Leo Gardner 356 11 Even assuming "polyhpn" in the title is a typo for polygon , it is unclear what you mean by "the edges and sides". Aren't the side of a regular polygon the same as the edges? A regular $n$-sided polygon has $n$ edges. – hardmath Aug 6 at 21:20 3 $n$ ne...
Read more

Relationship between determinant of matrix and determinant of adjoint?

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite We are studying adjoints in class, and I was curious if there is a relationship between the determinant of matrix A, and the determinant of the adjoint of matrix A? I assume there would be a relationship because finding the adjoint requires creating a cofactor matrix and then transposing it. linear-algebra determinant adjoint-operators share | cite | improve this question asked Nov 17 '17 at 17:32 CluelessCoder 32 5 For a square matrix $A$ of order $n$, we have $A(operatornameadj A)=(operatornameadj A)A=|A|I_n$ where $I_n$ is the identity matrix of order $n$. This should tell you about the determinant of the adjoint in terms of that of $A$ (use multiplicative property and other elementary properties of determinants). – Prasun Biswas Nov 17 '17 at 17:35 1 @CluelessCoder: see here: math.stackexchange.com/questions/516127/…...
Read more