Need a little help with improving search speed

[Thecoolman5]

Hi everybody. I have been developing a rather simple chess engine for a while now and I have hit a wall. I recently finished my searching algorithm and as of right now, it is in its most bald state meaning it searches every possible move and looks for what it can kill and what can be killed. Now, I am looking for ways to improve the search speed. Besides all the basics like improving my move generation and stuff, how should I go about this? I have read about alpha beta pruning but it makes absolutely no sense. How can you know if a tree is safe to be pruned when you don't search down it? Any insight would be great. Thanks!

[cdani]

Maybe you want to see here:

https://chessprogramming.wikispaces.com/Alpha-Beta

[Volker Annuss]

I have read about alpha beta pruning but it makes absolutely no sense. How can you know if a tree is safe to be pruned when you don't search down it? Any insight would be great. Thanks!

Imagine you have the choice, either get 1€ or pick the least valued coin from a bag that contains many coins of various currencies and values. Don't you think its safe to prune search after you have discovered one 1€ coin? Once you found it, it is no longer necessary to evaluate all those other coins. That's what alpha beta pruning does.

[hgm]

Alpha-beta pruning is absolutely fundamental to Chess thinking; humans employ it too. It is based on the principle of 'refutation'. When you consider a move that deviates from your original plan, and you find the opponent has a single move that makes it end bad, this single move refutes the deviation. You are then no longer interested in his other moves. They might get you mated, which would be even more reason to not play that deviation, or they might get him mated, in which case he would not play them, but stick with the refutation you already discovered.

E.g. suppose you can play Nxc5, and after careful analysis see that it safely gains you a Pawn, because c6 was unprotected. Now you consider to play Ne5+ instead, in the hope it is better, as it forks his King and Queen. After some thought you see that this will actually lose you a Knight, because e5 was unfortunately attacked by a Pawn, so that the opponent can play fxe5 to refute Ne5+. This should be enough for most people to discourage them from paying anymore attention to Ne5. The won't be interested what would happen if the opponent would not play fxe6, and in particular what would happen if he allowed you to capture his Queen, and how long it would take you to checkmate him after that, and how precisely you would do that.

Well, that is alpha-beta. If you find one move that makes the preceding opponent move end worse as what is already proven that the opponent can achieve, you consider that preceding move refuted, and won't spend any time on trying to find other, worse refutation. A single refutation is good enough. In alpha-beta terminology this is called a 'beta cutoff'.

[Greg Strong]

Alpha-Beta is key. It's the most important way to reduce tree size. How can you know if it's safe to prune without examining everything? I'll try to explain with an analogy.

First, let's pretend we're playing a game where you have a bunch of items and I get to pick any one I want and you have to give it to me. I'll pick the one that is the most valuable. In order to determine this, I have to look at every single item. This is like a Chess engine performing a search to depth 1. Alpha-Beta doesn't help.

But now, let's consider a depth 2 search. In our fictional game, this is like, instead of you having items and I get to choose one, you have a bunch of bags each of which contains a bunch of items. I get to pick which bag, but then you get to pick which item from the bag you give me. I want the most valuable item and you want to give me the least valuable item. So, do I have to look at everything? First, I examine every item in the first bag. I know that if I pick this bag, you will give me the least valuable item inside - so the only value that matters is the value of the least valuable item in the bag. But to determine that, I have to look at every item in the bag. Let's say I do that and the least valuable item in the first bag is a dollar bill. Knowing this, I have a "floor" on my search. I know that I can get at least a dollar. That's Alpha. So now I move on to the second bag. The first item I look at in the second bag is a penny. As soon as I can see this, I can safely ignore everything else in the bag. I already know if I choose this bag I will get, at most, a penny and I know I can do better. It is irrelevant for my purposes what anything else in the bag is worth. We've just pruned the search tree

If we take this a step farther to a depth 3 search, now it's like bags within bags, and now we have both an Alpha and a Beta. (My Alpha is your Beta.) If I find something too lousy, (beneath my Alpha), I know I can ignore it. But starting with depth 3, there's now a possibility that I can ignore things because they are too good! This happens because if I find something too good at depth 3, that means there's a decision you could have made at depth 2 that would prevent my from getting here. So a score higher than Beta is a Beta cut-off and it also means I can ignore the rest of this branch on the move tree.

So, as we go deeper and explore more and more of the move tree, our "window", the space between the value of Alpha and the value of Beta, starts to narrow and we can start ignoring more and more.

