Okay, our lessons now are on a computational efficient version of minimax called alpha-beta. And then I also want to do a, a fair amount with pure polymorphism in C++. So we're going to get back to a lot of C++. I'm going to show you today, a wonderful example of use of polymorphism, through inheritance in virtual functions. that does the evaluation of Polish expressions. So our two themes are going to be, the alpha-beta algorithm, pretty straight forward. Not going to spend a huge amount of time on it. And then our major effort is going to be, displaying some C++ techniques that are extremely useful in a way that should illustrate the power of modern OO techniques. So, alpha-beta. Alpha-beta, has a history that goes back to, again, at least the 50s. when trying to research a little bit of who invented it. there are three or four or five different people or groups who may have invented it. it's one of those things that anybody who's intensively doing game programming using minimax, and minimax of course, I said was largely formulated by Von Neumann and Morgenstern for games of perfect information. but then, when these things started to get implemented in things like checker and chess programs some of the early implementers of such programs, like Art Samuels, who implemented a great checkers program at IBM. he's one of the possible people who invented, they probably all invented it because it's just as I say, it was a computational shortcut rather than some foundational idea. But then the details and how important it is computationally. The exponential saving you can get out of it was demonstrated in detail mathematically by our greatest living algorithm expert, Don Knuth of Stanford. Also just a truly great programmer as well. So I want a little shout out to Don. He's just down the street from us at Stanford. just to let you know some of his accomplishments and while I won't be going into a lot of that here, Don is of course, extremely well known for his books on The Art of Computation. So, many of the things like Quicksort or pseudo random number generation his books are where you go to really understand them in detail. those algorithms. Again, very worth pursuing for any of you out there who wants to get way more deeply into a number of the comminatoric issues and algorithmic issues that we've been talking about all along in this course. Knuth is extremely prolific. And in many areas, so he also invented the type-setting language "TEX". He was frustrated when he was type-setting his own books. And TEX and LATEX are standard now for type-setting especially theoretical computer science and mathematics papers. He's also known for parsing. Invented one of the foundational efficient parsing methods called, LR parsing. And he did lots and lots of analysis of things like alpha-beta and sorting algorithms. And, looking at him in the worst case using things like adversaries. So, as I say, just wonderful to explore any of his work. Then some of his work is alpha-beta.
