Using Mathematics to find a Checkmate
$begingroup$
Question: Is it possible to discover a sequence of steps to checkmate using a king, bishop, and knight, while the enemy only has a king, on an 8x8 chessboard? Without loss of generality, assume that the king, bishop, and knight are white while the lone king is black.
I've tried to use graph theory to solve the problem, where I see all vertices that the white pieces fall on and which placements would allow the black king's graph to be a subset of the white pieces' graph.
I've also tried to create a bijection, where I let the possible moves of the pieces be functions while the graphs of the pieces are the ranges of the functions and the possible initial starting positions are the domains of the functions. While this seems to be a useful way to look at the problem, I'm not sure how to produce such functions. Perhaps looking at this in terms of functional equations could be helpful.
It would be preferable if the solution relied on mathematical concepts and proofs rather than just on logic or chess techniques since this problem is supposed to be solved using graph theory. However, any other methods apart from graph theory are also welcome!
graph-theory
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
$endgroup$
add a comment |
$begingroup$
Question: Is it possible to discover a sequence of steps to checkmate using a king, bishop, and knight, while the enemy only has a king, on an 8x8 chessboard? Without loss of generality, assume that the king, bishop, and knight are white while the lone king is black.
I've tried to use graph theory to solve the problem, where I see all vertices that the white pieces fall on and which placements would allow the black king's graph to be a subset of the white pieces' graph.
I've also tried to create a bijection, where I let the possible moves of the pieces be functions while the graphs of the pieces are the ranges of the functions and the possible initial starting positions are the domains of the functions. While this seems to be a useful way to look at the problem, I'm not sure how to produce such functions. Perhaps looking at this in terms of functional equations could be helpful.
It would be preferable if the solution relied on mathematical concepts and proofs rather than just on logic or chess techniques since this problem is supposed to be solved using graph theory. However, any other methods apart from graph theory are also welcome!
graph-theory
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
$endgroup$
add a comment |
$begingroup$
Question: Is it possible to discover a sequence of steps to checkmate using a king, bishop, and knight, while the enemy only has a king, on an 8x8 chessboard? Without loss of generality, assume that the king, bishop, and knight are white while the lone king is black.
I've tried to use graph theory to solve the problem, where I see all vertices that the white pieces fall on and which placements would allow the black king's graph to be a subset of the white pieces' graph.
I've also tried to create a bijection, where I let the possible moves of the pieces be functions while the graphs of the pieces are the ranges of the functions and the possible initial starting positions are the domains of the functions. While this seems to be a useful way to look at the problem, I'm not sure how to produce such functions. Perhaps looking at this in terms of functional equations could be helpful.
It would be preferable if the solution relied on mathematical concepts and proofs rather than just on logic or chess techniques since this problem is supposed to be solved using graph theory. However, any other methods apart from graph theory are also welcome!
graph-theory
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
$endgroup$
Question: Is it possible to discover a sequence of steps to checkmate using a king, bishop, and knight, while the enemy only has a king, on an 8x8 chessboard? Without loss of generality, assume that the king, bishop, and knight are white while the lone king is black.
I've tried to use graph theory to solve the problem, where I see all vertices that the white pieces fall on and which placements would allow the black king's graph to be a subset of the white pieces' graph.
I've also tried to create a bijection, where I let the possible moves of the pieces be functions while the graphs of the pieces are the ranges of the functions and the possible initial starting positions are the domains of the functions. While this seems to be a useful way to look at the problem, I'm not sure how to produce such functions. Perhaps looking at this in terms of functional equations could be helpful.
It would be preferable if the solution relied on mathematical concepts and proofs rather than just on logic or chess techniques since this problem is supposed to be solved using graph theory. However, any other methods apart from graph theory are also welcome!
graph-theory
graph-theory
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
asked Jan 7 at 9:03
Matthew TanMatthew Tan
755
755
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You could create a state graph $G$ where each vertex $v$ represents a configuration of a black king, knight, bishop and a white king (by configuration I mean positions for each of them).
Then, add an edge $(u,v)$ between two vertices if it is possible to go from one cconfiguration to another in a single move.
A path from the initial configuration to any checkmate configuration is a sequence of steps to checkmate.
The graph is probably very very big though.
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
$endgroup$
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
add a comment |
$begingroup$
Yes. Make a big vector space. Each position on chessboard gets its own element in this vector and let's add a virtual spot for captured pieces too.
Now let each piece occupy it's position and encode it by some means into a number on the field of this vector space (so we know which piece it is and whose player it belongs to). All allowed moves by one player will now be a very special small set of permutation matrices working on this vector.
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
$endgroup$
add a comment |
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',
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%2f3064790%2fusing-mathematics-to-find-a-checkmate%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You could create a state graph $G$ where each vertex $v$ represents a configuration of a black king, knight, bishop and a white king (by configuration I mean positions for each of them).
Then, add an edge $(u,v)$ between two vertices if it is possible to go from one cconfiguration to another in a single move.
A path from the initial configuration to any checkmate configuration is a sequence of steps to checkmate.
The graph is probably very very big though.
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
$endgroup$
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
add a comment |
$begingroup$
You could create a state graph $G$ where each vertex $v$ represents a configuration of a black king, knight, bishop and a white king (by configuration I mean positions for each of them).
Then, add an edge $(u,v)$ between two vertices if it is possible to go from one cconfiguration to another in a single move.
A path from the initial configuration to any checkmate configuration is a sequence of steps to checkmate.
The graph is probably very very big though.
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
$endgroup$
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
add a comment |
$begingroup$
You could create a state graph $G$ where each vertex $v$ represents a configuration of a black king, knight, bishop and a white king (by configuration I mean positions for each of them).
Then, add an edge $(u,v)$ between two vertices if it is possible to go from one cconfiguration to another in a single move.
A path from the initial configuration to any checkmate configuration is a sequence of steps to checkmate.
The graph is probably very very big though.
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
$endgroup$
You could create a state graph $G$ where each vertex $v$ represents a configuration of a black king, knight, bishop and a white king (by configuration I mean positions for each of them).
Then, add an edge $(u,v)$ between two vertices if it is possible to go from one cconfiguration to another in a single move.
A path from the initial configuration to any checkmate configuration is a sequence of steps to checkmate.
The graph is probably very very big though.
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
edited Jan 7 at 9:34
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
answered Jan 7 at 9:18
KuifjeKuifje
7,2722726
7,2722726
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
add a comment |
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
You are describing what's called a tablebase. The number of nodes for KBN vs K is not "very very big", only a few million nodes.
$endgroup$
– bof
Jan 7 at 10:09
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
$begingroup$
@bof: Thank you for the reference. Fascinating
$endgroup$
– Kuifje
Jan 7 at 10:17
add a comment |
$begingroup$
Yes. Make a big vector space. Each position on chessboard gets its own element in this vector and let's add a virtual spot for captured pieces too.
Now let each piece occupy it's position and encode it by some means into a number on the field of this vector space (so we know which piece it is and whose player it belongs to). All allowed moves by one player will now be a very special small set of permutation matrices working on this vector.
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
$endgroup$
add a comment |
$begingroup$
Yes. Make a big vector space. Each position on chessboard gets its own element in this vector and let's add a virtual spot for captured pieces too.
Now let each piece occupy it's position and encode it by some means into a number on the field of this vector space (so we know which piece it is and whose player it belongs to). All allowed moves by one player will now be a very special small set of permutation matrices working on this vector.
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
$endgroup$
add a comment |
$begingroup$
Yes. Make a big vector space. Each position on chessboard gets its own element in this vector and let's add a virtual spot for captured pieces too.
Now let each piece occupy it's position and encode it by some means into a number on the field of this vector space (so we know which piece it is and whose player it belongs to). All allowed moves by one player will now be a very special small set of permutation matrices working on this vector.
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
$endgroup$
Yes. Make a big vector space. Each position on chessboard gets its own element in this vector and let's add a virtual spot for captured pieces too.
Now let each piece occupy it's position and encode it by some means into a number on the field of this vector space (so we know which piece it is and whose player it belongs to). All allowed moves by one player will now be a very special small set of permutation matrices working on this vector.
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
answered Jan 7 at 10:25
mathreadlermathreadler
15.2k72263
15.2k72263
add a comment |
add a comment |
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%2f3064790%2fusing-mathematics-to-find-a-checkmate%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
