I have this work on my university to make AI for chess, but pretty simple one. I implemented MiniMax algorithm already, but its terribly slow, so I decided to try out AlphaBeta pruning.
So I did some research on google of course, I understand how the algorithm should work, but I'm a bit confused about something:
Everywhere I see they say AlphaBeta goes to the first deepest node (leaf), and then evaluates that move and returns it to the parent node. But, as I can see, that is the ONLY time the move is evaluated (I mean only on deepest nodes), because every node that is more "up" from the deepest node doesn't evaluate it's move, it just takes alpha/beta value from its children...
Hope you understand what confuses me.
Looking forward to your replies and help!
Cheers!
marcone wrote: because every node that is more "up" from the deepest node doesn't evaluate it's move, it just takes alpha/beta value from its children...
Yes, but returns the maximum among these values to his parent. So it picks one out of many and returns that: this is call to search.
Lets say you are doing a search to the depth of 2 from the starting position. You start by playing the move e4 on the internal board.
Then you look at the board from the black point of view. (you do a recursive call to search - the function calls itself)
Black plays e5 and evaluates the position which is scored 0. Next black tries all other moves and each evaluates to something < 0. So it now returns the best score 0 to the previous iteration.
White unmakes its move e4 and it is white to move again.
White tries a3 next lets say. Black to move tries e5 and evaluates the position. It finds out that the position gets a score of eg 20. It now knows that if white plays a3 it can score at least 20, white has however already an option how it can score 0 so it will not play a3. And instead of searching all other black replies you can save that time and return immediate. The same will happen with all the other white moves.
So after all white will score the starting position as 0, but this is not through calling evaluation. It is because it knows that after its best move and blacks best response on this move the score of this position will be 0. This score is much more accurate then the call to evaluation, because it takes into consideration the dynamic aspects of the game.
I see.
So basically if I'm searching to depth 6 for example, it will just evaluate the nodes at depth 6? All others are just getting values from their children, comparing them and returning max to its parent?
marcone wrote:I see.
So basically if I'm searching to depth 6 for example, it will just evaluate the nodes at depth 6? All others are just getting values from their children, comparing them and returning max to its parent?
exactly thats the basic idea,
However don't be confused if you look in other engines source code. Many of them do an evaluation on every node. That is mainly done to get a more efficient search tree. For example if you are close to the leaf-nodes (the nodes on the end of the tree where you call evaluation) and find the score is way too low (like you are down a rook or so) then only try moves that are threatening.
With tricks like that you look at certain interesting moves into more detail and skip some less interesting ones.
marcone wrote: But, as I can see, that is the ONLY time the move is evaluated (I mean only on deepest nodes), because every node that is more "up" from the deepest node doesn't evaluate it's move, it just takes alpha/beta value from its children...
Note that typical engines do not evaluate moves, the evaluate positions. The are only interested in the evaluation of the position you eventually get in. They completely disregard the way you get there. (This is a fundamental mistake, of course, but it is how they all do it.)
hgm wrote:
Note that typical engines do not evaluate moves, the evaluate positions. The are only interested in the evaluation of the position you eventually get in. They completely disregard the way you get there. (This is a fundamental mistake, of course, but it is how they all do it.)
Why it is a fundamental mistake?
If evaluation is good enough why should we care about how did we got there? And even if eval isn't good enough anyway, why we should care about the path anyway?
After his son's birth they've asked him:
"Is it a boy or girl?"
YES! He replied.....
hgm wrote:
Note that typical engines do not evaluate moves, the evaluate positions. The are only interested in the evaluation of the position you eventually get in. They completely disregard the way you get there. (This is a fundamental mistake, of course, but it is how they all do it.)
Why it is a fundamental mistake?
If evaluation is good enough why should we care about how did we got there? And even if eval isn't good enough anyway, why we should care about the path anyway?
Three-fold repetition, fifty-moves rule, en passant are path dependent rules. Only because of tricks and luck it's possible to narrow down to positions only.
marcone wrote: But, as I can see, that is the ONLY time the move is evaluated (I mean only on deepest nodes), because every node that is more "up" from the deepest node doesn't evaluate it's move, it just takes alpha/beta value from its children...
Note that typical engines do not evaluate moves, the evaluate positions. The are only interested in the evaluation of the position you eventually get in. They completely disregard the way you get there. (This is a fundamental mistake, of course, but it is how they all do it.)
Although, most engines take into account repetitions that made it to the particular position. It is fairly common to have a repetition check as the very first thing done before doing anything else with a position.
.
