Yes, my project is coming to an end. For school. I plan to continue my work on it, just at a different pace. Slower. Much slower. The last few days I've had enough, it's been tough to keep going. So I'll definitely be glad to have it behind me. Tonight I did a little bit on my paper - very little. Which means I'll need to finish it up tomorrow.
As for the program itself, another enhancement today. Move ordering. Here's the deal. In the beginning there was minimax. With minimax the idea was simple, you would search to a fixed depth (ply) and pull back to the beginning assuming each player made the best moves. What does that do for you? Well, for one, you only have to run your evaluation function on the nodes of the max depth, because those are the scores that you are pulling back to determine which move to play. For another, you're searching all possible moves up to that depth so you're not going to miss anything.
Then came Alpha-Beta. What did that do? Amazingly enough, it gave you a significant speedup... for free! The idea is that while you are scoring the maxply nodes you keep track of a cutoff. So once you find a score that is lower than in a previous branch, you can stop searching that branch because you know that with best play it's not your opponents best move to go down that branch. I may have messed that up a little, but that's the basic idea. So it gives you a significant speedup while coming up with the exact same answer. Not bad.
I have both of those implemented in my project. Tonight I added move ordering. What does move ordering do? It's Alpha-Beta, but you order the moves by what you think will be the best so that you ideally hit the best moves first and a lot more hits on your cutoff. I used one of the simpler methods of move ordering, which is to simply sort the movelist with the "best" captures first. Meaning that if a move captures a Queen it'll be checked before a move that captures a pawn... or nothing. It does slow down the nodes per second that the program can calculate, I'm down to about 100,000 (not just because of this though - implementing transposition tables for 3-fold repetition was a total hog on my performance. I need to work on that, but not until after I turn things in)! But I saw a good 50% reduction in the number of nodes that are being checked now, and my program is quicker when playing 5ply than it was. Which is good. It was taking up to a few minutes to make a move as the position started opening up... and now it's back to well under a minute.
Speaking of Ply, until I implement Quiescent Search (a search extension that goes beyond maxply when there are captures so that it's evaluation quiet positions) I'm thinking that I might be better off defaulting to an even ply (such as 4) instead of an odd ply (such as 5). 6 is too high for the moment, because it really does take minutes a move then. I am thinking this because at ply 5 the computer is the first and last to move. So if on its last move it sees that it can take a piece, it won't see that its piece is lost on the next move, so it will be more prone to making bad decisions. I could implement a 1-ply search extension on captures for odd-depth searches, but again, I'm down to only 1 more day.
Until next time,
Ed.
No comments:
Post a Comment