Mixing
Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy?
$begingroup$
Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one making the last move.
Lasker's Nim is the classical Nim with the additional rule that instead of reducing one of the heaps, you can split one into two heaps.
Lasker's Nim can be solved by using the Sprague-Grundy theorem, but the solution for Wythoff's game is descerned differently by looking for "cold positions" that allow for a win and follow a certain pattern.
Now, I have come across a combination of these two games: A Nim variation where you can either take any amount from one heap, or take the same amount from two heaps, or split an existing heap into two new heaps. And I am a bit lost on how to find the winning strategy. Does anyone know if this particular variation has its own name? I have found a few variations that combine Nim and Wyrthoff's game, going by the name of "Nimhoff", but none of these seem to include the rule that you can split a heap into two.
https://www.sciencedirect.com/science/article/pii/009731659190070W http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WytBridgeAmendedOct25.pdf http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WythoffWisdomJune62016.pdf
Is there someone who has ideas, or maybe even a solution for that particular Nim-Variation? I am uncertain how to proceed from here.
game-theory combinatorial-game-theory
asked Jan 29 at 15:58
Jane DoeJane Doe
62
$endgroup$
add a comment |
$begingroup$
Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one making the last move.
Lasker's Nim is the classical Nim with the additional rule that instead of reducing one of the heaps, you can split one into two heaps.
Lasker's Nim can be solved by using the Sprague-Grundy theorem, but the solution for Wythoff's game is descerned differently by looking for "cold positions" that allow for a win and follow a certain pattern.
Now, I have come across a combination of these two games: A Nim variation where you can either take any amount from one heap, or take the same amount from two heaps, or split an existing heap into two new heaps. And I am a bit lost on how to find the winning strategy. Does anyone know if this particular variation has its own name? I have found a few variations that combine Nim and Wyrthoff's game, going by the name of "Nimhoff", but none of these seem to include the rule that you can split a heap into two.
https://www.sciencedirect.com/science/article/pii/009731659190070W http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WytBridgeAmendedOct25.pdf http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WythoffWisdomJune62016.pdf
Is there someone who has ideas, or maybe even a solution for that particular Nim-Variation? I am uncertain how to proceed from here.
game-theory combinatorial-game-theory
asked Jan 29 at 15:58
Jane DoeJane Doe
62
$endgroup$
$begingroup$
The analysis you allude to for Wythoff's game is a partial analysis according to Sprague-Grundy. It identifies the winning and losing positions, but does not identify the size of the Nim-heap each losing position corresponds to. It is the same idea. When you combine the rules as opposed to adding separate games you need to redo the analysis from the start.
$endgroup$
– Ross Millikan
Jan 29 at 16:23
$begingroup$
This doesn't have a simple strategy. Can you say where you "came across" the combination you describe? Was this in a course or textbook where you were introduced to Wythoff's Nim? Are you having trouble applying the sort of cold position/Sprague-Grundy 0 or nonzero method to small positions of this game?
$endgroup$
– Mark S.
Jan 30 at 1:37
add a comment |
$begingroup$
Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one making the last move.
Lasker's Nim is the classical Nim with the additional rule that instead of reducing one of the heaps, you can split one into two heaps.
Lasker's Nim can be solved by using the Sprague-Grundy theorem, but the solution for Wythoff's game is descerned differently by looking for "cold positions" that allow for a win and follow a certain pattern.
Now, I have come across a combination of these two games: A Nim variation where you can either take any amount from one heap, or take the same amount from two heaps, or split an existing heap into two new heaps. And I am a bit lost on how to find the winning strategy. Does anyone know if this particular variation has its own name? I have found a few variations that combine Nim and Wyrthoff's game, going by the name of "Nimhoff", but none of these seem to include the rule that you can split a heap into two.
https://www.sciencedirect.com/science/article/pii/009731659190070W http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WytBridgeAmendedOct25.pdf http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WythoffWisdomJune62016.pdf
Is there someone who has ideas, or maybe even a solution for that particular Nim-Variation? I am uncertain how to proceed from here.
game-theory combinatorial-game-theory
asked Jan 29 at 15:58
Jane DoeJane Doe
62
$endgroup$
Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one making the last move.
Lasker's Nim is the classical Nim with the additional rule that instead of reducing one of the heaps, you can split one into two heaps.
Lasker's Nim can be solved by using the Sprague-Grundy theorem, but the solution for Wythoff's game is descerned differently by looking for "cold positions" that allow for a win and follow a certain pattern.
Now, I have come across a combination of these two games: A Nim variation where you can either take any amount from one heap, or take the same amount from two heaps, or split an existing heap into two new heaps. And I am a bit lost on how to find the winning strategy. Does anyone know if this particular variation has its own name? I have found a few variations that combine Nim and Wyrthoff's game, going by the name of "Nimhoff", but none of these seem to include the rule that you can split a heap into two.
https://www.sciencedirect.com/science/article/pii/009731659190070W http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WytBridgeAmendedOct25.pdf http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WythoffWisdomJune62016.pdf
Is there someone who has ideas, or maybe even a solution for that particular Nim-Variation? I am uncertain how to proceed from here.
game-theory combinatorial-game-theory
game-theory combinatorial-game-theory
asked Jan 29 at 15:58
Jane DoeJane Doe
62
asked Jan 29 at 15:58
Jane DoeJane Doe
62
edited Jan 29 at 16:14
Jane Doe
asked Jan 29 at 15:58
Jane DoeJane Doe
62
asked Jan 29 at 15:58
Jane DoeJane Doe
62
asked Jan 29 at 15:58
Jane DoeJane Doe
62
62
$begingroup$
The analysis you allude to for Wythoff's game is a partial analysis according to Sprague-Grundy. It identifies the winning and losing positions, but does not identify the size of the Nim-heap each losing position corresponds to. It is the same idea. When you combine the rules as opposed to adding separate games you need to redo the analysis from the start.
$endgroup$
– Ross Millikan
Jan 29 at 16:23
$begingroup$
This doesn't have a simple strategy. Can you say where you "came across" the combination you describe? Was this in a course or textbook where you were introduced to Wythoff's Nim? Are you having trouble applying the sort of cold position/Sprague-Grundy 0 or nonzero method to small positions of this game?
$endgroup$
– Mark S.
Jan 30 at 1:37
add a comment |
$begingroup$
The analysis you allude to for Wythoff's game is a partial analysis according to Sprague-Grundy. It identifies the winning and losing positions, but does not identify the size of the Nim-heap each losing position corresponds to. It is the same idea. When you combine the rules as opposed to adding separate games you need to redo the analysis from the start.
$endgroup$
– Ross Millikan
Jan 29 at 16:23
$begingroup$
This doesn't have a simple strategy. Can you say where you "came across" the combination you describe? Was this in a course or textbook where you were introduced to Wythoff's Nim? Are you having trouble applying the sort of cold position/Sprague-Grundy 0 or nonzero method to small positions of this game?
$endgroup$
– Mark S.
Jan 30 at 1:37
$begingroup$
The analysis you allude to for Wythoff's game is a partial analysis according to Sprague-Grundy. It identifies the winning and losing positions, but does not identify the size of the Nim-heap each losing position corresponds to. It is the same idea. When you combine the rules as opposed to adding separate games you need to redo the analysis from the start.
$endgroup$
– Ross Millikan
Jan 29 at 16:23
$begingroup$
The analysis you allude to for Wythoff's game is a partial analysis according to Sprague-Grundy. It identifies the winning and losing positions, but does not identify the size of the Nim-heap each losing position corresponds to. It is the same idea. When you combine the rules as opposed to adding separate games you need to redo the analysis from the start.
$endgroup$
– Ross Millikan
Jan 29 at 16:23
$begingroup$
This doesn't have a simple strategy. Can you say where you "came across" the combination you describe? Was this in a course or textbook where you were introduced to Wythoff's Nim? Are you having trouble applying the sort of cold position/Sprague-Grundy 0 or nonzero method to small positions of this game?
$endgroup$
– Mark S.
Jan 30 at 1:37
$begingroup$
This doesn't have a simple strategy. Can you say where you "came across" the combination you describe? Was this in a course or textbook where you were introduced to Wythoff's Nim? Are you having trouble applying the sort of cold position/Sprague-Grundy 0 or nonzero method to small positions of this game?
$endgroup$
– Mark S.
Jan 30 at 1:37
add a comment |
0
active
oldest
votes
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092336%2fcombining-a-nim-variation-and-wyrthoffs-game-how-to-find-a-winning-strategy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092336%2fcombining-a-nim-variation-and-wyrthoffs-game-how-to-find-a-winning-strategy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The analysis you allude to for Wythoff's game is a partial analysis according to Sprague-Grundy. It identifies the winning and losing positions, but does not identify the size of the Nim-heap each losing position corresponds to. It is the same idea. When you combine the rules as opposed to adding separate games you need to redo the analysis from the start.
$endgroup$
– Ross Millikan
Jan 29 at 16:23
$begingroup$
This doesn't have a simple strategy. Can you say where you "came across" the combination you describe? Was this in a course or textbook where you were introduced to Wythoff's Nim? Are you having trouble applying the sort of cold position/Sprague-Grundy 0 or nonzero method to small positions of this game?
$endgroup$
– Mark S.
Jan 30 at 1:37