Placeholder Image

字幕列表 影片播放

  • The following content is provided under a Creative

  • Commons license.

  • Your support will help MIT OpenCourseWare

  • continue to offer high quality educational resources for free.

  • To make a donation or to view additional materials

  • from hundreds of MIT courses, visit MIT OpenCourseWare

  • at ocw.mit.edu.

  • CHARLES E. LEISERSON: OK, let's get started.

  • On Thursday, we are really privileged to have

  • Jon Bentley, who is one of the masters of performance

  • engineering, come and give us a guest lecture.

  • In 1982, he wrote this wonderful little book

  • from which we adapted the Bentley

  • rules that you folks have seen.

  • And he's also famous for things like kd-trees.

  • Who's seen kd-trees. trees?

  • Yeah, so he invented kd-trees.

  • And who's ever used the master method of recurrence solving?

  • He invented the master method of recurrence solving.

  • And so he's just a wonderful, wonderful fellow,

  • with lots and lots of insights, and just a superior performance

  • engineer.

  • And he's going to give a guest lecture on Thursday.

  • And so I would encourage you to bring your friends.

  • Bring friends maybe who dropped the class,

  • and others who if any of you have UROPS, other people

  • in your research group, whether they're graduate students,

  • they're all welcome to come.

  • Because this is really one of the opportunities

  • you get to actually meet one of the legends of the field,

  • if you will.

  • And you'll see he's very approachable.

  • He's very approachable.

  • So anyway, my advertisement for Jon Bentley.

  • Good.

  • So let's start.

  • I want to talk about speculative parallelism for a little bit,

  • because that's kind of what you need to make the code go fast.

  • So if you look at code like alpha beta,

  • it turns out that it's inherently serial.

  • That is, if you try to do things in parallel,

  • then you missed the cutoffs.

  • And if you missed the cutoffs, then you

  • start doing work that you wouldn't necessarily

  • need to do.

  • And so the only way to sort of make this type of code run

  • fast is to use speculation.

  • Which is to say, that you're going

  • to guess that you can do stuff in parallel

  • and it'll be worthwhile, and then, occasionally, you're

  • going to be wrong.

  • But the trick is, well, how do you minimize the wasted effort

  • when things go wrong?

  • So let's just take a look at a very simple example

  • of speculative parallelism, which is thresholding a sum.

  • So here we have a little program that is returning a boolean.

  • It takes as input an array of size n.

  • So thresholding a sum-- we have an array

  • of length n and a limit.

  • And these are all unsigned integers, say.

  • And I start out the sum at 0, and what I'm going to do

  • is add up all the elements of the array.

  • And if it exceeds the limit, then I'm going to return.

  • And so how might I optimize this code a little bit?

  • Yeah.

  • AUDIENCE: Split up [INAUDIBLE] four processes, [INAUDIBLE]

  • split up an array [INAUDIBLE].

  • CHARLES E. LEISERSON: No, let's say on processor.

  • On one processor, what might you do?

  • AUDIENCE: In the middle of the loop,

  • you can check [INAUDIBLE].

  • CHARLES E. LEISERSON: Yeah, once you

  • check so that once you would exceed it,

  • why keep adding the other numbers?

  • So here's a code that does that-- quit early

  • if the partial product ever exceeds the threshold.

  • This isn't necessarily an optimization.

  • Because notice that now in the optimization,

  • not only do I have a memory reference and an addition,

  • I also now have an unpredictable branch.

  • Actually, it's predictable branch--

  • predictable branch.

  • But it's still one more step, because it's always

  • going to predict that it's not exceeding until it actually

  • does exceed.

  • So that'll be pretty predictable.

  • But still, I've added something into the loop

  • so that maybe slower.

  • How might I mitigate that problem?

  • So I don't want to add too much into the inner loop.

  • Yeah.

  • AUDIENCE: It could have an inner loop

  • that goes [INAUDIBLE] them.

  • CHARLES E. LEISERSON: Yeah.

  • So basically, I can do what's called strip mining.

  • I replace the loop of n iterations with a loop of,

  • let's say, n over four iterations,

  • with an inner loop of four iterations.

  • And every fourth iteration, I check

  • to see whether or not I've exceeded,

  • so that the cost of the check is going to be relatively

  • small at that point.

  • So are there ways of making this sort of go fast.

  • So now, we want to make this operate in parallel.

  • And the problem when I operate in parallel

  • is that as I'm adding stuff up, I want to do it.

  • So I'm going to do this here with a reducer.

  • And so, basically, I'm going to add up

  • the values in the reducer.

  • But now, I'd like to do the same thing

  • of being able to quit early.

  • And so the question is, well, how

  • can we parallelize a short-circuited loop?

  • And so, the way I'm going to do this-- and this

  • is sort of by hand here, but it's

  • going to give you-- so actually, as you

  • know, underneath the loop is really a divide

  • and conquer loop.

  • And so I could write it as a parallel loop.

  • And now, it becomes, I think, a little bit clearer

  • how I could, in this case, what I'm

  • going to do is return the value of the sum.

  • And now the question is, well, how

  • can I quit early and save the work if I exceed the threshold?

  • Understanding that when I'm executing

  • this and something like Cilk, it's

  • going to tend to go down one path.

  • And often, it's going to be a serial execution.

  • So I'd like if it's possible.

  • So here's one way of doing it, which

  • is that I add an abort flag to the code, which

  • is going to say whether I should keep going

  • or whether I've actually exceeded at that point.

  • And so I'm going to use that recursively.

  • And now, I take a look, for each time through the loop--

  • or through the divide and conquer--

  • to see whether the sum is greater than a limit.

  • And I haven't you know already aborted the flag,

  • then I set the abort flag to be true.

  • Why do I bother testing the abort flag

  • before I set it to true?

  • So notice that setting the abort flag is a race,

  • isn't it-- a determinancy race.

  • Because-- great.

  • Thank you.

  • It's because I have the stuff operating in parallel

  • is all trying to set the abort flag whenever something aborts.

  • I can have two guys who are in parallel setting

  • the abort flag.

  • But if they're setting it, they're

  • setting it to the same value.

  • So it's a benign race, assuming your memory model is such

  • that you can actually set the values.

  • So what happens here when--

  • why do I why do you bother checking this?

  • So what happens when several guys in parallel

  • want to write to the same variable?

  • This is quiz 1 stuff.

  • Yeah.

  • AUDIENCE: Cache bouncing.

  • CHARLES E. LEISERSON: Yeah.

  • You can have it bouncing along the cache.

  • It will serialize it.

  • Because if they're all trying to write,

  • then they have to get exclusive access for it

  • to write and modify it.

  • And so that happens-- boom, boom, boom-- one at a time.

  • And so by checking it first, it can be in a shared state,

  • and then one guy clobbers it, and then

  • it will update all the other ones.

  • So it makes it so we don't continually

  • have a true sharing race.

  • And then in checking to see if it exceeds,

  • we basically just check to see--

  • we basically call this function. we set the abort flag to false,

  • and then we return the sum of all the values.

  • And if it aborts, then it just returns early.

  • So it doesn't have to keep going through the computation.

  • And, of course, once again, you can coarsen

  • the leaves and so forth.

  • So this is nondeterministic code, which we should never

  • write unless we have to.

  • Because that's the only way of getting performance.

  • And you have to make sure you, of course, reset the abort flag

  • after the use.

  • And then, actually, do you need a memory fence

  • here on the abort flag?

  • Do you need to set--

  • where would you put an abort flag

  • to make sure that the value was--

  • yeah.

  • AUDIENCE: Maybe do it by setting default [INAUDIBLE]..

  • CHARLES E. LEISERSON: Yeah.

  • So what would you have to do?

  • AUDIENCE: Put a [INAUDIBLE].

  • CHARLES E. LEISERSON: OK.

  • So indeed, it turns out you don't need a memory fence here.

  • And the reason is because the code is correct,

  • whether it's the initial value false

  • or whether it's become true.

  • So it doesn't matter when it becomes true.

  • And so there's an issue of, if you put in the fence,

  • then you know that it becomes true earlier,

  • rather than waiting for the computation.

  • But that may actually slow things down,

  • because memory fences are expensive.

  • But because the transition is always

  • from false to true during the execution,

  • you don't actually need a memory fence there

  • in order to make sure that you've got the correct value.

  • Does that makes sense?

  • So you don't need a memory fence.

  • So that's a classic instance of speculative parallelism.

  • It occurs when our program spawns

  • some parallel work that might not be performed

  • in a serial execution.

  • So you're performing it, anticipating

  • that you're probably going to need to do it.

  • And then, typically, what you want to do

  • is have some way of backing out if you discover that you

  • didn't need to do it that way.

  • Have some way of making sure that you don't do any more.

  • So basic rule of speculation is, don't spawn speculative work

  • unless there's little other opportunity for parallelism

  • and there's a good chance it will be needed.

  • So one of the things I've seen, in research papers, no less,

  • is people who say, oh, I'm going to have a calculation where

  • I'm trying to find, say, the minimum of a bunch of values.

  • And so I'm going to spawn off n things, each of which

  • is looking for the minimum.

  • As soon as the minimum one comes back,

  • I'm going to retract all the other computations.

  • And I'm going to get super linear speed up that way.

  • Because in the serial execution, I

  • might have done the longer one first.

  • And maybe the minimum is not the first one or whatever.

  • And so they claim super linear speedup

  • by doing speculative parallelism.

  • But that's not really a good example,

  • because there was a better serial code.

  • If that was really a good way of doing it,

  • they should have been doing what's

  • called dovetailing, which is doing

  • a little bit of this computation,

  • a little bit of this, a little bit of this,

  • a little bit of this, et cetera, and then going back.

  • That would have been a better algorithm for which you

  • would then use it.

  • And the risk they have is that they're spawning off

  • n things, of which most of them may not be needed,

  • and now they don't get any speed up,

  • even though they've just used a lot more work.

  • And that often is a bad choice.

  • So usually, you don't want to speculative work

  • unless there's little other opportunity

  • and there's a good chance it'll be needed.

  • My experience is, what kind of chance do you need?

  • You need to have certainly less than--

  • for parallelism, if the chance that you're going to need

  • the work-- if you have p processors,

  • if the chance that it could be not needed is less than--

  • actually, I have a theorem at the end which

  • all which I've I'll refer you to,

  • because it's a little bit hard to say,

  • because I didn't put on the slide.

  • But there's a final slide for this,

  • which gives a nice little theorem about when

  • you should do this.

  • So now, let's talk about parallel alpha-beta search,

  • because that's kind of what you're

  • doing with your principal variation search.

  • So if you remember the analysis done by Knuth and Morris,

  • they basically showed that for a game

  • tree with the branching factor b and depth d,

  • and alpha-beta search with moves searched

  • in best-first order examines it exactly

  • b to the ceiling of d over 2 plus b to the floor of d

  • over 2 minus 1 nodes at ply d.

  • So that's basically square rooting the amount of work

  • that you would need if you did a full depth ply.

  • That's with alpha-beta.

  • So naive algorithm looks at b to the d nodes at depth d.

  • And so for the same work, the search depth

  • has effectively doubled, or the work is square rooted.

  • So that we solved last time in Helen's lecture.

  • So the key optimization here is pruning the game tree.

  • And as I mentioned at the beginning of this,

  • when you prune the game tree, you've

  • got what's effectively a serial thing.

  • And if you let something go ahead,

  • you may be working on something that would be pruned.

  • So then how does the parallelism really help you there?

  • You're just wasting processors that could be better

  • spent perhaps elsewhere.

  • Except, where else can you spend it?

  • Because there's no other parallelism in the code.

  • So we want to find some solution.

  • So the solution comes from an idea

  • from a very nice paper by Burkhard Monien

  • and some of his students in Germany.

  • And they made the observation that in a best-ordered tree,

  • the degree of every node is either 1 or maximal.

  • This is not their observation, this

  • is actually the observation in the Knuth paper.

  • So when you have a best-ordered tree,

  • if you can get all the moves ordered in their true order,

  • then it turns out that either you're

  • exploring all the children or you are refuting something

  • and you get a cutoff from the very first one

  • that you look at.

  • And so in this case, for example, it turns out,

  • on the principal variation, those are all full-width--

  • sorry, you have to explore all the children.

  • And then from there on it alternates.

  • One level, you have just a single child

  • that needs to be explored.

  • And when you explore it, if it's best-ordered,

  • you will get a beta cutoff for the others.

  • And then it alternates, and then it's full-width.

  • And so their idea was to say, well,

  • if the first child fails to generate a beta cutoff,

  • speculate that in fact you have the best one,

  • and the remaining children can be searched in parallel

  • without wasting any work.

  • So if it fails, you're going to say,

  • oh, I'm going to speculate that this

  • is in fact a full-width thing.

  • Now, in practice, you don't necessarily

  • get things best-ordered, but there

  • are a bunch of heuristics in the code we've given you

  • in chess code to make it so that you tend to do things

  • in the proper order.

  • The most important of those is, if you've seen the movie before

  • and it's in the transposition table,

  • you use the move that you've seen before, even

  • if it's to a shallower depth.

  • You guess that that's going to be their best move still,

  • even if you search deeper.

  • And that's pretty good.

  • And so they call that the young siblings weight algorithm.

  • They actually called it the young brothers weight,

  • but in the modern era, we call it young siblings weight.

  • And we abort subcomputations that proved to be unnecessary.

  • So you're going to start out searching,

  • but then you want to get rid of things

  • that you discover, oops, I did get a cutoff from searching

  • from one of these things.

  • I don't need to do this.

  • Let's not have it keep spawning and generating

  • work and some other thing, let's abort it.

  • And here's the idea for the abort mechanism.

  • So what you do is--

  • the abort can occur at any given node.

  • You get a beta cutoff--

  • you want to abort all the children that wouldn't

  • have been searched anyway.

  • But they may have already been spawned off.

  • So they have a record in each node that tells you

  • whether or not you've aborted.

  • And what you do is you just simply climb up the tree

  • to see, periodically, whether or not

  • you have an ancestor who is aborted.

  • If you have an ancestor that's aborted,

  • it says I'm aborting the side computations,

  • then you say, oh, I'm done, and I just have to return.

  • And so you check that on a regular basis.

  • So do people follow what that mechanism is?

  • And so, that's basically what you're

  • going to be implementing for the parallelization,

  • is this thing of climbing up.

  • You're going to guess, after you've searched one child,

  • that it's good.

  • Hey, actually some people say, why don't you

  • check two before you search the others,

  • so that you're even more sure that you

  • don't have a cutoff, because neither of the first two

  • aborted.

  • Because, in practice, of course, the game tree

  • is not best-ordered.

  • And so you're going to waste some work.

  • But the idea is, you're going to pull up the tree

  • to see whether or not-- and, of course,

  • you don't want to pull on every evaluation that you do,

  • you want to just pull frequently.

  • So you may have a counter in there

  • that says, OK, every 10th time, I'm going to pull up the tree.

  • You put a voodoo parameter there that says

  • how often it makes sense to actually check, because there's

  • cost to going up and checking versus exploring

  • more of the tree.

  • And so, I have an example here.

  • And I think this is where I'm going to cut this short.

  • So there's an example, which I suggest you take a look at.

  • I want to, as I say, spend time doing Q&A, and talking

  • about the other parts of the program,

  • and give you folks some good ideas for the thing.

  • So this is sort of the theory thing,

  • and then I have some slides that will explain this

  • with examples in more depth.

  • Because I don't expect that everybody

  • got every detail of this.

  • So I have some examples and so forth in here

  • that I'm going to let you guys look at on your own.

  • Now, if you parallelization the spawning

  • off loop of the younger siblings,

  • you will get a code with races.

  • And the reason you get races is because there are several--

  • the are three data structures--

  • that the search is employing that are kind of global.

  • The first is the transposition table--

  • looking things up to see whether or not you've seen them before.

  • That's a major optimization.

  • You don't want to get rid of the transposition table.

  • And so you have a choice with the transposition table.

  • What are you going to do with it?

  • Are you going to lock it so that the races become--

  • at least your data-- race-free and updated atomically.

  • Or you could replicate it.

  • For example, you could have a worker local copy of the data

  • structure, and each worker that is working on it

  • only accesses their own local copies.

  • Or you can make a copy when things are stolen

  • or you can make just one where you maintain it locally.

  • Or you can decide that, well, even if there's a race there,

  • the odds that it's going to affect how I play in the game

  • are not that high, so I'll run with the race.

  • Because any other solution is going to be more expensive.

  • And then maybe you get funny answers.

  • So one thing for that kind of data structure,

  • let me just recommend that you have

  • some way of turning of the data structure

  • so that you can actually do the parallel search

  • and get deterministic, repeatable results.

  • So even though it may be aborting

  • and some things may not be aborting,

  • you want to have some way of executing.

  • And so, for example, you want to be

  • able to turn off even the speculation in your code,

  • so you can test all the other things

  • in your code that don't depend on the speculation.

  • Because if you have something that's not deterministic,

  • as I say, it's a nightmare to debug.

  • So you're going to do the evaluation function.

  • Hey, if you're testing it, turn off the speculation.

  • You should be able to find out whether you've got bugs

  • in your evaluation function.

  • There's no point in discovering you of a bug,

  • and it's like, well, where did it come from or whatever.

  • So you want to have things you're turning out.

  • And also, want to have ways of turning off,

  • for example, access to the transposition table.

  • Yes, I'm going to speculate, but no, I'm

  • not going to access the transposition

  • table in parallel, because I may get

  • a race on the entry in the transposition table.

  • The hint that I will give you for that

  • is that in the code for our program

  • that took second prize in the world computer chess

  • championship many years ago--

  • I think it was in 1999--

  • where we actually almost won the tournament,

  • and we lost in the playoff.

  • We would have won the tournament,

  • except that our programmer suggested a rule

  • change at the beginning of the tournament

  • that everybody agreed to, and then we

  • were on the short end of that.

  • Otherwise, we would have been world champions.

  • And that was the last competition

  • against computers that Deep Blue, the IBM computer that

  • beat Kasparov, the human [INAUDIBLE],,

  • just a few months later.

  • They performed it.

  • And they placed third in the tournament.

  • We tied for first.

  • Our only loss was to Deep Blue.

  • And we were running on an 1,824 node supercomputer

  • at Sandia National Labs, a computer that probably is today

  • less powerful than this.

  • But it was very big type of computation.

  • They basically said, if there's a tie,

  • they're going to base who wins on strength of opponents.

  • So you take a look at your opponent's records,

  • and if you had stronger opponents,

  • you'll win against somebody.

  • And we said, you know, if there's

  • a tie just between two programs, we

  • should really have them face-off against each other

  • as an extra round.

  • And everybody said, yeah, that's a good idea.

  • And then, wouldn't you know, at the end,

  • we had the strongest opponents, and we

  • were tied with another program called

  • Fritz-- an excellent program.

  • And we were outsearching Fritz in the playoff game.

  • And then we saw a move that afterwards,

  • when we were able to do offline searches deeper,

  • we were outsearching them by like 2 ply.

  • But then there's a move that looks

  • like it's a good move for the depth we were looking at it--

  • doesn't look like a good move if you

  • search much deeper, or frankly, if you search much shallower.

  • It was one of these things where it just

  • looked like a good move for the ply

  • we happened to be searching.

  • Because there's no guarantee--

  • because you can't see the end of the game--

  • that if you search deeper you're actually

  • going to beat somebody else.

  • Because there's the horizon effect of you just

  • simply can't see what's coming up in the future.

  • You can only see sort of on average.

  • So we made this bad move.

  • We almost recovered.

  • We almost tied.

  • Had we tied, we would have been world champions,

  • because we had the stronger--

  • we won the tiebreaker.

  • And we weren't able to recover from the error.

  • And so we took second prize.

  • It was like--

  • [LAUGHTER]

  • Anyway, in that program, we decided

  • that we were just going to let there

  • be a race on the transposition table.

  • And the reason was, we calculated,

  • what are the odds that the race actually

  • affects the value that you would actually pick that value?

  • And if it affected the value, what

  • are the odds that it affects the move that you're going to make?

  • And if it affects the move you're going to make,

  • what are the odds it affects the game?

  • And if it affects the game, what are the odds that affects

  • your result in the tournament?

  • And when you've figured all these things out,

  • it was like, eh, we would slow the program down more

  • by putting in, for example, locking--

  • because that would slow down every access--

  • than we would if we just ran the thing.

  • Because one of the things that happens in alpha-beta

  • is if you get an extreme value, usually those are lopped off.

  • Because if it's such a good move for you,

  • your opponent's not going to let you play it.

  • So if you ended up with a score that was extreme

  • because it was based on a value that you were racing on,

  • usually it's going to not even propagate up

  • to the root of the tree.

  • So anyway, we just ran naked, so to speak.

  • So there are two other data structures

  • you going to have to worry about to make decision about.

  • Another one is the killer data structure.

  • So the killer data structure is a heuristic

  • that says, at a given depth of code,

  • you tend to see the same moves that are good.

  • And a move that is good for one thing at a given depth,

  • tends to be good for something else.

  • So for example, it may be that you play bishop takes queen.

  • So you've won the other players queen.

  • And then their response is to do something irrelevant.

  • Well, now you mate them.

  • Well, there's a lot of other moves

  • where you could make them on that move, for which they're

  • playing things on the board that are irrelevant.

  • and.

  • So the same type of move tends to be a killer--

  • always, you're able to, at that depth in that position,

  • make the same move.

  • And if they don't address the issue,

  • that's always a good move to check.

  • And so that ends up being ordered near the front.

  • So the killer table keeps track of that.

  • And I think, in our code, we have two killers.

  • Is that right, Helen?

  • I think it's set up to allow you to do for up to four killers,

  • but we only do two in the code that we gave you.

  • And you can enable it and see whether four killers--

  • but that's a shared data structure.

  • And so one of the questions is, should you

  • be keeping a local copy of that or should you

  • be you using a global one that they all share and updating it?

  • The third one is the best move table,

  • which is used to order all the low order thing.

  • So the first thing that's most important

  • is, did you get a move out of the transposition table?

  • That tends to be quite accurate.

  • And the second is, did you get a move out of the killer table?

  • And finally, it's, statistically,

  • how good are these moves?

  • Have you seen these a lot before?

  • If you've seen them a lot before,

  • that's how the other moves get ordered.

  • And that's kept in the best move table.

  • And once again, that's a shared table.

  • In the search, you're going to have to figure out,

  • do you want to do a thread worker local copy,

  • or do you want to synchronize it,

  • or how are you going to manage that data structure?

  • And the answer, I would say, is different

  • compared to what you do with a transposition table.

  • The transposition table, generally, it's

  • not worth locking or whatever.

  • And it is good to share.

  • Because if you have seen that move before,

  • that saved you a huge amount of computation

  • to be able to look it up and not do it.

  • So those are some of the tips for parallelization, which

  • we'll get to in the beta 2.

  • But now, I want to talk about, for most

  • of the rest of the time, some of the other things

  • that you can do with the code you've currently got.

  • And let me take these in some order,

  • and then we can ask questions.

  • So opening-- who's contemplating doing an opening book?

  • Anybody?

  • For beta 1?

  • Are you going to do an opening book for beta 1 or beta 2?

  • For beta 1, let me see.

  • OK.

  • Beta 2?

  • Who wants to do an opening book better 2?

  • Final?

  • OK.

  • Yeah, OK.

  • So the idea here is to precompute best moves

  • at the beginning of the game.

  • So, well, we know what the starting position is.

  • So why don't I spend $1,000 or whatever on Amazon,

  • and compute things to some ungodly ply,

  • and see what the best moves are at the beginning of the game,

  • and put that into a book so I don't have to search those?

  • So that's the idea.

  • I think, to begin with, there are lower hanging fruit

  • than the opening book.

  • If you look at it, you're going to be an opening

  • book, if you're lucky, for six or eight moves.

  • And the games tend to last-- have

  • you looked to see how long games tend to last?

  • What is it?

  • AUDIENCE: [INAUDIBLE]

  • CHARLES E. LEISERSON: No, most games don't go 4,096.

  • We don't let them go that long anyway.

  • So did anybody take a look, statistically,

  • to see how long games are?

  • I think they tend to be like 40 or 50 moves.

  • I mean, this year is different from other years,

  • because we have different rules.

  • But I think it's like 40 or 50 moves.

  • So you're not spending--

  • you're doing something that will help you in 10% of the game.

  • Whereas there are other places you

  • could do it which are going to help you in the whole game.

  • Nevertheless, we've had teams that

  • did a great job on opening books and clobbered people

  • by having a fantastic opening book.

  • It's actually cheaper to keep separate opening books

  • for each side than to keep one opening book for both sides.

  • And in this game, it's actually fairly easy

  • to keep a symmetry thing and basically

  • have one opening book that works for the side on move.

  • And that allows you to store.

  • You don't have to store--

  • if I make a given move, if I have a given position,

  • I only need, in principle, to store

  • one answer for that position.

  • Whereas, then, my opponent may make any number

  • of moves for which then I only need to know one move-- what's

  • my best move in that position.

  • So you can see that you have, once again,

  • this property, that on my move, I only

  • need to have one move stored.

  • My opponent's moves, I need to have all the moves stored.

  • And then my move, I have one move store.

  • And that basically means that you're effectively

  • going twice the depth, as if you kept all my moves,

  • and then all of the other opponents

  • moves, and then all of those.

  • Because when I do that, it's like, well,

  • why do I need to know the best move.

  • So it's better to keep them separate.

  • When you build the opening book, you'll store a lot less.

  • You'll have a lot smaller storage.

  • You'll be able to store a lot more moves if you do that.

  • But I would say, not necessarily the first thing

  • I would go to optimize.

  • But it's also the case that this is

  • a place where one of the teams built a fabulous opening

  • book one year.

  • And one of the things about the opening book

  • is it allows you also to sort of threshold

  • and say, in a given move, I don't just

  • have to have one move.

  • Let me have three moves and pick randomly among them,

  • so that I'm not predictable.

  • What the team did that used the opening book is they

  • observed that everybody was searching from the beginning.

  • So they were all finding exactly the same moves

  • at the beginning of the game.

  • And so they knew exactly what the path

  • was that all the other programs were going to follow.

  • And so they could make the best move on their move.

  • But if you have something that's got some randomness to it--

  • and there is a jitter in there.

  • Who found the randomness--

  • the place we insert randomness in the code?

  • So I think Zach had a comment on Piazza about that.

  • So there's a place in the code where

  • we dither the amount so that you will get unpredictable results.

  • And that way, you won't always play the same move, just

  • by changing things.

  • Because a hundredth of a pawn value is not very big.

  • And who cares whether or not we have--

  • these heuristics aren't measuring things

  • so closely that we care about a hundredth of a pawn.

  • So you can dither things and have

  • one move be better than another and not really affect

  • the quality of the playing.

  • So it is a good idea to do something

  • to not be so predictable.

  • But to build a full opening book, that's

  • a lot of work for beta 1.

  • For beta 2 and the final, yeah, you'll get to that point.

  • The next thing is iterative deepening.

  • Do people understand how this part of the search code works?

  • Yeah?

  • No?

  • Let me go over it.

  • So you can imagine, say, I'm going to search to depth d.

  • And in fact, instead of just searching depth d,

  • we do a depth 1 search.

  • If you look at the code there, there's a depth 1 search.

  • And then we do a depth 2 search.

  • Then we do a depth 3 search.

  • Then we do a depth 4 search.

  • And we keep doing that until our time control expires.

  • Why is that a good strategy, generally?

  • Well, first of all, the amount of work with each depth

  • is growing exponentially.

  • So you're only spending, in principle,

  • a constant factor more work than you would if you searched

  • to depth d right off the bat.

  • But the important thing is that you

  • can keep move ordering information

  • as you search deeper.

  • And the move ordering information,

  • remember, we want our searchers to use best-first move ordering

  • so that we get all the cutoffs we can possibly

  • get for pruning.

  • And so by searching it easier, actually you

  • end up with better move ordering.

  • Because when you find that same position in the transposition

  • table, you say, oh, well.

  • I didn't search it as deep as I need to search it now.

  • So I can't use the value that's in the transposition

  • table for the position, because maybe I've searched something

  • that's ply 8 in the transposition table,

  • but I've got it searched to ply 9--

  • not good enough a search.

  • But the value-- the move that you've found at 8--

  • that's probably a pretty good first move--

  • pretty good guess at best move.

  • So by doing iterative deepening, you actually

  • get the move ordering for all those intermediate positions

  • really really, really strongly.

  • Because that transposition table is the very best information

  • you've got for what the your best move is.

  • And also, as I mentioned, is a good mechanism

  • for time control.

  • Is that clear?

  • So that's why you bother.

  • It's one of these things that looks like it's redundant.

  • Why are you searching-- if you're

  • going to search to depth d, why search to depth d minus 1?

  • You're going to that as part of depth d.

  • Well, no, because you're going to get move ordering

  • information that's going to be really valuable when

  • you search to depth d minus 1.

  • So when you search to depth d, you've

  • got much better pruning than if you just

  • went straight to depth d and had no information

  • about the move ordering.

  • Does that makes sense?

  • Endgame database-- so here's the idea.

  • If there's a few enough pieces on the board,

  • you can precompute the outcomes and store them in a database.

  • So for example, the most common database to come up with

  • is the king versus king database.

  • So if you do King versus King, that

  • means that it's not that you expect the game will end up

  • as king versus king, it's that you're

  • going to encounter that in the search.

  • It'd be nice to know who has the win if you're King versus King.

  • Now, the code actually plays optimally for king versus king.

  • The code we gave you will play the king versus king perfectly

  • well.

  • And, in fact, there's just two heuristics

  • that are responsible for that.

  • One is called k aggressive heuristic,

  • which basically makes you move towards your opponent.

  • And the other one is the k face heuristic,

  • which makes you point towards your opponent.

  • And those two things turn out to do a pretty good job of when

  • there's one there's two kings and playing,

  • they go through this little endgame.

  • Did everybody do that by hand, by the way?

  • Did you play king versus king?

  • A really good idea if you want to understand the game

  • is just go and do a king versus king version of the game.

  • Get an eight by eight chessboard and just put down

  • two tokens kings that have orientations, and then just

  • you and a friend, just try to see if one can mate the other.

  • And you'll see that it goes through a very ritualistic type

  • of behavior which ends up with one of the Kings being mated.

  • So it's nice to know which one it's going

  • to be so if you encounter that.

  • But here's the question, how many games

  • actually make it to an endgame?

  • Once again, you have to look at what the odds are there.

  • Because if games are ending in the middle game,

  • there may not be any need to search

  • all the way to the endgame.

  • So that's something that you need to weigh.

  • Now, if you do an endgame database,

  • it doesn't suffice to just store win, loss, or draw

  • for a position.

  • And the reason is because you can get into a situation

  • where you've got a winning position,

  • and then you say, OK, well, let me move to another winning

  • position, and another winning position,

  • and another winning position.

  • Oh, and I'm back at my original winning position.

  • And I just keep going around in a circle,

  • always in a winning position, never moving towards the win.

  • And that, of course, will end up in a draw.

  • So you need to know which direction do you

  • go for the winning position.

  • So the typical thing you do there is you

  • keep the distance to mate to avoid cycling.

  • So instead of keeping just a boolean value,

  • you say, here's my distance to winning.

  • My distance to winning is 6.

  • Now, when I'm searching, I don't want

  • to go a distance to winning that 7 or 6,

  • I want to go to distance to winning

  • that's 5 when I make my move.

  • So it's very important to make sure

  • that you maintain the distance in order to avoid cycling.

  • Quiescence search-- we talk about quiescence,

  • which is to make sure that when you're doing the evaluation

  • you're not in the middle of an exchange.

  • So you zap their pawn, they're going to zap your pawn,

  • or maybe even zap your King.

  • And you don't want evaluate in the middle there.

  • And so the idea of quiescence is that when

  • you're done with the regular search,

  • you just play off moves that involve captures,

  • and then you evaluate the position.

  • So that's quieting the position.

  • Make sense?

  • Another heuristic there is null-move pruning.

  • In most positions, there's always something

  • better to do than nothing.

  • So sitting still is usually not as

  • good as actually making a move.

  • And so, the idea is, suppose that I can forfeit my move,

  • and search a shallower depth, and I still

  • have the best position--

  • then I still am winning.

  • And it generates a cutoff.

  • Then why bother exploring any other moves?

  • I probably am in a really good position here.

  • OK And if I don't manage to get a cutoff from the null-move,

  • then I do the full depth search.

  • So the place this is dangerous is in Zugzwang.

  • In chess, it's called Zugzwang situations.

  • So Zugzwang is a situation where everything is fine,

  • but if you have to make a move, you lose.

  • So usually, having the advantage of a move,

  • that's called the initiative in chess, and that's a good thing.

  • You want the initiative.

  • You want to have the extra move over your opponent.

  • But there are some situations where if you move, you lose.

  • And so you want to make sure you don't

  • have a Zugzwang situation.

  • I don't actually know if there's a Zugzwang

  • situation in Leiserchess.

  • So if somebody comes up with one,

  • I'd be interested to see that, where if I had to move,

  • I lose--

  • but if I sit there.

  • So in chess, what they do, is in the end game--

  • that's when Zugzwangs come up--

  • they turn off the null-move pruning.

  • So is this clear what null-move does for you?

  • What's going on there?

  • I see some people who are quizzical.

  • Anybody want to ask a question?

  • I see some people with sort of quizzical looks on their faces.

  • So the idea is for null-move, my position

  • is so good, that even if I do nothing, I still win.

  • So I don't want to search anymore in this part of it,

  • because I get a beta cutoff, you're

  • not going to let me make this move--

  • the move that got me here.

  • Yeah, question?

  • AUDIENCE: That was it.

  • CHARLES E. LEISERSON: OK.

  • That was it.

  • OK, good.

  • My move is so good, I can do nothing, and I still win.

  • And so why bother?

  • Let me verify that without necessarily

  • doing as deep a search.

  • So null-move is fairly cheap to do,

  • and it often results, in a lot of positions, for cutoff.

  • And if I don't get a cutoff, then I just

  • do the normal search.

  • This is a pretty complicated piece of code, isn't it?

  • Pretty complicated.

  • There are other situations.

  • We mentioned killers.

  • There's also move extensions.

  • So typical move extensions that people look at

  • is you grant an extra ply in chess

  • if the king is in check, or for certain captures,

  • or if you have a forced move.

  • So suppose you have a move and it's

  • the only move you can make, then don't count that as ply.

  • So you can search deeper along lines

  • where there are forced moves.

  • That's what they do in chess.

  • In Leiserchess, not quite so clear what you do--

  • which ones you would do extensions for.

  • Because it's rare that you have just one

  • move in Leiserchess, compared to an in chess.

  • By force move, it's like, if you don't do this,

  • you're going to get captured, or mated, or what have you.

  • So that may come up in Leiserchess.

  • But anyway, it's something to think about.

  • So the transposition table, we talk

  • about this as a search tree, but it's really a dag,

  • because I can get to the same position by transposing moves.

  • This guy does a, this guy does b, this guy just c,

  • this guy does d.

  • It's the same thing by doing a, d, c, b.

  • I transpose those two moves, and I get

  • to exactly the same position.

  • And so I'd like not to search that position again

  • if I've seen it.

  • And that's what the transposition does.

  • There's a quality score that is in the transposition table that

  • tells you how good to move you've made.

  • And the quality is essentially the depth

  • that you had to search in order to establish

  • the value that stored in the transposition table.

  • And so you don't want to use something of too low quality

  • when you're searching.

  • If you have to search the depth d,

  • something of quality d minus 1 is not good enough.

  • Because, otherwise, you'll not be searching the full tree.

  • But something typically that is deeper--

  • if I'm looking at depth d and I find something

  • in the transposition table that's d plus 1 or d plus 2,

  • that's great to use.

  • That just gave me an even deeper view

  • of what's behind that move.

  • And so if you look at the logic there,

  • you'll see that that's how they do it.

  • It's very tricky.

  • One of the things that's tricky is

  • when you find a mate, how you store that in the transposition

  • table.

  • And you'll see, there's special code

  • for handling mate positions.

  • And the reason is because what you're

  • interested in doing when you find a mate is

  • knowing your distance to mate.

  • But not from that position--

  • the distance to mate from the root of your search.

  • So, for example, let's say this is the root of my search,

  • and I search down to a given point.

  • And now, I do a lookup in the transposition table,

  • and I discover that there's a mate in 5 here.

  • And this, let's say I've searched 9 ply or something.

  • Well, if I store that this is a mate in 5,

  • and I store the value for mate in 5,

  • then if it makes it up to the top here,

  • it thinks there's a mate and 5.

  • But there isn't a mate in 5, there's a mate in 14.

  • So when you look it up and you discover

  • there's a mate and 5 in the table,

  • you have to do a little bit of a calculation to translate that

  • into being a mate in 14 as the value

  • that's going to be used here, rather than a mate in 5.

  • Does that makes sense?

  • So you'll see, that's the logic that's in there for dealing

  • with mates.

  • So a mate basically takes a very large number--

  • way larger than all the material on the board--

  • and then it subtracts what your number of ply

  • is to get to mate.

  • So some big number--

  • I don't know, 32,000 or something--

  • minus the depth to mate is how you represent a mate.

  • So it's some very, very big number

  • and then minus the depth.

  • And that way, you can make sure that you're

  • going for a mate in 13 instead of a mate in 14,

  • for example, preferring that you take the shorter path.

  • Makes sense?

  • So that's one of the things to look at in there.

  • And there's also a lot of stuff in there.

  • The transposition table has--

  • we talked about caching--

  • it's actually a k-way associative cache.

  • And so you can vary k to see what's

  • the best choice of how many entries you should have.

  • The more entries you have, the longer

  • it'll take you to search them.

  • On the other hand, the more likely

  • it is that good move stay in the cache.

  • So you can decide what's the right trade-off there.

  • So there's a good tuning optimization there.

  • Questions?

  • Any questions about transposition table?

  • Transposition table is a major optimization.

  • So Zobrist hashing-- so most of these, Helen

  • talked about at some level.

  • But I wanted to give a chance to have people ask questions.

  • Nobody's asking questions.

  • I came here for Q&A. All you're getting is A.

  • [LAUGHTER]

  • So let me explain Zobrist hashing again a little bit.

  • So Zobrist hashing-- very clever idea.

  • So we have our board with a bunch of pieces on it.

  • That's probably the wrong number of squares, right?

  • That's seven by six.

  • OK, who cares.

  • So the idea is that what I'm going to do

  • is have a table of random numbers

  • that I'm going to compute in advance.

  • And this is going to be indexed by my row, my column, my piece

  • type, and my orientation.

  • And every different combination of row, column, type,

  • and orientation corresponds to a different random number

  • in the table.

  • So we have some sort of random number there.

  • And what my hash function is is it's

  • the XOR of all of the values of all the pieces

  • that are on this table with their orientations.

  • OK so if I have a king here, that's a white king--

  • I guess I need to know not just what

  • the type is, I also need to know whether it's white or black--

  • so the side.

  • I think, actually, that gets encoded somehow.

  • But in any case, I think maybe in the type

  • we actually keep whether it's a white pawn or black pawn.

  • Yeah, it's in the type, I think, is the way we actually

  • implemented that.

  • So there's white king, black king, white pawn, black pawn,

  • or space.

  • So if I have a king there, that corresponds to a certain value.

  • If I end up with a pawn here--

  • let's say, a white pawn--

  • then that will be another one, and I XOR those together.

  • And I take the black king and I XOR

  • his position is, and the black pawn, XOR that in.

  • So I XOR all these four values.

  • That's the hash function that I use

  • to do things like look up things in the transposition table.

  • Now, if I had to compute this every time

  • I changed the position, that's if I have a lot of pieces--

  • how many pieces I've got, 7, 8, 16 pieces?

  • Each side has seven pawns and a King.

  • So 16 pieces-- I have to do 16 XORs in order

  • to compute my hash function.

  • So Zobrist hashing is really clever.

  • It takes advantage of that XOR trick

  • that I taught you in the first--

  • no, it wasn't the first, it was in the second lecture?

  • Yeah, the bit tricks lecture.

  • And that is that XOR is its own inverse.

  • So if I want to remove a piece-- let's

  • say I'm going to move this pawn from here to here.

  • So I remove this piece.

  • What do I do to my hash function to remove a piece?

  • I look up the value for that pawn in the hash table

  • and I XOR that into my hash for the table.

  • And I now have a hash for those three pieces left.

  • Does that make sense?

  • So I have my hash function, which

  • is a hash of the four things.

  • I'm not sure you guys can see very well there.

  • And I simply XOR it with the hash of the pawn

  • that I removed in this case.

  • And now, I moved it to here.

  • So what do I do?

  • I look up that one and I XOR that value in here

  • for the new position--

  • the new pawn position--

  • and that gives me, now, the hash for the new table

  • with the pawn in that position.

  • So any move that I make, I can basically

  • update my hash function with only two XORs.

  • And XORs are very fast.

  • They're one instruction.

  • And they can do lots of XORs and stuff.

  • So this is actually a very, very cheap thing to do--

  • a very cheap thing.

  • So that Zobrist hashing, that you can keep these things up

  • to date.

  • And that's something we implemented for you.

  • That's an optimization that was a freebie.

  • We could have given you the hash function like this

  • and had you implement that, but this

  • is one of the ones we gave you as a freebie for optimization.

  • You're not all saying, thank you very much, Professor Leiserson?

  • [LAUGHTER]

  • No, in some sense I took away an opportunity for optimization,

  • didn't I, there?

  • And so in the transposition table,

  • there are records for the Zobrist key, the score,

  • the move, the quality, also a bound type,

  • whether it's upper, lower, or exact.

  • Because when I return something from alpha-beta,

  • I only know a bound on it, if it's greater than alpha or less

  • than beta.

  • And in some sense, the age of how old is this move.

  • Because as things get older, I also

  • want to age them out of the table.

  • There are several aging things there.

  • And you'll see the best move table also has

  • an aging process, whereas every time it updates the values

  • and gives a new value, it ages all the other values

  • so that they gradually disappear and aren't relevant.

  • One of the ones that people get confused about

  • is the Late Move Reductions--

  • so-called LMR.

  • This is the situation where I'm going to do, let's say,

  • my parallel search of all my moves.

  • And the question is--

  • once again, you're trying to prune everything you can.

  • And so the idea is, which are the moves that are more

  • important to search deeper?

  • The ones near the beginning of your move list,

  • if it's sorted in best-first order?

  • Or the ones towards the end of your move list?

  • So where is it most important to search deeply?

  • For things that you think are possibly

  • the best move or the ones that you think are the worst moves?

  • Yeah.

  • AUDIENCE: Search for the best move.

  • CHARLES E. LEISERSON: Yeah, it makes sense

  • to search the best moves, right?

  • So the idea is, well, if something

  • is way down on the move ordering list, why search it as deeply?

  • It's probably not as good a move.

  • And so, let me search it more shallowly?

  • I probably don't lose much of an opportunity

  • to discover that that's actually is indeed a bad move.

  • There's a reason that got it ordered down there.

  • And so that's a late move reduction.

  • So with a good move ordering, a beta cutoff

  • will either occur right away or not at all.

  • So you search the first few moves normally,

  • and then you start reducing the depth for moves.

  • I believe, in our code, we have two numbers where

  • we reduce by depth 1 after a certain number of moves

  • and reduce by depth 2 after a certain number of other moves.

  • Those are things that you can tune.

  • I wouldn't tune them very much.

  • I don't think.

  • And once again, I could probably be wrong here,

  • and someone will discover, oh, if you tune it like this,

  • it's way better.

  • But that's the idea of the late move reductions.

  • Probably one of the most important things to think about

  • is the representation of the board.

  • Right now, we represent the board as it is.

  • That's a terrible representation.

  • It's very time-consuming.

  • There's sort of two major ways you can do it.

  • Oh, I didn't put the other one here.

  • Well, anyway, one of them is bitboards.

  • Here, you use a 64-bit to represent, for example,

  • where all the pawns are on the 64 squares of the board.

  • And then you can use POPCOUNT and other bit tricks

  • to do move generation and to implement other chess concepts.

  • So if you're looking to see what are

  • the possible places a pawn can move, and you want to say,

  • can they move right?

  • And let's say it's stored in row major order,

  • you can just do a right shift by 1,

  • and that tells you where all the places

  • that those pawns could move.

  • And now, you can just pick them off one bit

  • at a time to generate your move list.

  • And then you can do it that way.

  • If you're going to move up a thing,

  • well, then you're actually doing a shift by or down.

  • You're doing shift by how much?

  • By eight, to move up or down, if you're

  • storing things in row major.

  • That makes sense, right?

  • So if it's 8 by 8, and you're keeping a bit for each thing,

  • then if I want to generate where is this one?

  • If I shift this whole thing stored in row major order

  • by 8, if I shift it right, it basically puts it there.

  • So I'm moving by 7, 8, and 9, that gives you--

  • and then shifting it by 1 or minus 1

  • gives you this, or left by 1.

  • And then, similarly, you can do by shifting

  • by 7, 8, or 9 that way.

  • And I can generate all the possible moves.

  • So that's one way of doing move generation is using bitboard.

  • And there are a lot of things, for example, that you can

  • do with bitboards in parallel.

  • Because you can say, did I make a capture here?

  • Or let me use a bitboard to represent where the laser goes.

  • Did I make a move that is going to affect the path of laser?

  • Because one of the major optimizations

  • you can do is in the evaluations in dealing with the laser.

  • Because you're spending a lot of time

  • stroking out laser positions.

  • What's the point of doing that--

  • if you made a move of something and it

  • didn't affect where the laser goes why bother doing it out?

  • You can just cache what the value of the laser is.

  • And there are a lot more good stuff on the chess programming

  • wiki.

  • So, yeah, question?

  • AUDIENCE: How do you [INAUDIBLE] a right shift when

  • the [INAUDIBLE] if the shift by 8,

  • and it's clear when it falls off [INAUDIBLE]..

  • CHARLES E. LEISERSON: Yeah.

  • You got be careful there, right?

  • Because if I do a shift to the right,

  • for example, what'll I do?

  • I'll just do a mask to eliminate all the things that

  • got wrapped around.

  • So two instructions or whatever.

  • Yeah, details.

  • Yes.

  • Details are good though.

  • Good question.

  • Good question.

  • Whose timed their program?

  • Where are the opportunities that you

  • see for performance engineering for a first pass?

  • What are the expensive things?

  • What do you have as an expensive thing?

  • AUDIENCE: Add laser paths--

  • [INAUDIBLE]

  • CHARLES E. LEISERSON: Sorry the?

  • AUDIENCE: Marking the laser path.

  • CHARLES E. LEISERSON: Marking laser path, yep.

  • Good.

  • What else is time expensive?

  • AUDIENCE: Laser coverage.

  • [INAUDIBLE]

  • CHARLES E. LEISERSON: Yeah, laser coverage.

  • Boy, that is really expensive.

  • That is really expensive.

  • So where else is expensive?

  • What else is expensive?

  • So I would definitely go after l cover.

  • That's a huge one to go after.

  • One of the things, by the way, if you are making your changes

  • to the code and you're going to change the representation,

  • leave the old representation there.

  • Take it out at the end.

  • Add the new representation and put

  • in assertions that say that things are equivalent

  • or whatever.

  • But don't get rid of the old stuff,

  • because you'll end up with broken code.

  • And definitely, used things like perft

  • to tell you whether or not you made any change If you touch

  • anything with move generation.

  • So where else is expensive?

  • Yeah.

  • AUDIENCE: Can you explain the laser [INAUDIBLE]??

  • CHARLES E. LEISERSON: Sure.

  • How much detail do you want?

  • How it actually works?

  • AUDIENCE: [INAUDIBLE]

  • CHARLES E. LEISERSON: OK.

  • So what is supposed to do is figure out how safe--

  • the idea is, I want my laser to get closer to your king,

  • and I want your laser not to be close to my king.

  • And if I can move into positions where

  • my laser is closer to your king but your laser doesn't

  • get closer to my King, that's a good sort of thing.

  • But when we say get the laser close, what

  • happens when I've got, say--

  • let me do it this way--

  • a position like this.

  • So here's the--

  • OK.

  • Suppose I look at this position.

  • How close does the laser get?

  • Let's say I'm black here, and I look at the laser.

  • Well, the path of laser is it bounces there and goes across.

  • So I didn't get very close to the king there,

  • but I'm one move away from getting it pretty close.

  • Because if I just move this guy out of the way,

  • now I've got it really quite close.

  • So if I compare that to, let's say, a situation

  • where instead of the pawns are there,

  • let's say a pawn is here.

  • Now, the laser is actually closer to the King

  • than it was in the first position,

  • but it's a much worse position.

  • The first one was much better when

  • I had the pawns here and here, because I was simply

  • one move away from getting it really close.

  • And so if you use just the direct laser thing--

  • and we did some tests on this--

  • this turns out to be not very--

  • it doesn't guide the program very well

  • on getting into situations where my laser is

  • getting close to your king.

  • Does that make sense?

  • So then we said, well, how should we

  • measure how close the laser gets?

  • So what we said is, well, let's take a look

  • at all the possible moves from here of one move

  • and then look to see how close we get things.

  • And the way we did that is we said--

  • actually, Helen and I worked on this really hard,

  • because this is a new heuristic that we have not

  • used in previous years.

  • And it works great, it's just slow as anything.

  • But it works well, so you have to evaluate,

  • is it worth doing something if it's really slow?

  • It may be that you'd do better to use a simpler heuristic

  • and get deeper search than it is spending

  • a lot of time evaluating.

  • But anyway, we gave you one, that if you can make it

  • go fast, should be really good.

  • So the idea is that what we do is

  • we look at all the different paths from moving any one piece

  • and look at the paths of the laser.

  • And what we do is we go we count 1 for every position

  • that we go away--

  • 2, 3, 4, 5, 6, 7, et cetera.

  • We actually add an extra value if we bounce off

  • an opponent's--

  • how much do we add, Helen, do we add 1 or 2 if we bounce off

  • an opponent?

  • AUDIENCE: 2.

  • CHARLES E. LEISERSON: I think, 2.

  • Yeah.

  • So if this is an opponent's pawn,

  • we would basically go from 3 to 5, 6, 7, 8, 9.

  • And we basically do that for all the moves.

  • And the way we combine them is we

  • take the minimum number that I can get there.

  • What's the what's the cheapest way I can get to every square

  • that the laser goes?

  • So we take all the different moves, we stroke them out,

  • and we take the minimum.

  • So if I have another path, let's say

  • by turning the king it will go this way,

  • and there's a you know there's another one here

  • that's my pawn, then I may get there in 1, 2, 3, 4, 5, 6 7.

  • And so then this would become a value of 7 here.

  • so that's the first thing is we basically get

  • a map of how close are things.

  • And the second thing we do is say, well,

  • how valuable is it to have these to be near the particular king?

  • And then what we ended up with is something where

  • if I look at the distance that I am away--

  • let's say, this one, for example, is one row

  • and one column away, this is 0 row 0 column--

  • we use, I think, it's 1 over the row plus 1,

  • times 1 over the column plus 1, as a multiplier

  • to weight how good it is that we've been close to the king.

  • And we invert these values so that it's better

  • to have a smaller number there, and then we add them up.

  • We don't quite add them up.

  • No, I'm sorry.

  • What we do is we look at these things

  • as a fraction of my shortest path distance.

  • Sorry, that's what we did.

  • Yes, I'm sorry.

  • That was a previous heuristic.

  • So here, for example-- let's say this is the 9--

  • the shortest way of getting there is 1, 2, 3 4, 5, 6 7, 8.

  • So this would actually, when we do the conversion,

  • would give a value of 8/9 for being in that square.

  • So we didn't get it.

  • Whereas this one, the shortest path distance

  • is 7 because of this path, and you can get there in 7.

  • This would have a value of 1.

  • So this is better.

  • And so we do that for all the squares.

  • So we get a fraction of how much do we do.

  • And then we wait it by something like this,

  • which falls away quickly.

  • But it's important, in heuristics like this,

  • to have a smooth path, so that you can get things closer.

  • If I made all these things be 0, it

  • wouldn't know that it could move up and get a little bit better

  • in the second or third order digit to get closer.

  • And so then we add it all up, and that

  • ends up being a number, we discovered,

  • that's sort of in the range of--

  • what did we figure the range was there?

  • It was up to like 4, or so, right?

  • Something like 4 would be the maximum value it would be.

  • And then we said, OK, then we have

  • this magic constant multiplier that you can play with,

  • that says, OK, let's represent that as a fraction of a pawn.

  • How much is that worth?

  • And we multiplied by that value.

  • So that's what we're doing.

  • So that it makes it so that we do

  • tend to move our laser closer, we

  • subtract how close the opponent can get from us,

  • and then we say that's the evaluation.

  • Now, if you have a better way of determining whether a laser is

  • getting close than this one, that's cheaper to compute,

  • that's good.

  • For first pass, I would just simply try

  • to make this go fast.

  • Because for many of the moves that you're going to look at,

  • it's going to be moving this pawn to there.

  • Nothing changed.

  • There's no point in stroking this out, and calculating

  • all the minimum, et cetera, because it

  • didn't touch the laser path.

  • Things that are going to touch a laser path

  • are things that you move on or off the path.

  • So why bother?

  • And so if there's a clever way of caching it so that you

  • can do things, that's good too.

  • Any questions about other things that could be done?

  • So another place, I'll tell you, that's a good idea to look at

  • is--

  • especially once you get this heuristic top rate a little bit

  • faster--

  • is the sorting of moves is actually pretty expensive.

  • Once you figure out, here all the moves--

  • there are a lot of moves--

  • now you go through and you do a sort.

  • And if you think about it, in a best move order tree, sometimes

  • you only explore one of those.

  • So why'd you bother sorting all of them?

  • On the other hand, sometimes you do need to sort all of them.

  • So how you optimize that sort so that you

  • don't waste time sorting stuff that you're not

  • going to actually ever explore, that's

  • another opportunity for optimization.

  • Yeah, question?

  • AUDIENCE: How do you sort the moves [INAUDIBLE]??

  • CHARLES E. LEISERSON: The moves are sorted by these things

  • like--

  • there's a sort key in there that represents

  • a whole bunch of things, like whether it was a killer.

  • If it's a killer or it's a transposition table value,

  • it's a very big value.

  • If it's a statistical thing that the history table says,

  • historically, this has been a pretty good move,

  • then you get another value.

  • And then exchanges get ordered and so forth.

  • So there's a bunch of things that

  • are where you end up with information,

  • and then it sorts those things.

  • So that's actually kind of complicated logic

  • in terms of what the actual values that are used there.

  • But the idea is, here all the moves, now

  • let's figure out what's our best guess as to what they are.

  • Most of the good moves are coming out

  • of the transposition table.

  • But sometimes, the transition table it says it's

  • not a very good move, and there may be a better move.

  • So the quality of what you get out of transposition table

  • is good, but that doesn't mean that that's always

  • the best move.

  • AUDIENCE: [INAUDIBLE]

  • CHARLES E. LEISERSON: Yeah.

  • Any other questions about what should be worked on?

  • Let me just make sure I--

  • OK, go ahead.

  • AUDIENCE: Where does that sorting happen?

  • I've never [INAUDIBLE].

  • CHARLES E. LEISERSON: Where does the sorting happen?

  • That happens, I think, at the move generation.

  • Is that where it is?

  • Is it stored in the move generation?

  • AUDIENCE: In search.

  • CHARLES E. LEISERSON: Or is it in search?

  • I think it's in search.

  • I think you're right.

  • Search calls move generation and then sorts it.

  • I think that's right.

  • Yeah, question?

  • AUDIENCE: So one of the things we

  • did that we were providing [INAUDIBLE],,

  • we have a very tiny board implementation.

  • CHARLES E. LEISERSON: A very tiny board implementation.

  • AUDIENCE: Yeah, [INAUDIBLE].

  • You can do a lot of matrix on it as well.

  • But it's like maybe [INAUDIBLE] replace it everywhere.

  • CHARLES E. LEISERSON: Yes.

  • AUDIENCE: So what's a good strategy?

  • CHARLES E. LEISERSON: Well, as I say, keep the old one around.

  • AUDIENCE: [INAUDIBLE] still use [INAUDIBLE]..

  • CHARLES E. LEISERSON: Well, you use the old one

  • while you're still getting the new one right.

  • It's also good to be able to go from old representation

  • to new representation and having conversion functions.

  • But, yeah, making representation changes, painful, painful.

  • And boy, if there was one tool I would

  • love that would automate stuff like that, that would be it,

  • to be able to change representations of things

  • and still have things go well.

  • I should have mentioned, by the way,

  • the other representation besides bitboard.

  • Another one is just to keep a list of the pieces

  • and their positions.

  • Because that's going to be smaller than keeping

  • this great big board.

  • And do you keep this list sorted or do you not keep it sorted?

  • But the advantage of that is, particularly

  • as the game goes on, that list gets shorter and shorter.

  • And so if you're doing less in manipulating the board

  • position, that's generally a good thing.

  • AUDIENCE: So for the board reputation,

  • my recommendation is to refactor all the board

  • axes into a function.

  • And then you would still use the old representation

  • in the function.

  • Then you can validate that you refactor everything correctly.

  • And then you can easily change the board representation

  • to whatever you want and keep changing it

  • without having to do it a lot of refactor after that.

  • So find all the board axes and refactor that to a function

  • call before you modify it.

  • CHARLES E. LEISERSON: Yeah.

  • Because the compiler will inline that stuff.

  • So putting in a function call is not necessarily a bad idea.

  • And if it doesn't, you can put it in macro,

  • and it'll be effectively the same thing.

  • So great idea.

  • Great idea.

  • Yeah, question?

  • AUDIENCE: Anything else that wasn't

  • there that you would highly recommend for us to look at?

  • CHARLES E. LEISERSON: Testing, testing, testing.

  • If you can test and know that when you make a change

  • it's correct and that you're not--

  • that's probably the number one hole that people go into

  • is they don't test adequately.

  • So having good test infrastructure is good.

  • Yeah?

  • AUDIENCE: Some questions about codes counts--

  • I saw on Piazza there was [INAUDIBLE]

  • if the beta changed the [INAUDIBLE] count will

  • stay the same.

  • CHARLES E. LEISERSON: As long as you're

  • doing it deterministically, yes?

  • AUDIENCE: Yeah.

  • But even the references limitation

  • is nondeterministic serially for [INAUDIBLE]..

  • CHARLES E. LEISERSON: That's because there's

  • a randomness thing.

  • There's a little variable, and you can set the variable

  • to be not random.

  • And then it will be.

  • AUDIENCE: Is that a part of the set option RNG?

  • CHARLES E. LEISERSON: Yes.

  • AUDIENCE: When that's set, it's still nondeterministic.

  • CHARLES E. LEISERSON: Run serially?

  • AUDIENCE: Yeah.

  • I checked the-- is there anything else that

  • should be done?

  • Or should it just be that seed option?

  • CHARLES E. LEISERSON: I think that's--

  • AUDIENCE: [INAUDIBLE]

  • CHARLES E. LEISERSON: [INAUDIBLE],,

  • can give to her the mic?

  • AUDIENCE: Yeah.

  • AUDIENCE: [INAUDIBLE].

  • Yeah.

  • Did you try the things that [INAUDIBLE] include

  • [INAUDIBLE] like [INAUDIBLE].

  • AUDIENCE: Yeah.

  • I got out of the opening book and I set the RNG option.

  • AUDIENCE: OK Let me test it again.

  • Because when I tested it , it was deterministic.

  • So [INAUDIBLE].

  • AUDIENCE: OK.

  • AUDIENCE: [INAUDIBLE]

  • CHARLES E. LEISERSON: Yeah.

  • It shouldn't be-- if you run serially,

  • the only things that should be doing things is

  • if you're doing--

  • it should be deterministic if you turn off the random number

  • generator.

  • So as I say, that's put in so that it

  • will behave nonpredictably.

  • But that's exactly the kind of thing

  • you want to find right at the beginning.

  • So that's exactly the thing is find out

  • all the ways of making it deterministic,

  • and that would be really important for beta 2.

  • So Thursday, we have Jon Bentley, legend of the field,

  • opportunity to meet a celebrity.

  • Bring friends.

  • He's going to give a great lecture.

The following content is provided under a Creative

字幕與單字

單字即點即查 點擊單字可以查詢單字解釋

B1 中級

20.投機平行主義與萊澤爾切斯法 (20. Speculative Parallelism & Leiserchess)

  • 6 0
    林宜悉 發佈於 2021 年 01 月 14 日
影片單字