3.6 alpha-beta Algorithm Preview

Loading...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part B

73 ratings

University of California, Santa Cruz

C++ For C Programmers, Part B

73 ratings

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

From the lesson

Hex and the use of AI and C++ Move semantics

This module explains Min-Max and the Alpha-Beta algorithm for game playing. Its programming topics include C++ 11 Move semantics and a detailed example of referential garbage collection.

3.4 Lookahead12:50

3.5 Plausible Move Generator22:47

3.6 alpha-beta Algorithm Preview4:54

3.7 alpha-beta Improvement to Min Max15:02

Meet the Instructors

Ira Pohl
Professor
Computer Science

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.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play