An important detail to note is that, in order to benefit from Alpha-Beta, you have to try to look at better moves first. If you consider moves in the worst possible order, you will get no benefit at all. Let's consider our depth 2 search again. If the second bag I look at doesn't have anything of less value than a dollar, I have to look at everything in that bag also. And so on, and so on. So you have to try to guess which moves will be good. (Capturing a Queen is likely good, moving pieces into the corner is likely bad, etc.)

[Thecoolman5]

I see how it works and it makes sense (ish) but here is my problem: aren't there branches of the tree that end up returning a higher value than the root weight? If I sacrifice my queen and down the road a few moves, the opponent is forced into giving me his queen and a rook, won't that branch be pruned? What about mating the opponent? If I can force the opponent into a mate, but that requires the sacrifice of a few pieces, won't that branch be pruned as well?

[hgm]

You prune the branches that would always be avoided, if not by player A, then by player B. If there are (say) 3 half-moves leading to position P, let us call them X, Y and Z... Now player B, which played move Y, has an already thoroughly verified alternative Y' for move Y that will put him 0.5 Pawn in the lead. And player A has an alternative Z' for Z that will put B 1 Pawn ahead...

Now the score after Z is only of interest if it is between 0.5 and 1 Pawn in favor of B. If it ends worse for B then +0.5 Pawn, B would prefer to play Y' over Y to get his +0.5, and A would never get the opportunity to play Z. If Z ends better for B then +1 Pawn, A would prefer to play Z' over Z, to limit B's advantage to +1. In either case, Z would not be played.

That does not mean that Z can be pruned yet, but it does mean that at this point in the search the root score is limited to ly between -1 and -0.5 from A's point of view. But suppose that in another case the score after Z' would be equal (instead of +1 for B). Then if the score after Z would be in favor of B, A would prefer to play Z' over Z. While if the score after Z was worse than +0.5 Pawn for B, B would prefer Y'. These two cases overlap, so together they cover every possible value. No matter what the score would be, it has already been established that one of the players can get a better score by notplaying Z, or preventing you can get to the position where it is possible to play C.

[Thecoolman5]

I'm sorry but I'm still a little lost. The idea makes perfect sense up to depth 2. Root move 1 plus the worst enemy move (for me) returns a value of 3. The next root move plus the first possible enemy move from that root move returns a value of 2; therefore, root move 1 is better. Quit searching root move 2.

How does that carry to depth 3 and beyond?

Btw, thanks for the help guys. I really appreciate it.

[hgm]

The root is not really different from a PV node deeper in the tree. If after 6 ply candidate-move 1 for ply number 7 scores 3, and a reply to candidate-move 2 there returns a value of 2, you can also quit searching there, as candidate-move 2 now is refuted.

A small difference is that you can now also quit searching (opponent moves in in the ply 8 node) if that score 3 was not from candidate-move 1 for ply number 7, but from an already searched candidate move at ply 5, 3 or 1. In the root the path leading upto it is empty, so the only possible alternatives to deviate if the currently searched line is refuted are in the root itself.

Normally the situation in the search is this: in every node along the path to the node that you are searching now you have a number of moves that were already completely searched, a number of nodes you have not looked at at all, and a single move that you are currently searching. The moves that have already been completely searched define a minimum score (from the mover's perspective) for that node; if what still has to be searched (including the line you are searching now) will score lower, they will just ignore it, and play the (best) already-searched move instead.

E.g. suppose in the roout you can capture a clean unprotected Pawn, or you could capture a piece, after which murky tactics ensues (your Queen gets pinned, but you can interpose a Knight that is difficult to protect etc.) So after having determined to your satisfaction that capturing the Pawn indeed brings you ahead a Pawn without any complications, and start thinking about capturing the piece, you find that after 4 more moves the opponent has a move that captures BxQ. This makes you lose interests in that line, and in particular you won't waste time to figure out what would happen if he would not capture your Queen (but perhaps go directly for your King). At that position you would lose at least a Queen, and you know that with the alternative move in the root you could have avoided all trouble. It would be the same if the choice between taking the Pawn or the piece would only have occurred at ply 3.

[Dirt]

I see how it works and it makes sense (ish) but here is my problem: aren't there branches of the tree that end up returning a higher value than the root weight? If I sacrifice my queen and down the road a few moves, the opponent is forced into giving me his queen and a rook, won't that branch be pruned? What about mating the opponent? If I can force the opponent into a mate, but that requires the sacrifice of a few pieces, won't that branch be pruned as well?

No. Alpha-beta is only good for the depth you are searching. When you search deeply enough to see the queen and rook return on your sacrifice you won't prune it.

Example:
One ply search -> NxP wins a pawn
Two ply search -> Pawn is protected NxP PxN loses a knight, prune it
Three ply search -> Second pawn was pinned against the queen NxP PxN BxQ, do not prune