sorting move before alpha beta pruning - tic tac toe - python
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I have the negascout or principal variation search algorithms working fine to solve tic tac toe. I have read somewhere that for these algorithms to be most efficient it is important to sort the moves such that the search starts with what is likely going to be the best move.
Assume the heuristic that in tic tac toe, the center square is better than a corner square, which is better than a side square.
I represent a square in tic tac toe by an integer between 1 and 9, as ordered on a numerical keypad. In Python3, I am currently doing:
def sort_candidate_move(candidate_move):
# center > corner > side
move_dict = {1: 'b', 2: 'c', 3: 'b', 4: 'c', 5: 'a', 6: 'c', 7: 'b', 8: 'c', 9: 'b'}
to_sort = [(move_dict[move], move) for move in candidate_move]
to_sort.sort()
return [tup[1] for tup in to_sort]
where candidate_move is the list of candidate moves, for example:
candidate_move = [2, 5, 9]
The code returns:
[5, 9, 2]
It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe.
Is there a more efficient way (in terms of computation speed) to code the function sort_candidate_move()?
python sorting tic-tac-toe alpha-beta-pruning
asked Nov 16 '18 at 15:14
JSBJSB
12
add a comment |
I have the negascout or principal variation search algorithms working fine to solve tic tac toe. I have read somewhere that for these algorithms to be most efficient it is important to sort the moves such that the search starts with what is likely going to be the best move.
Assume the heuristic that in tic tac toe, the center square is better than a corner square, which is better than a side square.
I represent a square in tic tac toe by an integer between 1 and 9, as ordered on a numerical keypad. In Python3, I am currently doing:
def sort_candidate_move(candidate_move):
# center > corner > side
move_dict = {1: 'b', 2: 'c', 3: 'b', 4: 'c', 5: 'a', 6: 'c', 7: 'b', 8: 'c', 9: 'b'}
to_sort = [(move_dict[move], move) for move in candidate_move]
to_sort.sort()
return [tup[1] for tup in to_sort]
where candidate_move is the list of candidate moves, for example:
candidate_move = [2, 5, 9]
The code returns:
[5, 9, 2]
It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe.
Is there a more efficient way (in terms of computation speed) to code the function sort_candidate_move()?
python sorting tic-tac-toe alpha-beta-pruning
asked Nov 16 '18 at 15:14
JSBJSB
12
add a comment |
I have the negascout or principal variation search algorithms working fine to solve tic tac toe. I have read somewhere that for these algorithms to be most efficient it is important to sort the moves such that the search starts with what is likely going to be the best move.
Assume the heuristic that in tic tac toe, the center square is better than a corner square, which is better than a side square.
I represent a square in tic tac toe by an integer between 1 and 9, as ordered on a numerical keypad. In Python3, I am currently doing:
def sort_candidate_move(candidate_move):
# center > corner > side
move_dict = {1: 'b', 2: 'c', 3: 'b', 4: 'c', 5: 'a', 6: 'c', 7: 'b', 8: 'c', 9: 'b'}
to_sort = [(move_dict[move], move) for move in candidate_move]
to_sort.sort()
return [tup[1] for tup in to_sort]
where candidate_move is the list of candidate moves, for example:
candidate_move = [2, 5, 9]
The code returns:
[5, 9, 2]
It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe.
Is there a more efficient way (in terms of computation speed) to code the function sort_candidate_move()?
python sorting tic-tac-toe alpha-beta-pruning
asked Nov 16 '18 at 15:14
JSBJSB
12
I have the negascout or principal variation search algorithms working fine to solve tic tac toe. I have read somewhere that for these algorithms to be most efficient it is important to sort the moves such that the search starts with what is likely going to be the best move.
Assume the heuristic that in tic tac toe, the center square is better than a corner square, which is better than a side square.
I represent a square in tic tac toe by an integer between 1 and 9, as ordered on a numerical keypad. In Python3, I am currently doing:
def sort_candidate_move(candidate_move):
# center > corner > side
move_dict = {1: 'b', 2: 'c', 3: 'b', 4: 'c', 5: 'a', 6: 'c', 7: 'b', 8: 'c', 9: 'b'}
to_sort = [(move_dict[move], move) for move in candidate_move]
to_sort.sort()
return [tup[1] for tup in to_sort]
where candidate_move is the list of candidate moves, for example:
candidate_move = [2, 5, 9]
The code returns:
[5, 9, 2]
It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe.
Is there a more efficient way (in terms of computation speed) to code the function sort_candidate_move()?
python sorting tic-tac-toe alpha-beta-pruning
python sorting tic-tac-toe alpha-beta-pruning
asked Nov 16 '18 at 15:14
JSBJSB
12
asked Nov 16 '18 at 15:14
JSBJSB
12
edited Nov 22 '18 at 0:06
JSB
asked Nov 16 '18 at 15:14
JSBJSB
12
asked Nov 16 '18 at 15:14
JSBJSB
12
asked Nov 16 '18 at 15:14
JSBJSB
12
12
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Tic-tac-toe game is at most 9 steps, giving less than 9! different games. For a problem of this scale all sensible algorithms will be superfast, so comparing their times will not show much difference. The algorithms' time-complexity estimates ("big O") are asymptotic, which means they are apparent only for problem of large to very-large size.
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53340581%2fsorting-move-before-alpha-beta-pruning-tic-tac-toe-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Tic-tac-toe game is at most 9 steps, giving less than 9! different games. For a problem of this scale all sensible algorithms will be superfast, so comparing their times will not show much difference. The algorithms' time-complexity estimates ("big O") are asymptotic, which means they are apparent only for problem of large to very-large size.
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
add a comment |
Tic-tac-toe game is at most 9 steps, giving less than 9! different games. For a problem of this scale all sensible algorithms will be superfast, so comparing their times will not show much difference. The algorithms' time-complexity estimates ("big O") are asymptotic, which means they are apparent only for problem of large to very-large size.
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
add a comment |
Tic-tac-toe game is at most 9 steps, giving less than 9! different games. For a problem of this scale all sensible algorithms will be superfast, so comparing their times will not show much difference. The algorithms' time-complexity estimates ("big O") are asymptotic, which means they are apparent only for problem of large to very-large size.
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
Tic-tac-toe game is at most 9 steps, giving less than 9! different games. For a problem of this scale all sensible algorithms will be superfast, so comparing their times will not show much difference. The algorithms' time-complexity estimates ("big O") are asymptotic, which means they are apparent only for problem of large to very-large size.
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
answered Nov 16 '18 at 15:27
Maiki BodhisattvaMaiki Bodhisattva
1837
1837
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
add a comment |
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
The question is how to implement such a function - not whether such a function would make sense ...
– quant
Nov 16 '18 at 16:17
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
Thanks Maiki. I asked the question for tic tac toe. But I am actually working on more complex games, like reversi. The search tree in reversi is large enough that optimizing the code for my function sort_candidate_move() is important apparently.
– JSB
Nov 16 '18 at 16:38
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
@quant I'm not saying it doesn't make sense. I'm saying the difference wouldn't show up in any measurement. I'm answering to the OP concern: "It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe."
– Maiki Bodhisattva
Nov 16 '18 at 17:18
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53340581%2fsorting-move-before-alpha-beta-pruning-tic-tac-toe-python%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
