Not logged inRybka Chess Community Forum
Up Topic The Rybka Lounge / Computer Chess / Alpha beta engine with infinite analysis for decades
- - By rocket (****) Date 2020-08-15 14:10
What happens once the horizon is reached and no more positions can be examined? Does it go into an infinite loop?

Also, how much stronger in elo terms would an alpha beta engine be that examines 1 position each for 50 years?
Parent - - By Uly (Gold) Date 2020-08-16 17:24 Edited 2020-08-16 17:38
50 Years is nowhere close to reach the horizon due to Chess' branching factor. First, since we're letting it search for so long, let's make it search smartly, so that the branching factor doesn't explode later. She'll find the right move in a week, and its correct reply in the next, and so on, otherwise all the previous time could have been wasted and when it switches moves in the PV it's like starting from scratch or worse.

Nobody knows how to do this in real life, so we'll imagine we already have some sort of magic algorithm that finds the right move in a week, so it's already playing perfect chess at one week/move time controls. This would be costly, so it couldn't be as fast as today's programs to reach depth, and it'd not be able to cut its branching factor below 2 (that'd require some pruning which would make it just a dumb algorithm which could switch its main move years later, which would be terrible for us.)

With all that being set, let's see how this imaginary entity would analyze the opening position:

Depth 50 in 1 week. It finds that 1.e4 is the best move.
Depth 51 in 2 weeks. It finds that 1.e4 e5 is the best continuation.
Depth 52 in 1 month. It finds that 1.e4 e5 2. Nf3 is the best continuation.
Depth 53 in 2 months. It finds that 1.e4 e5 2. Nf3 Nc6 is the best continuation.
Depth 54 in 4 months. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 is the best continuation.
Depth 55 in 8 months. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 is the best continuation.
Depth 56 in 16 months. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4.Ba4 is the best continuation.

Huh, to keep it simple, let's say it did that in a year. It works because of forced moves down the line (say, the line with 4.Bxc6 only had 2 moves worth considering a reply, so it saved 4 months of work.)

Depth 57 in 2 years. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 is the best continuation.
Depth 58 in 4 years. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5.O-O is the best continuation.
Depth 59 in 8 years. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5.O-O Bc5 is the best continuation (Be7 is a better defense but it leaves black with no chance of winning. Bc5 can be afforded because we'll know black will be playing perfect moves in the future).

Depth 60 in 16 years. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5.O-O Bc5 6.c3 is the best continuation.
Depth 61 in 32 years. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5.O-O Bc5 6.c3 O-O is the best continuation.
Depth 62 in 64 years. It finds that 1.e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5.O-O Bc5 6.c3 O-O 7.d4 is the best continuation.

And that's it. After 64 years of searching we have found that those are 13 perfect plies for both sides, and that no matter how long you search after this, you won't be able to improve on this line. But we already knew that! Because we already knew none of these moves were losing! All this turns out to be a big waste of time.

And the 14th ply will be ready on another 64 years!

And you can't be faster than this (or you can't guarantee it.) Assume we have an algorithm that is twice as efficient, in this time instead of 13 perfect plies, we get to 26. The problem is that any of those moves could fail low, say, it finds that there's some defense that makes it reach a position worse than the advantage of white on the opening position, and it could switch its first move to 1.d4. But now it only has 1 ply! It has to rebuild a new line for this, and you'll get nothing back for years until it has 26 perfect plies for 1.d4. If that falls it could fail low and go back to 1.e4. 1.e4 could go up and force 1...e5 to fail, and make it switch to the Sicilian 1...c5, and now it needs to build the 26 perfect plies line for it.

Depth 63 could take longer than 200 years, and you'd have no idea if the 26 plies that survived would fall down in a future iteration.

(and all this assumes it has access to infinite memory! We gave it magic memory as well.)

Where's the horizon depends on the position. If we assume your opponent wants to put the horizon the furthest away from you, let's say it can force the game to continue for 256 moves before you can reach 7-men tablebases and stop searching.

You'd need at least 512 perfect plies to reach this horizon, since 100 years weren't enough to get you 14 plies, this should give you an idea.
Parent - - By rocket (****) Date 2020-08-16 21:18
I meant a middle game position with all pieces on the board.
Parent - By user923005 (****) Date 2020-08-17 18:55
If you mean pure alpha-beta, then with a branching factor of 36, the best you can hope for is a minimum of 6^k nodes visited, where k is the ply forward and that assumes perfect move ordering.
Realistically, you won't do quite that well.  When you try the number 6 to integer powers, you will find that your calculator will overflow before long because the numbers become too large.

On the other hand, real world alpha-beta searchers do more pruning than just the perfectly sound alpha-beta pruning.  AB pruning will give the exact same answer as examining every single node in the tree.
Other techniques are called unsound, because they can make you possibly miss something.  An example of this kind of pruning is null move pruning.  But it works so well everyone does it even though it can introduce a problem (especially when you are zugzwang).   Another very popular technique is called late move reductions where you prune based upon existing information derived from previous searches.

So, the best chess engines have an actual effective branching factor of about one and a half rather than 6.  That is how they can search to depth 70, which would be impossible with pure alpha-beta except for very specialized positions.

A pure alpha-beta searcher is not a practical chess engine when we compare it with contemporary software.  It would be so absurdly out-searched that it would be clobbered in a humiliating way against a top "unsound"  engine.
Up Topic The Rybka Lounge / Computer Chess / Alpha beta engine with infinite analysis for decades

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill