Hi, I've read the chess tutorials and I've created an iterative deepening alpha beta program for chess. What it does is generate moves and then sort them on the bottom tree of the current search, it then goes through and evaluates them. The moves are then stored in memory as child nodes of the parent node. All of the nodes I go to are stored in memory. When it comes to the nodes again, it sorts them again to make sure the best moves from the last search are ordered first. It then repeats. In addition, I use a killer moves heuristic to try to get quicker beta cutoffs.

This was for the a chess variant that starts off with twice the legal moves as regular chess, but I managed to get anywhere from 5 to 30 seconds per move (it varied at different times of the game--it sped up in the end game it seemed) for a 4 ply search; the moves also generally made sense (though there was some questionable hanging of pieces). I would just match a stronger computer against a weaker computer that didn't search as many plies.

Nevertheless, my computer seemed to get really slow as the searching was being done and my program using 300+ MB.

After reading further, however, I find that storing all the nodes in memory may not be the best way. What specifically would be the best things to store in memory?

You don't need to store the tree in memory, no. At most you need to store the descendant moves from all the nodes in the branch we are currently exploring. This can be done cleanly if you make the list of available moves a local variable of a recursive function.

Then you can use a fixed amount of RAM to remember the results of previous searches, which can save you a lot of time later on if the same position is visited again. This is called a "transposition table".

Quote: Original post by alvaro
You don't need to store the tree in memory, no. At most you need to store the descendant moves from all the nodes in the branch we are currently exploring. This can be done cleanly if you make the list of available moves a local variable of a recursive function.

Then you can use a fixed amount of RAM to remember the results of previous searches, which can save you a lot of time later on if the same position is visited again. This is called a "transposition table".

Thanks. I suppose when I generate the moves I should sort them by whether their positions generate TT hits and then by TT score from highest to lowest to try to get quicker beta cutoffs?

Quote: Original post by beneficii
Thanks. I suppose when I generate the moves I should sort them by whether their positions generate TT hits and then by TT score from highest to lowest to try to get quicker beta cutoffs?

Well, one usually stores the move that was deemed best in the TT, and that's the first one you should try, if you find the current position in the TT. Then usually come all the captures, then other moves. More info here.

Sorting by TT score is one of those things that probably won't work because with alpha-beta search you end up not having reasonable scores for most nodes. But, of course, you should experiment a lot with your program, no matter how crazy the idea.