< Earlier Kibitzing · PAGE 22 OF 22 ·
|Mar-14-17|| ||maxi: <sudoplatov> I have missed your comment until now. I assume it is related to what <AylerKupp> and I were discussing back then. It is a good idea to cite some of the people in the discussion, to make the contribution easier to find, just as I have done with your name and AylerKupp's.|
Would you care to explain a bit more to a layman what you mean by "The alpha-beta always returns the value of the game tree that a full search would (it's provable)."
|Mar-19-17|| ||AylerKupp: <sudoplatov> I also missed your comment until now which, depending on your perspective, it might be better if you <don't> mention other user names in your post (at least mine) since that makes it harder for me to respond and therefore it saves you the agony of possibly looking at my posts. :-)|
But, since it's too late now, let me elaborate as to why I said that increasing search depth entails a narrowing of the search trees. A the search depth increases the width of the search tree also increases as more nodes are defined for the leaves of the previous ply. But the number of branches that are considered by the engine is roughly constant and limited by the engine according to what its search heuristics indicate are the most promising branches to expand. So the ratio of actual branches examined to the number of possible branches (which increases exponential) get smaller at each ply. That's what allows engines to search to deep plies in a reasonable amount of time.
And, since so far you haven't responded to <maxi>'s question about alpha-beta (pruning), allow me to try, although of course you can correct me if I'm wrong.
<maxi> Alpha-beta pruning is an improvement over the basic minimax evaluation used by, as far as I know, all the chess engines. Its advantage lies in ordering the search tree so that the most promising tree branches (the ones with the highest evaluation of their leaf node in the minimax sense) are searched first. This is called optimal ordering. If that is done then, if a branch of the tree results in a lower leaf node evaluation than one of the most promising branches, it does not need to be considered further. This results, on the average, in the reduction of about 1/2 of the calculations needed to reach a particular search depth, allowing either the reaching of that search depth in a smaller amount of time or the reaching of a greater search depth in the same amount of time.
What makes alpha-beta pruning particularly effective is that it can be shown (you can find many instances on the web) that the search of search tree with alpha-beta pruning will yield the same results (the Principal Variation and sub-variations) as the search of a search tree without alpha-beta pruning, provided that the move ordering is optimal. For that reason, FWIW, I consider alpha-beta pruning to be an algorithm rather than a heuristic.
As an aside, the need for optimal ordering to achieve best alpha-beta pruning results has a great significance in the non-determinism of multi-core chess engines (two analyses of the same position, on the same computer, by the same engine, conducted to the same depth, will yield different results). This is because the searches are performed by different threads executing in different cores and, as each of those threads are interrupted by higher priority systems processes), they complete their search at different time, the move ordering is modified, and this leads to different results from analysis to analysis.
|Mar-21-17|| ||Petrosianic: You know, speaking of Fred Reinfeld again, there's a position I saw in an old Reinfeld book years ago with a motif very similar to the Re1 line that wasn't played in this game. In both games, there's a Rook to the Back Rank motif intended to remove the protection from a checkmate on KN2. And the kicker is that THIS move wasn't actually played either.|
Fred gave this position:
click for larger view
The winning line is 1. Bxf7+ Kxf7 2. Rf1+ Kg8 3. Rf8+ Rxf8 4. Qg7++.
According to Fred, this line wasn't played because White resigned over the fact that his Queen was pinned to his King and he didn't see how to get out of it.
The annoying part is that Fred would often use examples from real GM games in his books (I remember seeing a Rosanes-Anderssen game in one), WITHOUT telling you who the players were. So, although he tells you White resigned in a winning position here, he doesn't tell you who White was, when the game was played, or anything that might help you identify it. It could be two GM's, or it could be an offhand game he saw in a club. I'd love to see the entire score to this one.
|Mar-27-17|| ||maxi: <AylerKupp>, thanks for the explanation on alpha-beta pruning. I find your posts always very interesting.|
|Mar-27-17|| ||maxi: You are right, <Petrosianic>. I remember having similar doubts. But my first two chess books were A Chess Course (or something like that) by Reinfeld and Capa's Chess Fundamentals! Sometimes Capablanca too would put a chess diagram and not quote the source game. I figured people just didn't write down what the original games were!|
Later I realized Capa would do that with positions from his own games.
|Mar-27-17|| ||sudoplatov: A couple of points about alpha-beta. Given a minimax search tree to a fixed depth, alpha-beta will return the same value (not necessarily the same move) as a complete search. The algorithm works by noting that both sides are trying to minimax their play. |
A couple of caveats are in order. The actual speedup depends on move ordering. Always choosing the best move first in a search (the so-called principal variation) helps. In real implementations, the hash table operates more or less independently of the search tree. So the evaluation of a position may not be exactly the same if positions are examined in a different order; mostly this doesn't matter. The alpha beta search is not usually either a depth-first nor a width-first tree search. One does a depth-first to depth 1; then depth-first to depth 2, etc. The early shallow searches help with ordering; filling the hash table, and may find a game-ending move early.
The point of alpha-beta is that nodes that are pruned cannot influence the final score of the root position (assuming that the evaluation function is accurate.) Thus deeper searches always give a better estimate of the actual position.
Another point is that only quiescent positions are considered leaf nodes. In a quiescent position, there are no captures, checks, or pawn promotions.
There are other algorithms (B* is popular) which do forward pruning. So far, in computer chess (as far as I have read) none of these are as effective as alpha-beta; the
|May-01-17|| ||Mithrain: 12 ... e5 shows how well Fischer understood the dynamics of the position (seriously weakening the d5-pawn but gaining a lot of play with his minor pieces).|
|Jul-06-17|| ||The Kings Domain: Poor Byrne brothers, the whipping boys of ol' Bobby. |
Fischer's smooth escalating type of victory is perhaps unmatched in the game. His brilliancies are usually simple but there's a magic to them that can be awe-inspiring.
|Jul-06-17|| ||Petrosianic: <The Kings Domain: Poor Byrne brothers, the whipping boys of ol' Bobby.>|
Actually, Robert was maybe Bobby's toughest US opponent after Reshevsky. You need to study more than just one game.
|Sep-02-17|| ||Penguincw: Video analysis of this game: https://www.youtube.com/watch?v=QHy....|
|Jan-13-18|| ||CheckMateEndsTheGame: On move 14. Why not just play f3?|
|Jan-14-18|| ||GT3RS: Fischer was built in a lab.
A brilliant and underrated short game. Bryne made no obvious error leading up to the fatal queen move or should I say rook move.
From what I've read there was a lengthy analytic artillery exchange via articles in chess publications afterward as Soviet analysts sought to diminish the result by showing Bryne's win with the other move and Fischer responding with analysis to show a plausible draw.
|Jan-15-18|| ||Petrosianic: <GT3RS: Fischer was built in a lab.|
A brilliant and underrated short game.>
Underrated? You've got to be kidding me, Pyle. This is the one that everyone raves about.
|Jan-22-18|| ||scottpi: Why Didn't Byrne play 21. Nf3? What was Fischer's reply to that?|
|Jan-22-18|| ||ChessHigherCat: <scottpi: Why Didn't Byrne play 21. Nf3? What was Fischer's reply to that?>|
Fischer was planning to take the cyanide pill in his signet ring if white played 21. Nf3.
Either that or Bxf3+ 22. Kxf3 Qf6+ followed by Qxc3. That only wins back the piece and leaves Fischer a pawn up, so there's probably better, but I don't see it.
|Jan-22-18|| ||Gregor Samsa Mendel: <scottpi: Why Didn't Byrne play 21. Nf3? What was Fischer's reply to that?>|
21..Qxd2+ 22 Rxd2 Bxc3 and black will be up the exchange and a pawn.
|Jan-23-18|| ||Granny O Doul: And winning more material still with ...Re3 coming up after gathering the exchange.|
|Jan-23-18|| ||Howard: Yes, Fischer could hardly have overlooked 21.Nf3 in his calculations. You just "know" that that move would not have worked for White or even come close---otherwise, Fischer would have acknowledged the move in his book.|
|Jan-30-18|| ||yurikvelo: https://pastebin.com/kqfHg5Qt
|Feb-09-18|| ||Artemio: It's a Gruenfeld similar to his game with the other Byrne (Donald)...|
|Apr-13-18|| ||Justin796: There's a Herbert James Fischer in the 1700s who supposedly won every game with the black pieces, and never won with the White pieces except on Wednesday, 1776!|
|May-26-18|| ||offramp: Has anyone ever seen this game annotated anywhere without the final quip about the grandmasters in the other room?|
|May-26-18|| ||Retireborn: <offramp> I don't think I even know who these two(?) grandmasters were, although I have seen Rossolimo named as one.|
|May-26-18|| ||offramp: <This dazzling move came as the shocker... the culminating combination is of such depth that, even at the very moment at which I resigned, both grandmasters who were commenting on the play for the spectators in a separate room believed I had a won game! -- Robert Byrne>|
The commentators were not Fischer or Robert Byrne. I suppose it was Reshevsky and Kashdan... what other US grandmasters were there?
And how many spectators were there? December 18th, 1963 in New York's deep midwinter - who would come along to see a chess game?
I would imagine a dozen or so spectators and two chess masters, and the masters are being paid five nickels an hour, and the spectators aren't sure how knights move....
|May-26-18|| ||Howard: Soltis mentions who those other two grandmasters/commenters were, and I do recall that one of them was indeed Rossolimo. But I'll be darned if I can recall the other one. Just consult that book, though.|
< Earlier Kibitzing · PAGE 22 OF 22 ·