Memory is NOT the limiting factor
on
Solving Chess?
·
· Score: 1
Just to correct mistake I've seen a lot of people make - When solving a game by building a game tree and then searching all possible lines for one which produces a certain victory, it is not necessary to store the entire tree at once. If you use the basic algorithms for solving a game tree, like MiniMax or AlphaBeta, you generate the game tree recursively as you go, depth first. So at any one time, you only have N board states in memory, where N is the number of moves into the game you have calculated so far. You would also need a list of moves you have already tried so far, and the outcome (win, loss, draw) associated with each. Assuming a game lasted 200 moves, and a 100K to keep track of one board position, a PC would do fine on memory. The problem is simply one of time, as has already been discussed. Out of curiosity, how many people are required to take an AI class as part of their CS degree?
Slashdot Mirror
Just to correct mistake I've seen a lot of people make - When solving a game by building a game tree and then searching all possible lines for one which produces a certain victory, it is not necessary to store the entire tree at once. If you use the basic algorithms for solving a game tree, like MiniMax or AlphaBeta, you generate the game tree recursively as you go, depth first. So at any one time, you only have N board states in memory, where N is the number of moves into the game you have calculated so far. You would also need a list of moves you have already tried so far, and the outcome (win, loss, draw) associated with each. Assuming a game lasted 200 moves, and a 100K to keep track of one board position,
a PC would do fine on memory. The problem is simply one of time, as has already been discussed.
Out of curiosity, how many people are required to take an AI class as part of their CS degree?