Quote:Original post by tomekdd
To tell the truth I am not a pro in implementing graph searching algorithms, but as far as I know to use BSF game tree have to be created at the very beginning(or a vector with all vertices?)
I'll try to clarify alvaro's point with this analogy. If you have the set of all integers from zero to two million, do you first have to put all those numbers into a std::vector to be able to go through each of them and tell which of them are prime numbers? Of course not, since you can generate the numbers on demand: after having checked number 'i' for primality, you know you need to check the number 'i+1' next, unless 'i+1' > 2,000,000 when you stop. So, you just increment the previously checked number by one, and call the CheckIfPrime() function again for that newly generated number.
How did you avoid having to put all these numbers to a std::vector, but still be able to operate on them? You defined a Successor function which tells you the successor, or the next element, that comes after the element 'i', namely 'i+1'.
With minimax game tree search, it is no different. You do not have to put your whole game tree into memory to be able to operate on the tree. At any given time, you only need to look at one board state, so all you need to keep in memory is that board state. The rules of the game give you the equivalent of the Successor function, but this time, there are multiple Successors (children) of the given state, so you do need to keep track of which children you have already searched, and which you haven't. But this is very little amount of memory (at minimum, just a single integer at each parent of the current node telling which child index to look at next)
Using the rules of the game, you can transform the current board state to a next board state, on-demand, with a legal Move action. Minimax is a bit more complicated than the prime-search example above, that we have to be able to go back up the tree as well, so we solve this by generating Undo moves that match each Move action we have made.
Using the Move and Undo actions, we can successfully navigate the game tree without ever having to hold but a single game board state in memory at once. To be able to quickly tell which node to look at next when we make an Undo move, we have to have some book-keeping information for each parent of the current node, but that only requires #current-search-depth entires of stack memory.
I hope that was a successful analogy.