Archived

This topic is now archived and is closed to further replies.

Merge2

Game Search

Recommended Posts

Two things: First quetsion. In a game like chess or checkers, is it more efficient to perform the "search" using a search function that calls itself recursively until the specified depth is reached, or is it more efficient to build an actual search tree, with nodes, pointers to sibling nodes and child nodes? It seems like a recursive search might be a little more efficent, but that building a tree would allow you to prevent restarting the search everytime it''s your turn to move, and that the tree would allow you to simply keep searching the entire time you are playing, during it''s turn, and during it''s opponents turn. I figured I would ask this question before I spend a lot of time trying to implement both methods and testing for myself, only to find that one method is way better than the other. Second question is regarding the transpositionable table and the STL. It seems like using the STL''s map template would be a good candidate for the transpositionable table. If you know how the transpositionable table and the STL''s map template, I''d love to know if you have any thoughts on that. Thanks for your help

Share this post


Link to post
Share on other sites
I think building a tree each move and iteratively transversing it would be the fastest. Use a parent pointer to ''go back up'' the tree, and leave a bread crumb to remember where you were.
The speed difference with recursion isn''t huge, but it can add up - the deeper you search for the best move the bigger difference it''ll make.
The first rule of optimization is to minimize function calls.

What''s a transpositionable table?


Magmai Kai Holmlor
- The disgruntled & disillusioned

Share this post


Link to post
Share on other sites
Ok, I didn''t think about the repeated function calling being a problem. Anyone who has actually done this that doesn''t just "think" one way is better? Thanks.

Share this post


Link to post
Share on other sites