Mixing
Transposition table is only used for roughly 17% of the nodes - is this expected?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I mean that 17% of the positions my engine comes across in its calculations can be automatically given a value (due to the position being calculated previously via a different move order).
For most games, is this figure expected? To me it seems very low, and I was optimistically hoping for the TT to speed up my engine by around 50%. It should be noted though that on each turn in the game, I reset my TT (since the evaluation previously assigned to each position is inaccurate due to lower depth back then).
I know that the effectiveness of TT's are largely dependent on the game they're being used for, but any ballparks of how much they speed up common games (chess, go, etc) would be helpful.
EDIT - After running some more tests and adjusting my code, I found that the TT sped up my engine to about 133% (so it took 75% as much time to calculate). This means those 17% nodes were probably fairly high up in the tree, since not having to calculate the evaluation of these 17% sped up things by 33%. This is definitely better, but my question still remains on whether this is roughly expected performance of a typical TT.
game-ai search gaming minimax efficiency
asked 5 hours ago
Inertial Ignorance
1805
add a comment |Â
up vote
3
down vote
favorite
I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I mean that 17% of the positions my engine comes across in its calculations can be automatically given a value (due to the position being calculated previously via a different move order).
For most games, is this figure expected? To me it seems very low, and I was optimistically hoping for the TT to speed up my engine by around 50%. It should be noted though that on each turn in the game, I reset my TT (since the evaluation previously assigned to each position is inaccurate due to lower depth back then).
I know that the effectiveness of TT's are largely dependent on the game they're being used for, but any ballparks of how much they speed up common games (chess, go, etc) would be helpful.
EDIT - After running some more tests and adjusting my code, I found that the TT sped up my engine to about 133% (so it took 75% as much time to calculate). This means those 17% nodes were probably fairly high up in the tree, since not having to calculate the evaluation of these 17% sped up things by 33%. This is definitely better, but my question still remains on whether this is roughly expected performance of a typical TT.
game-ai search gaming minimax efficiency
asked 5 hours ago
Inertial Ignorance
1805
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I mean that 17% of the positions my engine comes across in its calculations can be automatically given a value (due to the position being calculated previously via a different move order).
For most games, is this figure expected? To me it seems very low, and I was optimistically hoping for the TT to speed up my engine by around 50%. It should be noted though that on each turn in the game, I reset my TT (since the evaluation previously assigned to each position is inaccurate due to lower depth back then).
I know that the effectiveness of TT's are largely dependent on the game they're being used for, but any ballparks of how much they speed up common games (chess, go, etc) would be helpful.
EDIT - After running some more tests and adjusting my code, I found that the TT sped up my engine to about 133% (so it took 75% as much time to calculate). This means those 17% nodes were probably fairly high up in the tree, since not having to calculate the evaluation of these 17% sped up things by 33%. This is definitely better, but my question still remains on whether this is roughly expected performance of a typical TT.
game-ai search gaming minimax efficiency
asked 5 hours ago
Inertial Ignorance
1805
I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I mean that 17% of the positions my engine comes across in its calculations can be automatically given a value (due to the position being calculated previously via a different move order).
For most games, is this figure expected? To me it seems very low, and I was optimistically hoping for the TT to speed up my engine by around 50%. It should be noted though that on each turn in the game, I reset my TT (since the evaluation previously assigned to each position is inaccurate due to lower depth back then).
I know that the effectiveness of TT's are largely dependent on the game they're being used for, but any ballparks of how much they speed up common games (chess, go, etc) would be helpful.
EDIT - After running some more tests and adjusting my code, I found that the TT sped up my engine to about 133% (so it took 75% as much time to calculate). This means those 17% nodes were probably fairly high up in the tree, since not having to calculate the evaluation of these 17% sped up things by 33%. This is definitely better, but my question still remains on whether this is roughly expected performance of a typical TT.
game-ai search gaming minimax efficiency
game-ai search gaming minimax efficiency
asked 5 hours ago
Inertial Ignorance
1805
asked 5 hours ago
Inertial Ignorance
1805
edited 1 hour ago
asked 5 hours ago
Inertial Ignorance
1805
asked 5 hours ago
Inertial Ignorance
1805
asked 5 hours ago
Inertial Ignorance
1805
1805
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (basically would have to know every single tiny detail of your implementation to be able to reproduce).
Some things to consider:
The size of your transposition table / the number of bits you use for indexing into the TT. If you have a relatively small TT, meaning you use relatively few bits for indexing, you'll have bigger probabilities of collisions. That means you will have to replace existing entries more often, which means they might no longer be in the table anymore by the time you encounter transpositions during the search.
Where in the search tree are the nodes located that are recognized as transpositions already in the table? If you detect transpositions very high up in the search tree, you save a lot more search time than if you detect a transposition somewhere deep down in the search tree; once you detect a transposition that has already been searched sufficiently deep for the value stored in the table to be valid, you can cut off the complete subtree below that node from the search. This becomes more valuable as it happens closer to the root. So, just the number "17% of nodes" doesn't really tell us much.
Are you using iterative deepening? Since you mentioned only minimax + alpha-beta pruning in the question, I suspect you're not using iterative deepening. TTs become significantly more valuable once you do use iterative deepening, because then almost every state encountered becomes a "transposition". You'll already have seen all those states in a previous iteration with a lower search depth limit. Now, it is important to note with this combo of ID + TTs, that you can no longer completely cut off searches for all recognized transpositions. If an entry in the table holds a value that was computed with a search depth of $d$, that value will no longer be valid when performing a subsequent iteration of ID with a max search depth of $d + 1$ for example. However, that "outdated" value stored in the TT can still be used for move ordering, which can lead to significantly more prunings from alpha-beta pruning.
How efficient is the remainder of your engine? A TT is not 100% free, it takes a bit of additional time too (for example to compute the hash values for your game states). If the rest of your engine is relatively slow (i.e. inefficient implementation for playing moves, copying game states, etc.), the computational overhead of the TT won't matter much and even a low number of recognized transpositions will still be valuable. If the rest of your engine is very fast, it'll be more important to have a high number of transpositions for the TT to be really valuable.
As an "educated guess", I'd say the number of 17% you describe is not necessarily strange. Especially given your edit to the question, where you indeed mention that it is likely that transpositions are found high up in the tree (close to the root). When this happens, you immediately remove the probability of recognizing all those states deeper down in the tree of getting recognized as transpositions yourself. So, the pool of states that could "potentially" be found in the TT is much less than 100% of the states stored in the TT.
It's really just that though, just an educated guess. It's going to be very difficult for anyone to give a conclusive "yes" or "no".
answered 1 hour ago
Dennis Soemers
2,3291327
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (basically would have to know every single tiny detail of your implementation to be able to reproduce).
Some things to consider:
The size of your transposition table / the number of bits you use for indexing into the TT. If you have a relatively small TT, meaning you use relatively few bits for indexing, you'll have bigger probabilities of collisions. That means you will have to replace existing entries more often, which means they might no longer be in the table anymore by the time you encounter transpositions during the search.
Where in the search tree are the nodes located that are recognized as transpositions already in the table? If you detect transpositions very high up in the search tree, you save a lot more search time than if you detect a transposition somewhere deep down in the search tree; once you detect a transposition that has already been searched sufficiently deep for the value stored in the table to be valid, you can cut off the complete subtree below that node from the search. This becomes more valuable as it happens closer to the root. So, just the number "17% of nodes" doesn't really tell us much.
Are you using iterative deepening? Since you mentioned only minimax + alpha-beta pruning in the question, I suspect you're not using iterative deepening. TTs become significantly more valuable once you do use iterative deepening, because then almost every state encountered becomes a "transposition". You'll already have seen all those states in a previous iteration with a lower search depth limit. Now, it is important to note with this combo of ID + TTs, that you can no longer completely cut off searches for all recognized transpositions. If an entry in the table holds a value that was computed with a search depth of $d$, that value will no longer be valid when performing a subsequent iteration of ID with a max search depth of $d + 1$ for example. However, that "outdated" value stored in the TT can still be used for move ordering, which can lead to significantly more prunings from alpha-beta pruning.
How efficient is the remainder of your engine? A TT is not 100% free, it takes a bit of additional time too (for example to compute the hash values for your game states). If the rest of your engine is relatively slow (i.e. inefficient implementation for playing moves, copying game states, etc.), the computational overhead of the TT won't matter much and even a low number of recognized transpositions will still be valuable. If the rest of your engine is very fast, it'll be more important to have a high number of transpositions for the TT to be really valuable.
As an "educated guess", I'd say the number of 17% you describe is not necessarily strange. Especially given your edit to the question, where you indeed mention that it is likely that transpositions are found high up in the tree (close to the root). When this happens, you immediately remove the probability of recognizing all those states deeper down in the tree of getting recognized as transpositions yourself. So, the pool of states that could "potentially" be found in the TT is much less than 100% of the states stored in the TT.
It's really just that though, just an educated guess. It's going to be very difficult for anyone to give a conclusive "yes" or "no".
answered 1 hour ago
Dennis Soemers
2,3291327
add a comment |Â
up vote
1
down vote
I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (basically would have to know every single tiny detail of your implementation to be able to reproduce).
Some things to consider:
The size of your transposition table / the number of bits you use for indexing into the TT. If you have a relatively small TT, meaning you use relatively few bits for indexing, you'll have bigger probabilities of collisions. That means you will have to replace existing entries more often, which means they might no longer be in the table anymore by the time you encounter transpositions during the search.
Where in the search tree are the nodes located that are recognized as transpositions already in the table? If you detect transpositions very high up in the search tree, you save a lot more search time than if you detect a transposition somewhere deep down in the search tree; once you detect a transposition that has already been searched sufficiently deep for the value stored in the table to be valid, you can cut off the complete subtree below that node from the search. This becomes more valuable as it happens closer to the root. So, just the number "17% of nodes" doesn't really tell us much.
Are you using iterative deepening? Since you mentioned only minimax + alpha-beta pruning in the question, I suspect you're not using iterative deepening. TTs become significantly more valuable once you do use iterative deepening, because then almost every state encountered becomes a "transposition". You'll already have seen all those states in a previous iteration with a lower search depth limit. Now, it is important to note with this combo of ID + TTs, that you can no longer completely cut off searches for all recognized transpositions. If an entry in the table holds a value that was computed with a search depth of $d$, that value will no longer be valid when performing a subsequent iteration of ID with a max search depth of $d + 1$ for example. However, that "outdated" value stored in the TT can still be used for move ordering, which can lead to significantly more prunings from alpha-beta pruning.
How efficient is the remainder of your engine? A TT is not 100% free, it takes a bit of additional time too (for example to compute the hash values for your game states). If the rest of your engine is relatively slow (i.e. inefficient implementation for playing moves, copying game states, etc.), the computational overhead of the TT won't matter much and even a low number of recognized transpositions will still be valuable. If the rest of your engine is very fast, it'll be more important to have a high number of transpositions for the TT to be really valuable.
As an "educated guess", I'd say the number of 17% you describe is not necessarily strange. Especially given your edit to the question, where you indeed mention that it is likely that transpositions are found high up in the tree (close to the root). When this happens, you immediately remove the probability of recognizing all those states deeper down in the tree of getting recognized as transpositions yourself. So, the pool of states that could "potentially" be found in the TT is much less than 100% of the states stored in the TT.
It's really just that though, just an educated guess. It's going to be very difficult for anyone to give a conclusive "yes" or "no".
answered 1 hour ago
Dennis Soemers
2,3291327
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (basically would have to know every single tiny detail of your implementation to be able to reproduce).
Some things to consider:
The size of your transposition table / the number of bits you use for indexing into the TT. If you have a relatively small TT, meaning you use relatively few bits for indexing, you'll have bigger probabilities of collisions. That means you will have to replace existing entries more often, which means they might no longer be in the table anymore by the time you encounter transpositions during the search.
Where in the search tree are the nodes located that are recognized as transpositions already in the table? If you detect transpositions very high up in the search tree, you save a lot more search time than if you detect a transposition somewhere deep down in the search tree; once you detect a transposition that has already been searched sufficiently deep for the value stored in the table to be valid, you can cut off the complete subtree below that node from the search. This becomes more valuable as it happens closer to the root. So, just the number "17% of nodes" doesn't really tell us much.
Are you using iterative deepening? Since you mentioned only minimax + alpha-beta pruning in the question, I suspect you're not using iterative deepening. TTs become significantly more valuable once you do use iterative deepening, because then almost every state encountered becomes a "transposition". You'll already have seen all those states in a previous iteration with a lower search depth limit. Now, it is important to note with this combo of ID + TTs, that you can no longer completely cut off searches for all recognized transpositions. If an entry in the table holds a value that was computed with a search depth of $d$, that value will no longer be valid when performing a subsequent iteration of ID with a max search depth of $d + 1$ for example. However, that "outdated" value stored in the TT can still be used for move ordering, which can lead to significantly more prunings from alpha-beta pruning.
How efficient is the remainder of your engine? A TT is not 100% free, it takes a bit of additional time too (for example to compute the hash values for your game states). If the rest of your engine is relatively slow (i.e. inefficient implementation for playing moves, copying game states, etc.), the computational overhead of the TT won't matter much and even a low number of recognized transpositions will still be valuable. If the rest of your engine is very fast, it'll be more important to have a high number of transpositions for the TT to be really valuable.
As an "educated guess", I'd say the number of 17% you describe is not necessarily strange. Especially given your edit to the question, where you indeed mention that it is likely that transpositions are found high up in the tree (close to the root). When this happens, you immediately remove the probability of recognizing all those states deeper down in the tree of getting recognized as transpositions yourself. So, the pool of states that could "potentially" be found in the TT is much less than 100% of the states stored in the TT.
It's really just that though, just an educated guess. It's going to be very difficult for anyone to give a conclusive "yes" or "no".
answered 1 hour ago
Dennis Soemers
2,3291327
I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (basically would have to know every single tiny detail of your implementation to be able to reproduce).
Some things to consider:
The size of your transposition table / the number of bits you use for indexing into the TT. If you have a relatively small TT, meaning you use relatively few bits for indexing, you'll have bigger probabilities of collisions. That means you will have to replace existing entries more often, which means they might no longer be in the table anymore by the time you encounter transpositions during the search.
Where in the search tree are the nodes located that are recognized as transpositions already in the table? If you detect transpositions very high up in the search tree, you save a lot more search time than if you detect a transposition somewhere deep down in the search tree; once you detect a transposition that has already been searched sufficiently deep for the value stored in the table to be valid, you can cut off the complete subtree below that node from the search. This becomes more valuable as it happens closer to the root. So, just the number "17% of nodes" doesn't really tell us much.
Are you using iterative deepening? Since you mentioned only minimax + alpha-beta pruning in the question, I suspect you're not using iterative deepening. TTs become significantly more valuable once you do use iterative deepening, because then almost every state encountered becomes a "transposition". You'll already have seen all those states in a previous iteration with a lower search depth limit. Now, it is important to note with this combo of ID + TTs, that you can no longer completely cut off searches for all recognized transpositions. If an entry in the table holds a value that was computed with a search depth of $d$, that value will no longer be valid when performing a subsequent iteration of ID with a max search depth of $d + 1$ for example. However, that "outdated" value stored in the TT can still be used for move ordering, which can lead to significantly more prunings from alpha-beta pruning.
How efficient is the remainder of your engine? A TT is not 100% free, it takes a bit of additional time too (for example to compute the hash values for your game states). If the rest of your engine is relatively slow (i.e. inefficient implementation for playing moves, copying game states, etc.), the computational overhead of the TT won't matter much and even a low number of recognized transpositions will still be valuable. If the rest of your engine is very fast, it'll be more important to have a high number of transpositions for the TT to be really valuable.
As an "educated guess", I'd say the number of 17% you describe is not necessarily strange. Especially given your edit to the question, where you indeed mention that it is likely that transpositions are found high up in the tree (close to the root). When this happens, you immediately remove the probability of recognizing all those states deeper down in the tree of getting recognized as transpositions yourself. So, the pool of states that could "potentially" be found in the TT is much less than 100% of the states stored in the TT.
It's really just that though, just an educated guess. It's going to be very difficult for anyone to give a conclusive "yes" or "no".
answered 1 hour ago
Dennis Soemers
2,3291327
edited 1 hour ago
answered 1 hour ago
Dennis Soemers
2,3291327
answered 1 hour ago
Dennis Soemers
2,3291327
answered 1 hour ago
Dennis Soemers
2,3291327
2,3291327
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fai.stackexchange.com%2fquestions%2f8403%2ftransposition-table-is-only-used-for-roughly-17-of-the-nodes-is-this-expected%23new-answer', 'question_page');
);
Post as a guest
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
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
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
