Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
Hi, everyone. Welcome to the seventh lecture of CS 188 for the semester. Let's start with a couple of logistics.
Chào các bạn. Chào mừng đến với bài giảng thứ bảy của CS 188 trong học kỳ này. Trước hết là vài thông báo.
Homework three, games, has been released. It will due on Monday, this coming Monday. And just also a reminder that every homework has three parts that are due.
Bài tập về nhà số ba, về trò chơi, đã được đăng. Hạn nộp là thứ Hai, thứ Hai tuần này. Xin nhắc lại là mỗi bài tập về nhà có ba phần phải nộp.
There is the electronic homework, there is the written part, and then there is the self-assessment of the previous homework. For the written, for the self-assessment, make sure to use the templates that we provide.
Có phần bài tập điện tử, có phần viết, và có phần tự đánh giá bài tập trước. Với phần viết và phần tự đánh giá, nhớ dùng mẫu mà chúng tôi cung cấp.
Any questions about that? Yes.
Có câu hỏi nào về phần này không? Mời bạn.
STUDENT
You can still annotate [INAUDIBLE].. Yeah, for the self-assessment, you can go into Grade Scope, download the PDF that you submitted, and annotate onto that.
Em vẫn có thể chú thích [KHÔNG NGHE RÕ]. Vâng, với phần tự đánh giá, các bạn vào Grade Scope, tải file PDF mà các bạn đã nộp, rồi chú thích trực tiếp lên đó.
If you happen to not submit anything, you can grab the empty templates and annotate that with the differences between what you had, which would be empty if you had empty, and annotated with everything we have to show the differences.
Nếu bạn lỡ không nộp gì cả, bạn có thể lấy mẫu trống và chú thích những điểm khác nhau giữa bài của bạn là bài trống nếu bạn để trống, và chú thích mọi thứ chúng tôi có để thấy sự khác biệt.
[INAUDIBLE] You can annotate it electronically or you can annotate it on a printout and then rescan or take pictures, but we wanted to use the template format, whether you do it by writing or by directly electronically.
[KHÔNG NGHE RÕ] Các bạn có thể chú thích bằng máy hoặc chú thích trên bản in rồi quét lại hoặc chụp ảnh, nhưng chúng tôi muốn dùng định dạng của mẫu, dù bạn viết tay hay làm trực tiếp trên máy.
Project 2 games is out. In project 2, you get to program minimax alpha beta evaluation functions, expectimax, which we'll see today, for Pac-Man to play against ghosts.
Project 2 về trò chơi đã ra. Trong project 2, các bạn lập trình minimax, cắt tỉa alpha-beta, hàm đánh giá, expectimax, mà hôm nay ta sẽ học, để Pac-Man chơi với các con ma.
This will be due next week Friday at 4 PM. Also there's an update to the homework policy. We already posted this on Piazza, but I don't think we've said it in lecture yet.
Hạn nộp là 4 giờ chiều thứ Sáu tuần sau. Ngoài ra có cập nhật về chính sách bài tập về nhà. Chúng tôi đã đăng trên Piazza, nhưng tôi nghĩ chưa nói trên lớp.
There's 11 homeworks total, which is more than usual. We also have three parts through each homework, which is more than we've done in the past.
Tổng cộng có 11 bài tập về nhà, nhiều hơn thường lệ. Mỗi bài còn có ba phần, nhiều hơn so với các năm trước.
So we've concluded it makes sense to let you drop the two lowest scoring homeworks.
Vì vậy chúng tôi thấy hợp lý khi cho phép các bạn bỏ hai bài điểm thấp nhất.
So at the end of the semester, we'll automatically look at every subset of 9 homeworks and see which one gives you the highest score and use that one to compute your homework grade.
Cuối học kỳ, chúng tôi sẽ tự động xét mọi tập con gồm 9 bài tập và xem tập nào cho điểm cao nhất rồi dùng tập đó để tính điểm bài tập về nhà của bạn.
You can independently drop written versus electronic versus self-assessment up to two of each. You don't have to drop them.
Các bạn bỏ riêng được phần viết, phần điện tử và phần tự đánh giá, mỗi loại tối đa hai bài. Các bạn không bắt buộc phải bỏ.
You can just also do them all, but our calculation will then still just try to grab the nine highest scoring ones and give you a grade based on the nine highest score ones for each separately.
Các bạn cứ làm hết cũng được, nhưng cách tính của chúng tôi vẫn sẽ lấy chín bài điểm cao nhất và tính điểm dựa trên chín bài cao nhất đó cho từng loại riêng.
Any questions about that? Yes. [INAUDIBLE] Say that again.
Có câu hỏi nào không? Mời bạn. [KHÔNG NGHE RÕ] Bạn nói lại giúp tôi.
The written homework is graded based on whether you completed it.
Phần viết được chấm dựa trên việc bạn có hoàn thành hay không.
Our mindset here is that, with the written, we want to work on it as if it were an exam let's say, give yourself a feeling of where you would be out if it were an exam, then after that maybe talk with some other students, and write up after that your full understanding of everything.
Ý của chúng tôi là với phần viết, hãy làm như thể đang thi, để tự cảm nhận mình đang ở mức nào nếu đây là bài thi, rồi sau đó có thể trao đổi với các bạn khác, và sau đó viết lại hiểu biết đầy đủ của mình về mọi thứ.
If it looks like you've completed everything, as you would do in an exam, then you will get a complete grade on the written, whether it's accurately solved or not accurately solved.
Nếu trông như bạn đã làm hết mọi phần, như khi làm bài thi, thì bạn sẽ được điểm tối đa cho phần viết, dù giải đúng hay không đúng.
The self-assessment, similarly, you will assess what the difference is between your answer and our answer, but our assessment of your self-assessment is based on whether your self-assessment is accurate, not based on whether your self-assessment gives you a 0 or a five or a 10.
Phần tự đánh giá cũng tương tự: bạn sẽ đánh giá sự khác biệt giữa đáp án của bạn và đáp án của chúng tôi, nhưng chúng tôi chấm phần tự đánh giá của bạn dựa trên việc nó có chính xác hay không, chứ không dựa trên việc bạn tự cho mình 0, năm hay 10 điểm.
[INAUDIBLE] Sorry, I couldn't hear that very well. [INAUDIBLE] What do you mean with the lowest scores?
[KHÔNG NGHE RÕ] Xin lỗi, tôi nghe không rõ lắm. [KHÔNG NGHE RÕ] Ý bạn về điểm thấp nhất là gì?
[INAUDIBLE] So what will happen is that, at the end of the semester, they will have been 11 homeworks.
[KHÔNG NGHE RÕ] Vậy thế này, cuối học kỳ sẽ có 11 bài tập về nhà.
And for each one of you, we will look at your 11 electronic homeworks, see which nine out of 11 have the highest score among your 11, and those nine will constitute your electronic homework score.
Với mỗi bạn, chúng tôi sẽ xem 11 bài điện tử của bạn, xem chín bài nào trong 11 bài có điểm cao nhất, và chín bài đó sẽ là điểm bài điện tử của bạn.
Then we'll look around your 11 written homeworks.
Sau đó chúng tôi xem 11 bài viết của bạn.
We'll look at the nine out of 11 that have the highest score, use those as your written homework score, and then we'll look at your 11 self-assessments.
Chúng tôi lấy chín bài trong 11 bài có điểm cao nhất làm điểm phần viết, rồi xem 11 bài tự đánh giá của bạn.
And we'll see which nine out of 11 have the highest score there and use that as your self-assessment score.
Chúng tôi xem chín bài nào có điểm cao nhất và dùng làm điểm tự đánh giá.
Any other questions about that?
Còn câu hỏi nào khác không?
Mini contest one is ongoing. It's optional. It's a lot of fun though. It ends on Sunday.
Mini contest một đang diễn ra. Cuộc thi này là tùy chọn. Nhưng rất vui. Cuộc thi kết thúc vào Chủ nhật.
Let's take a look at the leaderboard at this point. So this is what the contest looks like. You'll have massive mazes compared to the ones you've done in the regular project.
Giờ ta xem bảng xếp hạng hiện tại. Cuộc thi trông như thế này. Các mê cung rất lớn so với những mê cung các bạn làm trong project thông thường.
You'll have multiple Pac-man agents that work together to clear the board, and you'll be time constrained or, better phrased, time penalized.
Có nhiều tác tử Pac-Man phối hợp với nhau để dọn sạch bàn chơi, và các bạn bị giới hạn thời gian, hay đúng hơn là bị trừ điểm theo thời gian.
The more time you spend thinking about what to do, the lower your score will be. Let's take a look at the current leaderboard. At number one we have currently Otto.
Càng mất nhiều thời gian suy nghĩ phải làm gì, điểm của bạn càng thấp. Ta xem bảng xếp hạng hiện tại. Hạng nhất hiện là Otto.
Is Otto here? Over there. Great. At number two, we have Jason Lee.
Otto có ở đây không? Ở đằng kia. Tuyệt. Hạng hai là Jason Lee.
Here, great. And number three, we have Yoon Shan, Yoon Shan here. Yoon Shan.
Có mặt, tuyệt. Hạng ba là Yoon Shan, Yoon Shan có ở đây không? Yoon Shan.
I think Yoon Shan wasn't here last time either, but Yoon Shan has a good entry in the contest. And at this highest point there was I believe about 140 teams on the leaderboard.
Tôi nghĩ lần trước Yoon Shan cũng không có mặt, nhưng Yoon Shan có bài dự thi rất tốt. Và ở điểm cao nhất này thì có Tôi tin là có khoảng 140 đội trên bảng xếp hạng.
Some teams have one student behind it. Some teams have two student behind it.
Có đội chỉ có một sinh viên. Có đội có hai sinh viên.
Also some fun names starting to emerge — too greedy, muh, team no sleep, don't recommend that, a name for the leader board when you're just too tired to come up with something, Joe Mama, Kiwigot,
Cũng bắt đầu xuất hiện vài cái tên vui nhộn — too greedy, muh, team no sleep, không khuyên dùng đâu, một cái tên cho bảng xếp hạng khi bạn mệt quá không nghĩ ra gì, Joe Mama, Kiwigot,
just got some food delivered, should have tried harder, and many more. We'll take another look next time.
just got some food delivered, should have tried harder, và nhiều tên khác nữa. Lần sau chúng ta sẽ xem lại.
So this will end on Sunday, and then next week we'll report out on the results of the final ranking and also on the strategies used by some of the top teams.
Cuộc thi kết thúc vào Chủ nhật, và tuần sau chúng ta sẽ công bố kết quả xếp hạng cuối cùng và cả các chiến lược của một số đội dẫn đầu.
Any questions about the mini contest?
Có câu hỏi nào về cuộc thi nhỏ không?
Let's start with the technical content for today then.
Vậy hôm nay ta bắt đầu phần kiến thức chính.
Today we're going to look at decision making when there is uncertainty, and we'll also start looking at what these utilities really are that we've been optimizing all along since lecture 1.
Hôm nay ta sẽ xem xét việc ra quyết định khi có sự bất định, và ta cũng sẽ bắt đầu tìm hiểu độ hữu dụng thực sự là gì, thứ mà ta vẫn luôn tối ưu từ bài giảng 1.
So we'll now have uncertain outcomes. Remember this game tree from last time where we had maximizer player at the top gets to choose between two actions, then the minimizer gets to choose.
Giờ ta sẽ có các kết quả không chắc chắn. Nhớ cây trò chơi lần trước, trong đó người chơi maximizer ở trên cùng được chọn giữa hai hành động, rồi đến lượt minimizer chọn.
And we see a 10 and a 10 on the left, a nine and 100 on the right. If we run minimax, what do we end up with?
Ta thấy 10 và 10 bên trái, 9 và 100 bên phải. Nếu chạy minimax thì ta được gì?
Well, minimax, we'll say this would be 10, this would be 9. So we should go this way.
Theo minimax, nhánh này là 10, nhánh này là 9. Nên ta đi hướng này.
And that's what you want to use if you play against a true minimax player that really optimizes, in this case, against you.
Và đó là điều bạn nên dùng nếu chơi với một đối thủ minimax thật sự, luôn tối ưu chống lại bạn, trong trường hợp này.
You want to take no chances because they're going to stick you with a nine on the other side.
Bạn không mạo hiểm vì họ sẽ khiến bạn chỉ được 9 ở nhánh kia.
But we also alluded to it what if you play against, let's say, an agent like this one. Maybe if the agent looks like that, you say I'm willing to take my chances.
Nhưng ta cũng đã nhắc tới: nếu bạn chơi với, giả sử, một tác tử như thế này thì sao. Có thể nếu tác tử trông như vậy, bạn nói tôi sẵn sàng liều.
There is a possibility that they don't play the optimal thing for them and that would give me 100. And a nine is not that much worse than a 10.
Có khả năng họ không chơi nước tối ưu cho họ và tôi sẽ được 100. Mà 9 cũng không tệ hơn 10 bao nhiêu.
So I'm just going to go for it. But I was pretty informal. And the question today becomes, how do we formalize something like this.
Nên tôi cứ thử. Nhưng đó là cách nói khá không chính thức. Và câu hỏi hôm nay là làm sao hình thức hóa điều này.
It could be an agent that looks like that, and you say I'm willing to take my chances. It could also be that there is inherent stochasticity.
Có thể là một tác tử trông như vậy, và bạn nói tôi sẵn sàng liều. Cũng có thể vốn có tính ngẫu nhiên.
Somebody is going to be rolling dice, and based on the outcome of the roll of the dice, go left or right in the bottom branch.
Ai đó sẽ tung xúc xắc, và dựa vào kết quả tung xúc xắc, đi trái hoặc phải ở nhánh dưới.
If that's the case — and let's say the chances of the coin flip, chances are 50/50, you could say, well, on average here, I'm going to get 109 divided by 2 — so 54.5.
Nếu vậy — giả sử tung đồng xu với xác suất 50/50, bạn có thể nói, trung bình ở đây tôi được 109 chia 2, tức 54,5.
On average here, I would get 10, and now we have a formal way of justifying going that way because, on average, we'll do better going to the right than going to the left.
Trung bình ở đây tôi được 10, và giờ ta có cách chính thức để biện minh việc đi hướng đó vì trung bình đi bên phải sẽ tốt hơn đi bên trái.
When we do this kind of calculation, we'll have a different scheme of annotating the nodes. We'll use circles.
Khi tính toán kiểu này, ta dùng một cách ký hiệu nút khác. Ta dùng hình tròn.
So we have up triangles for the maximizers, down triangles for minimizers, and we will have circles for chance nodes.
Tam giác hướng lên cho maximizer, tam giác hướng xuống cho minimizer, và ta sẽ dùng hình tròn cho nút ngẫu nhiên (chance node).
So when we follow this procedure, it's called expectimax search. You might ask yourself the question, why wouldn't we know what the result of an action would be.
Khi làm theo quy trình này, nó gọi là tìm kiếm expectimax. Bạn có thể tự hỏi, tại sao ta lại không biết kết quả của một hành động.
How come there could be a chance node in our model of the world? Well, one possibility is that it's designed that way. Maybe we're playing a game.
Sao mô hình thế giới của ta lại có nút ngẫu nhiên? Một khả năng là nó được thiết kế như vậy. Có thể ta đang chơi một trò chơi.
And as part of the game, there is some dice being rolled, and then it's by design stochastic. Another possibility is that the opponents we are playing with are unpredictable.
Và trò chơi có tung xúc xắc, nên theo thiết kế nó mang tính ngẫu nhiên. Khả năng khác là các đối thủ ta chơi cùng không thể đoán trước.
So we don't know how they're going to act, and maybe we can model them with a probability distribution over possible things they might do.
Ta không biết họ sẽ hành động ra sao, và có thể mô hình họ bằng một phân phối xác suất trên những việc họ có thể làm.
And we think that maybe modeling them with a probability distribution is a better way to model them than to model them as masterminds that work against us.
Và ta nghĩ mô hình họ bằng một phân phối xác suất có thể tốt hơn so với coi họ là những bậc thiên tài luôn chống lại ta.
Another reason it could be — it could be that what does this is modeling here is that, first, you get to choose between two actions.
Một lý do khác là, điều mô hình này thể hiện là, trước hết bạn được chọn giữa hai hành động.
After you choose those actions, those actions don't get executed perfectly. Maybe you're a robot.
Sau khi chọn, các hành động đó không được thực hiện hoàn hảo. Giả sử bạn là một robot.
You want to spin your wheels a bit, and you expect they're going to move forward or backward depending on which action you take.
Bạn muốn quay bánh xe một chút, và bạn kỳ vọng nó tiến lên hoặc lùi lại tùy hành động bạn chọn.
But then the wheels might slip, and you might actually not move forward or might not move backward and instead stay in place.
Nhưng bánh xe có thể trượt, và thực tế bạn có thể không tiến hay không lùi mà đứng yên.
And then the chance node here would model the fact that, after you chose your action, the outcome of that action is actually not deterministic.
Và nút ngẫu nhiên ở đây mô hình hóa việc sau khi bạn chọn hành động, kết quả của hành động đó thực ra không xác định.
Now when we're in this stochastic world, our values should reflect the average case, which is the expectimax max value rather than the worst case or minimax outcomes.
Khi ở trong thế giới ngẫu nhiên này, các giá trị của ta nên phản ánh trường hợp trung bình, tức giá trị expectimax, thay vì trường hợp xấu nhất hay kết quả minimax.
When we run expectimax search, we will compute the average score under optimal play. So optimal play here means that you maximize what you get on average. What does that mean?
Khi chạy tìm kiếm expectimax, ta tính điểm trung bình khi chơi tối ưu. Chơi tối ưu ở đây nghĩa là bạn tối đa hóa điều bạn nhận được trung bình. Điều đó nghĩa là gì?
In a game like this one here, you would still, if you choose the right branch, always either get nine or 100. You would never get the 54.5. That's never an outcome of the game.
Trong trò chơi như ở đây, nếu chọn nhánh phải, bạn vẫn luôn nhận được hoặc 9 hoặc 100. Bạn sẽ không bao giờ được 54,5. Đó không bao giờ là kết quả của trò chơi.
But what we're saying is, if you were to play this game many, many, many times and you'd take the right action and it's really 50/50 there, then, on average, you will get 54.5.
Nhưng ý ta là, nếu chơi trò này rất, rất nhiều lần và chọn đúng hành động, mà ở đó đúng là 50/50, thì trung bình bạn sẽ được 54,5.
Hence, we call the value of the top node the expectimax value of 54.5 even if never we are experience that specific value in any single outcome of the game.
Do đó ta gọi giá trị của nút trên cùng là giá trị expectimax 54,5 dù ta không bao giờ gặp đúng giá trị đó trong bất kỳ ván chơi đơn lẻ nào.
How does the algorithm work? Well, the max nodes are just like in minimax search. Nothing different has to happen. Chance nodes are like the mid nodes.
Vậy thuật toán hoạt động thế nào? Các nút max thì giống hệt như trong tìm kiếm minimax. Không có gì khác cả. Các nút chance thì giống các nút min.
They are opponents in some sense, but they're not working against us. It's just a stochastic.
Theo một nghĩa nào đó chúng là đối thủ, nhưng chúng không chống lại chúng ta. Chỉ là tính ngẫu nhiên thôi.
And so rather than saying, in a chance node we take to the min like we did for minimizers, in a chance node we say let's take some weighted average based on how likely each outcome is.
Vì vậy, thay vì nói ở nút chance ta lấy giá trị nhỏ nhất như đã làm với các nút min, ở nút chance ta lấy trung bình có trọng số dựa trên khả năng xảy ra của từng kết quả.
Those are called expectations, the weighted average of the outcomes.
Đó gọi là kỳ vọng, tức trung bình có trọng số của các kết quả.
Later, we'll actually see another formalism that's very related to this that's going to start next week called Markov decision processes, which is another way to think about expectimax problems.
Sau này ta sẽ thấy một hình thức khác rất liên quan, bắt đầu từ tuần sau, gọi là quá trình quyết định Markov (MDP), một cách khác để nghĩ về các bài toán expectimax.
Actually let's run some demos illustrating what we're doing here. So as typical in the lectures, there's two big parts to how we think about problems.
Giờ ta chạy vài bản demo minh họa những gì đang làm ở đây. Như thường lệ trong các bài giảng, có hai phần lớn khi ta suy nghĩ về bài toán.
We have the world. We want to turn it into some model that we use of the world.
Ta có thế giới thực. Ta muốn biến nó thành một mô hình về thế giới.
And then we have an algorithm that works on the model and finds a solution based on that model.
Rồi ta có một thuật toán chạy trên mô hình và tìm ra lời giải dựa trên mô hình đó.
And so you can ask the question, OK, what does it mean to model the world in a very specific way.
Và bạn có thể hỏi, mô hình hóa thế giới theo một cách cụ thể nghĩa là gì?
For example, let's model the world — let's go back to a situation we had last time over here — fairly grim world again for Pac-Man, flanked by two ghosts.
Ví dụ, hãy mô hình hóa thế giới... quay lại tình huống lần trước ở đây... lại là một thế giới khá ảm đạm cho Pac-Man, bị hai con ma kẹp hai bên.
We now have a choice on how to model the situation. We could say we're going to model it as ghost that work directly against us. That would be minimax.
Giờ ta có lựa chọn về cách mô hình hóa tình huống này. Ta có thể mô hình hóa chúng như những con ma trực tiếp chống lại ta. Đó là minimax.
If we model things that way, then we have a minimax tree — murderous Pac-Man, then each of their ghosts, then Pac-Man, each of that ghosts.
Mô hình hóa như vậy thì ta có cây minimax... Pac-Man tối đa hóa, rồi đến từng con ma, rồi lại Pac-Man, rồi từng con ma.
This repeats, and we have a tree that goes maybe till the end of the game. If we do a minimax search in that tree, what will happen?
Điều này lặp lại, và ta có một cây có thể đi đến tận cuối ván chơi. Nếu tìm kiếm minimax trên cây đó thì chuyện gì xảy ra?
Well, we saw last time because we lose a point for every time step that passes and we again time for food pals.
Lần trước ta đã thấy, vì ta mất một điểm mỗi bước thời gian trôi qua và lại muốn có thời gian ăn thức ăn.
But we're flanked here and we're going to be eaten by the ghosts. We might as well be eaten as quickly as possible.
Nhưng ở đây ta bị kẹp hai bên và sẽ bị ma ăn. Vậy thì thà bị ăn càng nhanh càng tốt.
So we're going to go right on to the red ghost and get eaten as quickly as possible. And that's indeed what minimax, in this case, will give us.
Nên ta sẽ lao thẳng vào con ma đỏ và bị ăn nhanh nhất có thể. Và đúng là minimax trong trường hợp này cho ta kết quả đó.
So minimax in action goes straight to the nearestby ghost, minimize the damage.
Vậy minimax khi chạy sẽ đi thẳng đến con ma gần nhất, giảm thiểu thiệt hại.
What, on the other hand, if we set it up as an expectimax tree. An expectimax, when the ghosts choose, it's a coin flip.
Còn nếu ta thiết lập thành cây expectimax thì sao? Trong expectimax, khi các con ma chọn, đó là tung đồng xu.
In particular for the blue ghost, it's a coin flip whether they'll go up or down, and then they keep going the direction they chose.
Cụ thể với con ma xanh, là tung đồng xu xem nó đi lên hay xuống, rồi nó cứ đi tiếp theo hướng đã chọn.
So if we run expectimax, what do you expect to happen? We say, well, just two possible outcomes. Well, there's many possible outcomes. If we go to the right, only one thing happens.
Nếu chạy expectimax, bạn đoán điều gì sẽ xảy ra? Ta nói, chỉ có hai kết quả có thể. À, thực ra có nhiều kết quả có thể. Nếu đi sang phải, chỉ có một điều xảy ra.
We die instantly. If we go to the left, there is two possible outcomes. Either the ghost is running away or coming to me.
Ta chết ngay lập tức. Nếu đi sang trái, có hai kết quả có thể. Hoặc con ma chạy đi, hoặc lao về phía tôi.
If it's coming to me, then I am in trouble and I really should have dive bombed the red ghost. I would have finished things off earlier and lost less points.
Nếu nó lao về phía tôi thì tôi gặp rắc rối và lẽ ra nên lao thẳng vào con ma đỏ. Như vậy tôi đã kết thúc sớm hơn và mất ít điểm hơn.
That's a bad outcome. But if the blue ghost is running away from me, then I can run behind the blue ghost, eat all the dots, and get high reward.
Đó là kết quả xấu. Nhưng nếu con ma xanh chạy khỏi tôi, thì tôi có thể chạy theo sau nó, ăn hết các chấm, và nhận phần thưởng cao.
So expectimax will then say, OK, if that's a 50/50 thing, we don't need to average the score you get in one case versus the other case of running to the left.
Vậy expectimax sẽ nói, được, nếu là 50/50 thì ta lấy trung bình điểm số nhận được ở trường hợp này và trường hợp kia khi chạy sang trái.
And if the average of that is higher than what you get from running to the right, then you should run to the left.
Và nếu trung bình đó cao hơn điểm khi chạy sang phải, thì bạn nên chạy sang trái.
That doesn't mean, after you decide to run to the left, you're guaranteed to do better than you would have done if you had run to the right. It's a 50/50 chance.
Điều đó không có nghĩa là sau khi quyết định chạy sang trái, bạn chắc chắn sẽ làm tốt hơn so với khi chạy sang phải. Đó là cơ hội 50/50.
And so sometimes you'll do really well. Sometimes you'll actually not do well. It depends on the random seed. Let's see what happens here.
Nên đôi khi bạn sẽ làm rất tốt. Đôi khi bạn lại không tốt. Điều đó phụ thuộc vào random seed. Hãy xem chuyện gì xảy ra ở đây.
Expectimax was run. Pac-Man has decided needs to go left to maximize expected value, but will it be lucky in this run or not? We'll see.
Expectimax đã được chạy. Pac-Man quyết định cần đi sang trái để tối đa hóa giá trị kỳ vọng, nhưng liệu lần chạy này có may mắn không? Ta sẽ xem.
It is lucky in this run, and so it gets a very high score. If we run this again with expectimax, it might be a lucky again or it might be unlucky this time.
Lần này may mắn, nên nó được điểm rất cao. Nếu chạy lại với expectimax, có thể lại may mắn hoặc lần này sẽ xui.
It's unlucky. And it has score that's as negative as it's going to get in this particular game scenario.
Xui rồi. Và điểm của nó âm đến mức thấp nhất có thể trong kịch bản ván chơi này.
But on average, it's doing better than if would have gone off to the right and run into the ghost instantly.
Nhưng trung bình, nó vẫn tốt hơn so với việc đi sang phải và đâm vào con ma ngay lập tức.
One thing that's important to keep in mind here is that we're making assumptions about how these ghosts function.
Một điều quan trọng cần nhớ ở đây là ta đang đưa ra giả định về cách những con ma này hoạt động.
And these assumptions can be mismatched with the world, and we need to be careful about that.
Và những giả định này có thể không khớp với thực tế, nên ta cần cẩn thận về điều đó.
If your run expectimax but the ghost is actually playing against you, then you're very naive and you're going to be taken advantage of.
Nếu bạn chạy expectimax nhưng con ma thực sự chơi chống lại bạn, thì bạn quá ngây thơ và sẽ bị lợi dụng.
On the Other Hand, if you play minimax but the ghost is kind of random, then you're very pessimistic about everything, too cautious, and you don't take advantage of opportunities.
Ngược lại, nếu bạn chơi minimax nhưng con ma lại khá ngẫu nhiên, thì bạn quá bi quan về mọi thứ, quá thận trọng, và không tận dụng được các cơ hội.
And so it's important to understand how the world functions to then decide which model you're going to use.
Vì vậy điều quan trọng là hiểu thế giới vận hành ra sao để rồi quyết định bạn sẽ dùng mô hình nào.
Here's a pseudocode for this looks. It's a lot like the minimax pseudocode we had last time. There was a dispatch node. The dispatch node decides, is this a terminal state or not.
Đây là mã giả của thuật toán này. Nó rất giống mã giả minimax lần trước. Có một nút điều phối. Nút điều phối quyết định: đây có phải trạng thái kết thúc không.
If it is, return the state utility. If it's not, checked is it a max, call max value. Is it an expectinode? Call the x value function.
Nếu phải, trả về độ hữu dụng của trạng thái. Nếu không, kiểm tra xem có phải nút max không, thì gọi max value. Có phải nút expecti không? Thì gọi hàm giá trị kỳ vọng.
This one is the same as before. Then the one on the right, the expectation calculation, is a weighted average.
Hàm này giống như trước. Còn hàm bên phải, phép tính kỳ vọng, là một trung bình có trọng số.
So it loops over all successors, looks at the probability of that successor, and then looks at the value of that successor, multiplies it with the probability of having that successor, and computes the weighted sum of all of them.
Nó lặp qua tất cả các nút con, xem xác suất của nút con đó, rồi xem giá trị của nút con đó, nhân giá trị với xác suất có được nút con đó, và tính tổng có trọng số của tất cả chúng.
So let's take a look at this in action. Here is an x node. We have probabilities that are not equal in this case — one half, one third, one sixth.
Hãy xem nó chạy thế nào. Đây là một nút kỳ vọng. Các xác suất ở đây không bằng nhau: một phần hai, một phần ba, một phần sáu.
So that means we end up with one half a plus 1/3 24 plus 1/6 negative 12, which is C 4 plus 8 minus 2 is 10.
Vậy ta có một nửa nhân 8, cộng 1/3 nhân 24 cộng 1/6 nhân -12, tức là 4 cộng 8 trừ 2 bằng 10.
So we have 10 over here. And again, very different from minimax is that in minimax, whatever ended up over here, corresponded to something we had at the bottom.
Vậy ở đây ta có 10. Và một lần nữa, rất khác với minimax là trong minimax, giá trị nào xuất hiện ở đây cũng tương ứng với một giá trị ở dưới đáy.
Here is no 10 at the bottom. You're never going to have 10. But on average, you expect to score 10 if you land in this node.
Ở đây dưới đáy không có 10. Bạn sẽ không bao giờ nhận được 10. Nhưng trung bình, bạn kỳ vọng được 10 điểm nếu rơi vào nút này.
Let's to another example.
Hãy xem một ví dụ khác.
Maybe let's have you work through this one.
Các bạn thử làm ví dụ này nhé.
I'll give you 30 seconds, talk to your neighbors, and figure out what is the expectimax value, that is, the value of this node over here in this game tree.
Tôi cho 30 giây, hãy trao đổi với bạn bên cạnh, và tìm giá trị expectimax, tức là giá trị của nút này trong cây trò chơi.
Any thoughts on the value of the game here? Anyone?
Ai có ý kiến về giá trị của trò chơi này không? Có ai không?
Suggestion is 8. Anybody have another suggestion?
Đề xuất là 8. Có ai có đáp án khác không?
Everybody thinks 8? Seems right. How will we get it? Well, it wasn't explicit here.
Mọi người đều nghĩ là 8? Có vẻ đúng. Ta tính ra nó thế nào? Ở đây đề không nói rõ.
When it's not explicit, we tend to assume that all probabilities are equal. But then we could sometimes have them not be equal, but we are assuming they're all equal.
Khi không nói rõ, ta thường giả định rằng tất cả xác suất bằng nhau. Đôi khi chúng có thể không bằng nhau, nhưng ở đây ta giả định chúng bằng nhau.
Nothing else has said. We have to an equally average these — three plus 12 plus 9 is 24, divided by 3 is 8.
Không có gì nói khác cả. Ta lấy trung bình đều các giá trị này: 3 cộng 12 cộng 9 là 24, chia 3 được 8.
2, 4, 6 that's 12, divided by 3 is 4. 21 divided by 3 is 7. Then we have a max node on top of that.
2, 4, 6 là 12, chia 3 được 4. 21 chia 3 được 7. Rồi ở trên cùng là một nút max.
The max node we'll choose, the maximum expected value, which is 8. So you had it right.
Nút max sẽ chọn giá trị kỳ vọng lớn nhất, là 8. Vậy các bạn đã đúng.
Now last time when we looked at minimax, after we saw minimax, we saw some modifications of minimax that could make it more practical.
Lần trước, sau khi học minimax, ta thấy một số cải tiến của minimax giúp nó thực tế hơn.
For example, we saw alpha beta printing, which was a meta reasoning approach that allowed us to think about, is this subtree important to look out or does it maybe not even matter what's in the subtree?
Ví dụ, ta đã thấy cắt tỉa alpha-beta, đó là cách lập luận meta cho phép ta nghĩ xem cây con này có cần xem không, hay có thể nó chẳng quan trọng bên trong có gì?
It's not going to affect the outcome of what the value is of this game. Can we do the same thing here? We have an expectimax tree.
Nó sẽ không ảnh hưởng đến kết quả giá trị của trò chơi này. Ở đây ta có làm tương tự được không? Ta có một cây expectimax.
We've seen the left branch to be 8. So we know that we have an option of 8 going this way. We now see a 2 over here.
Nhánh trái có giá trị 8. Vậy ta biết đi hướng này được 8. Giờ ta thấy một số 2 ở đây.
Can we now skip the rest or not? See some of those. Why not? Well, you can't know.
Ta có thể bỏ qua phần còn lại không? Có bạn nói là có. Tại sao không? Vì bạn không thể biết.
Right now it doesn't look pretty good with a 2. But what if one of these is 1 million over here? All of a sudden, it looks really good.
Hiện giờ với số 2 thì trông không tốt lắm. Nhưng nếu một trong các số này là 1 triệu thì sao? Bỗng nhiên nó trông rất tốt.
And you want to go there. Of course, you still need a check none of the other ones are negative 1 billion.
Và bạn sẽ muốn đi hướng đó. Tất nhiên, bạn vẫn cần kiểm tra xem không số nào khác là -1 tỷ.
But it really matters to look until till the last one because, when you average things out, one really extreme number can always dominate the average.
Vậy nên phải xem cho đến số cuối cùng, vì khi lấy trung bình, một con số cực đoan luôn có thể chi phối giá trị trung bình.
And so you can't skip anything in this scenario unless you know there are maybe some bounds on what values can be achieved at the different nodes. So can't do the same kind of printing.
Nên ở đây bạn không thể bỏ qua gì cả, trừ khi bạn biết một số cận về các giá trị có thể đạt được ở những nút khác nhau. Vậy ta không thể cắt tỉa kiểu đó.
The other thing we looked down was to do a depth limited search.
Điều khác ta đã xem là tìm kiếm giới hạn độ sâu.
The reason there was that, if we have to traverse the tree, even with alpha beta pruning, where we only to look at, in best case scenario , square root of the size of the tree, square of the size of the trees is still often way too big to visit everything.
Lý do là nếu phải duyệt cả cây, thì ngay cả với cắt tỉa alpha-beta, trong trường hợp tốt nhất ta chỉ cần xem căn bậc hai của kích thước cây, mà căn bậc hai kích thước cây vẫn thường quá lớn để duyệt hết mọi thứ.
So can we maybe look out less by making approximations?
Vậy ta có thể xem ít hơn bằng cách xấp xỉ không?
And in depth limited search, we made the approximation that we said we're not going to search all the way to the bottom because we can't get there in the time we have.
Trong tìm kiếm giới hạn độ sâu, ta xấp xỉ bằng cách không tìm kiếm đến tận đáy vì không thể tới đó trong thời gian có hạn.
We're going to stop earlier. So maybe we stop somewhere here.
Ta sẽ dừng sớm hơn. Có thể ta dừng ở đâu đó quanh đây.
We say after three moves we use an estimate of the true value, using a evaluation function. So I would look at the current situation.
Sau ba nước đi, ta dùng một ước lượng của giá trị thật, bằng hàm đánh giá. Tôi sẽ xem tình huống hiện tại.
We had an evaluation function that this situation, we think it's worth this much. Compute that number and use that instead of looking underneath. That evaluation function is only going to be an approximation.
Ta có một hàm đánh giá cho tình huống này, và nghĩ rằng nó đáng giá chừng này. Tính con số đó và dùng nó thay vì xem các nút bên dưới. Hàm đánh giá đó chỉ là một xấp xỉ.
It might be better if you design a really good evaluation function, whereas if you don't design a good one, a lot of art goes into that. Often also machine learning goes into that.
Nếu bạn thiết kế hàm đánh giá thật tốt thì kết quả tốt hơn, còn nếu không thì sao, có rất nhiều nghệ thuật trong việc này. Thường cả machine learning cũng được dùng.
If you have seen many situations before, you've seen how much they were worth. You can in principle machine learn to predict how much a new situation is worth.
Nếu bạn đã thấy nhiều tình huống trước đó, và biết chúng đáng giá bao nhiêu, về nguyên tắc bạn có thể học máy để dự đoán một tình huống mới đáng giá bao nhiêu.
What it results in is that you don't need to go as deep in the tree, and you can, in a reasonable amount of time, find an approximate answer to the value at the top.
Kết quả là bạn không cần đi sâu xuống cây, và trong một khoảng thời gian hợp lý, bạn tìm được câu trả lời xấp xỉ cho giá trị ở trên cùng. Còn các xác suất mà ta đang dùng thì sao?
How about these probabilities that we're using now. Let's do a little bit of a refresher of what they are and then build up from there.
Hãy ôn lại một chút chúng là gì rồi xây dựng tiếp từ đó.
A random variable represents an event whose outcome is unknown, and a probability separation is an assignment of weights to those outcomes.
Một biến ngẫu nhiên biểu diễn một sự kiện có kết quả chưa biết, và một phân phối xác suất là một phép gán và một phân phối xác suất là một phép gán của các trọng số cho những kết quả đó.
For example, we might decide that we don't know what the traffic is on the freeway, or Bainbridge, right now. We don't know what it is, but we still want to somehow reason about it.
Ví dụ, giả sử chúng ta không biết tình trạng giao thông trên đường cao tốc, hay đường Bainbridge, ngay lúc này. Ta không biết nó thế nào, nhưng vẫn muốn suy luận về nó bằng cách nào đó.
And so we're going to assign probabilities to different possible situations. We might say 25% chance it's empty. It's probably not the Bainbridge, then. It's something else.
Vì vậy ta sẽ gán xác suất cho các tình huống có thể xảy ra. Ta có thể nói 25% là đường vắng. Vậy chắc không phải đường Bainbridge rồi. Là một đường khác.
50% chance the highway has mild traffic and 25% chance it has heavy traffic — a lot of modeling assumption being made here.
50% đường cao tốc hơi đông và 25% là kẹt nặng. Ở đây ta đã đưa ra rất nhiều giả định mô hình hóa.
For one, we just assumed that traffic can take on only three values. That's a very specific assumption of how we're modeling the world here.
Thứ nhất, ta giả định giao thông chỉ nhận ba giá trị. Đó là một giả định rất cụ thể về cách ta mô hình hóa thế giới.
You might say, I'm going to measure density with real numbers, or you might say, I'm going to model it in five categories.
Bạn có thể nói: tôi sẽ đo mật độ bằng số thực, hoặc bạn có thể nói: tôi sẽ mô hình hóa thành năm loại.
Those are choices you have to make as the engineer, the designer of your AI system. How do you want to capture what is in the world?
Đó là những lựa chọn bạn phải đưa ra với tư cách kỹ sư, người thiết kế hệ thống AI. Bạn muốn nắm bắt những gì có trong thế giới như thế nào?
And then the second thing we have to do is choose probabilities for each one of them.
Và việc thứ hai ta phải làm là chọn xác suất cho từng trường hợp.
And the choice of those probabilities this will affect what we do when we run an expectimax agent because, if the probabilities are different, then different outcomes are more or less likely, making certain branches better or worse for the agent.
Lựa chọn các xác suất đó sẽ ảnh hưởng đến việc ta làm khi chạy tác tử expectimax, vì nếu các xác suất khác đi, thì các kết quả có khả năng xảy ra nhiều hay ít hơn, khiến một số nhánh tốt hơn hoặc tệ hơn cho tác tử.
But that's what we have to do here for now. There are some laws of probability. They're always non-negative, and they have to sum up to 1.
Nhưng bây giờ ta cứ phải làm như vậy. Có một số quy luật của xác suất. Chúng luôn không âm, và tổng phải bằng 1.
So notice that the sum of all of these is one. It's also the case that, as we get more information maybe over the lifetime of the agent, the probabilities can change.
Hãy để ý tổng của tất cả những số này là một. Ngoài ra, khi ta có thêm thông tin, có thể là trong suốt vòng đời của tác tử, các xác suất có thể thay đổi.
For example, maybe a priori we think probability of heavy traffic is 25%, but now we know that it is 8:00 AM.
Ví dụ, ban đầu ta nghĩ xác suất kẹt nặng là 25%, nhưng giờ ta biết là 8 giờ sáng.
Well, if we know it's 8:00 AM, probability of heavy traffic is higher because a lot of people are driving around at 8:00 AM. And now the probability has changed to the 0.6.
Nếu biết là 8 giờ sáng, xác suất kẹt nặng cao hơn vì rất nhiều người đang đi trên đường lúc 8 giờ sáng. Và giờ xác suất đã đổi thành 0,6.
We'll talk more about that later. The middle one third of the class is very much focused on dealing with probabilities, updating them based on new evidence that comes in.
Ta sẽ nói thêm về điều này sau. Một phần ba giữa của khóa học tập trung rất nhiều vào việc xử lý xác suất, cập nhật chúng dựa trên bằng chứng mới.
And so we'll defer that to them. But for now, just keep in mind that these probabilities are things we need to work with and that they can change as you get more information.
Nên ta sẽ để phần đó cho sau. Còn bây giờ, chỉ cần nhớ rằng các xác suất này là thứ ta cần làm việc cùng, và chúng có thể thay đổi khi bạn có thêm thông tin.
What does it mean to compute an expectation? The expected value of a function of a random variable is the average weighted by the probability of distribution over outcomes.
Tính kỳ vọng nghĩa là gì? Giá trị kỳ vọng của một hàm của biến ngẫu nhiên là trung bình có trọng số theo phân phối xác suất trên các kết quả.
So how long does it get to the airport?
Vậy đi đến sân bay mất bao lâu?
How long to get to the airport if this is our distribution over traffic — and maybe depending on the traffic situation, it could be 20 minutes, 30 minutes or 60 minutes.
Mất bao lâu để đến sân bay nếu đây là phân phối của ta về giao thông, và tùy tình hình giao thông, có thể mất 20 phút, 30 phút hoặc 60 phút.
Then the expected value of travel time to the airport would be the weighted sum, which gives us 35 minutes.
Thì giá trị kỳ vọng của thời gian đến sân bay là tổng có trọng số, cho ra 35 phút.
Any questions about this? This is the basic review we're doing. Yes.
Có câu hỏi nào về phần này không? Đây là phần ôn tập cơ bản. Vâng, mời bạn.
[INAUDIBLE] So the question is, what if the expected value is the same in both branches but maybe in one branch it'll be either 500 or 550, whereas the other one
[KHÔNG NGHE RÕ] Câu hỏi là, nếu giá trị kỳ vọng ở hai nhánh bằng nhau, nhưng một nhánh có thể là 500 hoặc 550, còn nhánh kia
would have something close to 0 and 1,000. And that's a much higher variance. You might you have a preference for one or the other.
là gần 0 và 1.000 thì sao. Và phương sai cao hơn nhiều. Bạn có thể thích nhánh này hơn nhánh kia.
We'll touch upon some of that at the end of this lecture. So let's defer it for now, but it's a good consideration.
Ta sẽ đề cập chút về điều đó ở cuối bài giảng. Tạm để sau, nhưng đó là một điều đáng cân nhắc.
So in expectimax search, we have a probabilistic model of how the opponent or the environment will behave in any state. This model could be as simple as a uniform distribution, roll of dice.
Trong tìm kiếm expectimax, ta có một mô hình xác suất về cách đối thủ hoặc môi trường sẽ hành xử ở bất kỳ trạng thái nào. Mô hình này có thể đơn giản như phân phối đều, như tung xúc xắc.
The model could be sophisticated and require a lot of computation.
Mô hình cũng có thể phức tạp và đòi hỏi nhiều tính toán.
It might be something along the lines of you have to decide whether to organize a barbecue or a indoor event, maybe October 10th, and then maybe run a complicated simulation of air pressure, air flows.
Chẳng hạn bạn phải quyết định tổ chức tiệc nướng ngoài trời hay sự kiện trong nhà, giả sử ngày 10 tháng 10, rồi có thể chạy một mô phỏng phức tạp về áp suất không khí, luồng khí.
And from that, you have a distribution over what the weather will be like on that day. And then you use that distribution to decide whether one or the other is the better decision.
Từ đó, bạn có một phân phối về thời tiết vào ngày hôm đó. Rồi bạn dùng phân phối đó để quyết định phương án nào tốt hơn.
And so that can often happen in practice that the way you get those probabilities is after a very complicated calculation and then finally you know what the probabilities are.
Trong thực tế điều này thường xảy ra: cách bạn có được các xác suất đó là sau một phép tính rất phức tạp và cuối cùng bạn mới biết các xác suất.
In the game tree, there is a chance node for any such stochastic event where we don't have control.
Trong cây trò chơi, có một nút ngẫu nhiên cho mỗi sự kiện ngẫu nhiên mà ta không kiểm soát.
It could be opponent or it could be environment, and it might even be that our probabilistic model says that it's likely the ghosts are adversarial to us but they're not necessarily always adversarial to us.
Đó có thể là đối thủ hoặc môi trường, và thậm chí mô hình xác suất của ta có thể nói rằng nhiều khả năng các con ma đối kháng với ta nhưng không phải lúc nào cũng đối kháng.
That's one type of probabilistic model, where you say maybe they're mastermind ghosts working directly against us, maybe not. Maybe some ss for one, some probability for the other.
Đó là một kiểu mô hình xác suất, khi bạn nói có thể chúng là những con ma thông minh trực tiếp chống lại ta, hoặc không. Có thể xác suất này cho khả năng một, xác suất kia cho khả năng còn lại.
For now we assume each chance node magically comes along with probabilities. So probability fairy visits us for this lecture, sprinkles the probabilities and we're good to go.
Bây giờ ta giả sử mỗi nút ngẫu nhiên tự nhiên có sẵn các xác suất. Như thể tiên xác suất ghé thăm ta trong bài giảng này, rắc các xác suất xuống và thế là xong.
One thing to keep in mind, though, is that, even though this is how we model things, it doesn't need to mean that we are right.
Tuy nhiên, cần nhớ một điều là dù ta mô hình hóa như vậy, không có nghĩa là ta đúng.
For example, you might model a opponent as some probability of being minimax and some probability of being random.
Ví dụ, bạn có thể mô hình hóa một đối thủ có một xác suất nào đó chơi theo minimax và một xác suất nào đó chơi ngẫu nhiên.
But that doesn't mean the opponent is actually doing any such things. It's just your model that you put in this expectimax tree.
Nhưng không có nghĩa đối thủ thực sự làm như vậy. Đó chỉ là mô hình của bạn mà bạn đặt vào cây expectimax.
And hopefully your model is related to what is happening in the real world. For example, maybe you are playing against someone and you don't have enough information to know how they play.
Và hy vọng mô hình của bạn có liên quan đến những gì đang xảy ra trong thế giới thực. Ví dụ, giả sử bạn đang chơi với một người mà bạn không có đủ thông tin để biết họ chơi thế nào.
You don't know their strategy. And then you might have a distribution over strategies. In practice, they have one strategy, and they're using it. But you don't know what the strategy is.
Bạn không biết chiến lược của họ. Khi đó bạn có thể dùng một phân phối trên các chiến lược. Thực tế, họ chỉ có một chiến lược và đang dùng nó. Nhưng bạn không biết đó là chiến lược nào.
And so you have a distribution over strategies and optimize against a distribution over strategies rather than a single strategy.
Nên bạn có một phân phối trên các chiến lược và tối ưu theo phân phối đó thay vì theo một chiến lược duy nhất.
Let's do another little exercise.
Ta làm thêm một bài tập nhỏ nữa.
Let's say you know that your opponent is actually running a depth to a minimax and uses the result 80% of the time, and the other 20% of the time, doing a random move to mix things up.
Giả sử bạn biết đối thủ thực ra chạy minimax độ sâu 2 và dùng kết quả đó 80% thời gian, còn 20% còn lại thì đi một nước ngẫu nhiên cho khó đoán.
How would you put this into a game tree? I'll give you about maybe a minute to think about this, talk with your neighbors. And let's see where you come up with.
Bạn sẽ đưa điều này vào cây trò chơi thế nào? Tôi cho các bạn khoảng một phút để nghĩ, trao đổi với bạn bên cạnh. Xem các bạn nghĩ ra gì.
Any thoughts about how we can model this?
Ai có ý kiến về cách mô hình hóa này không?
Over there, yes.
Bạn ở đằng kia, mời.
[INAUDIBLE] So the suggestion here is, because we
[KHÔNG NGHE RÕ] Ý kiến là, vì ta
know the opponent periodically makes a random move, we don't want to play too conservatively. And so we want it somehow built into what we do that we don't end up playing too conservatively.
biết đối thủ thỉnh thoảng đi nước ngẫu nhiên, nên ta không muốn chơi quá thận trọng. Vậy ta muốn bằng cách nào đó đưa vào những gì ta làm để không rơi vào lối chơi quá thận trọng.
Now of course the question is how do we build that into it. So we know that's what we want based on analyzing what the description is here.
Tất nhiên câu hỏi là làm sao đưa điều đó vào. Ta biết mình muốn thế, dựa trên việc phân tích mô tả ở đây.
But what we want to avoid, of course, is that we have to hard code all kinds of things into it. Then we'd like to see if we can reduce it to a game tree.
Nhưng tất nhiên, điều ta muốn tránh là phải mã hóa cứng đủ thứ vào đó. Ta muốn xem có thể quy về một cây trò chơi không.
And we run search, the right kind of search in this game tree, then that strategy that you want, that periodically taking your chances just automatically emerges from solving the game tree.
Rồi ta chạy đúng loại tìm kiếm trên cây trò chơi này, thì chiến lược bạn muốn, tức thỉnh thoảng chấp nhận rủi ro, sẽ tự động xuất hiện khi giải cây trò chơi.
And so then the question becomes, if we want achieved this — and you're right, we want we do want to achieve this — how do we set up the game tree such that a search in that three gives us what we want?
Vậy câu hỏi trở thành, nếu muốn đạt được điều này và bạn đúng, ta thực sự muốn thế, thì thiết lập cây trò chơi thế nào để tìm kiếm trên cây đó cho ra điều ta muốn?
Suggestion in the back there.
Ý kiến ở phía sau kia.
[INAUDIBLE] So the suggestion there is, if we reach an opponent node,
[KHÔNG NGHE RÕ] Ý kiến là, nếu gặp nút của đối thủ,
we're going to model it as 80% chance one type of behavior, 20% chance another type of behavior.
ta mô hình hóa nó là 80% khả năng một kiểu hành vi, 20% khả năng một kiểu hành vi khác.
20% chance of the type of behavior — in fact, we reach a chance node again because it's random.
Với 20% đó, thực ra ta lại có một nút ngẫu nhiên vì nó là ngẫu nhiên.
And the 80% side, we reach the minimax strategy of depth too that the opponent is using.
Còn ở nhánh 80%, ta có chiến lược minimax độ sâu 2 mà đối thủ đang dùng.
And then once we do that — and that's the answer we're going to follow here — is we achieve a game tree that, if we run expectimax in that game tree, we find a strategy that takes advantage of the randomness in the opponent while also being aware that it's only random 20% of the time.
Và khi làm vậy và đó là đáp án ta sẽ theo ở đây ta có một cây trò chơi mà nếu chạy expectimax trên đó, ta tìm được chiến lược tận dụng tính ngẫu nhiên của đối thủ, đồng thời biết rằng họ chỉ ngẫu nhiên 20% thời gian.
So the answer remains then expectimax.
Vậy đáp án vẫn là expectimax.
But to run this expectimax, when we look at these chance nodes, for each chance, node a bunch of calculation has to happen inside that chance node before we can proceed.
Nhưng để chạy expectimax này, với các nút ngẫu nhiên, ở mỗi nút ngẫu nhiên phải có cả một loạt tính toán bên trong nút đó trước khi ta đi tiếp.
So when we look at one of these chance nodes, what's the probability of the opponent, let's say a ghost, moving left or right?
Khi nhìn một nút ngẫu nhiên, xác suất đối thủ, ví dụ một con ma, đi sang trái hay phải là bao nhiêu?
Well, we need to then look at this description here and we actually need to go run depth to minimax to understand what happens 80% of the time. So you need to think about that.
Ta cần nhìn vào mô tả này và thực sự phải chạy minimax độ sâu 2 để biết điều gì xảy ra trong 80% thời gian. Bạn cần nghĩ về điều đó.
That tells us for 80% of the time what's happening one specific action, depth to a minimax solution.
Nó cho ta biết trong 80% thời gian hành động cụ thể nào xảy ra, theo nghiệm minimax độ sâu 2.
And then the other 20% of the time we have maybe equal probability over all other actions, or maybe even including the one that's chosen from the depth to a minimax.
Còn 20% thời gian còn lại có thể ta chia xác suất đều cho mọi hành động khác, hoặc thậm chí gồm cả hành động được chọn từ minimax độ sâu 2.
So what we have here, then, is, whenever we encounter a chance node, we have to do a whole minimax calculation to just find the probabilities that live in that chance node.
Vậy ở đây, mỗi khi gặp một nút ngẫu nhiên, ta phải tính cả một minimax chỉ để tìm các xác suất nằm trong nút ngẫu nhiên đó.
Imagine the ghost did a depth 10 minimax.
Hãy tưởng tượng con ma chạy minimax độ sâu 10.
Then every chance that you encounter, you'd have to run a depth 10 minimax search, which could be pretty expensive quickly, to find the distribution over actions they would take.
Thì mỗi nút ngẫu nhiên bạn gặp, bạn phải chạy một tìm kiếm minimax độ sâu 10, và việc đó có thể nhanh chóng trở nên khá tốn kém, chỉ để tìm phân phối trên các hành động họ sẽ chọn.
So it's kind of interesting. Imagine it's indeed depth 10 minimax 80% of the time, and 20% of the time just random action.
Điều này khá thú vị. Hãy tưởng tượng đúng là minimax độ sâu 10 trong 80% thời gian, và 20% còn lại là hành động ngẫu nhiên.
To solve that kind of problem, in every opponent node you have to run another depth 10 minimax, whereas in regular minimax, you just have to do a depth 10 once in the original tree and you're done.
Để giải bài toán kiểu đó, ở mỗi nút đối thủ bạn phải chạy thêm một minimax độ sâu 10, trong khi với minimax thông thường, bạn chỉ chạy độ sâu 10 một lần trên cây ban đầu là xong.
What's happening here? Why is it so much more expensive to deal with an opponent that does this other thing where sometimes they do something random?
Chuyện gì đang xảy ra ở đây? Tại sao xử lý một đối thủ như thế này lại tốn kém hơn nhiều, đối thủ mà đôi khi làm điều gì đó ngẫu nhiên?
It's because now we don't have a perfect match between the assumptions of one player, player A about player B and player B about Player A. Once these assumptions are mismatched, all of a sudden the tree doesn't nicely align in the entire search and you need to do all these side calculations.
Vì giờ ta không còn sự khớp hoàn hảo giữa giả định của người chơi A về người chơi B và của B về A. Khi các giả định này lệch nhau, đột nhiên cây không còn khớp gọn gàng trong toàn bộ tìm kiếm và bạn phải làm hàng loạt tính toán phụ.
And that's what's happening here, whereas in minimax, if one is always minimiz — other one is always maximizer and they know that about each other and do that consistently, then their tree is the same tree.
Đó là điều xảy ra ở đây, còn trong minimax, nếu một bên luôn là bên cực tiểu còn bên kia luôn là bên cực đại, và họ biết điều đó về nhau và làm nhất quán, thì cây của họ là cùng một cây.
But here it's not anymore because there is a mismatch, and we need to do a big calculation in each of the opponent nodes to figure out what they would do in that situation or distribution over what they would do.
Nhưng ở đây thì không còn vậy vì có sự lệch giả định, và ta phải tính toán lớn ở mỗi nút của đối thủ để biết họ sẽ làm gì trong tình huống đó, hoặc phân phối trên những gì họ sẽ làm.
Any questions about this?
Có câu hỏi nào về phần này không?
Yes.
Mời bạn.
[INAUDIBLE] The way we set it up here, the assumption is then this is how we model the opponent.
[KHÔNG NGHE RÕ] Cách ta thiết lập ở đây, giả định là đây là cách ta mô hình hóa đối thủ.
So we model the opponent as doing this. What they actually do, it might be that. If it is that, then we're doing great by solving it this way.
Tức ta mô hình hóa đối thủ làm như thế này. Còn thực tế họ làm gì thì có thể đúng như vậy. Nếu đúng vậy thì giải theo cách này là rất tốt.
If they're actually doing something else, then doing this is not going to be the best fit to play against that opponent.
Còn nếu họ thực sự làm điều khác, thì làm thế này sẽ không phải là cách phù hợp nhất để chơi với đối thủ đó.
But all we can be sure of in this setting here is that we have a model for how we think they behave.
Nhưng điều duy nhất chúng ta chắc chắn trong bối cảnh này là ta có một mô hình về cách ta nghĩ họ hành xử.
And if we assume that's a good model, this is how we could solve the problem.
Và nếu ta giả định đó là một mô hình tốt, thì đây là cách ta có thể giải bài toán.
Question, yes. [INAUDIBLE] In this case, it will take a constant amount of time longer.
Có câu hỏi, mời em. [KHÔNG NGHE RÕ] Trong trường hợp này, nó sẽ lâu hơn một lượng thời gian không đổi.
So it'll be the constant amount of time that it takes to expand depth to minimax search.
Đó là lượng thời gian không đổi để mở rộng thêm độ sâu cho tìm kiếm minimax.
And so maybe that is a certain amount of time that is a factor — I don't know — 20 or 100 larger than just already having a chance node that tells you this region over actions.
Và có thể đó là một hệ số nào đó, một hệ số — thầy không biết — lớn hơn 20 hay 100 lần so với việc đã có sẵn một nút xác suất cho biết phân phối trên các hành động.
And then that would be happening throughout the tree that you have to pay that factor 10 or 100 whenever you consider the opponent.
Và điều đó sẽ xảy ra khắp cây tìm kiếm, nghĩa là bạn phải trả hệ số 10 hay 100 đó mỗi khi tính đến đối thủ.
It also shows that, in practice, you might have to approximate your opponent because, if your opponent is somehow capable of looking 100 deep, you might not have the resources to also look 100 deep and you'll have to approximate it with something else that hopefully is good enough.
Nó cũng cho thấy rằng trong thực tế, bạn có thể phải xấp xỉ đối thủ của mình, vì nếu đối thủ có khả năng nhìn trước sâu 100 bước, bạn có thể không đủ tài nguyên để cũng nhìn sâu 100 bước và sẽ phải xấp xỉ họ bằng một thứ khác mà hy vọng là đủ tốt.
Let's take a look at the assumptions you were making throughout here. And what are the dangers of optimism and the dangers of pessimism? What are the dangers of optimism?
Hãy xem các giả định mà ta đã đặt ra xuyên suốt phần này. Và nguy cơ của sự lạc quan và nguy cơ của sự bi quan là gì? Nguy cơ của sự lạc quan là gì?
It's assuming chance when the world is adversarial. What does that mean? It means you go around the world, you see everything very rosy, everything's good, everything's good.
Đó là giả định có yếu tố ngẫu nhiên trong khi thế giới là đối kháng. Điều đó nghĩa là gì? Nghĩa là bạn đi khắp thế giới, thấy mọi thứ đều màu hồng, mọi thứ đều tốt, mọi thứ đều tốt.
And in practice, that might mean you get pickpocketed everywhere, you get mugged.
Và trong thực tế, điều đó có thể nghĩa là bạn bị móc túi khắp nơi, bị cướp.
A lot of things go wrong because you're just assuming the world is so good where it really is not as good as you're assuming it is. And so that's the danger of optimism.
Nhiều thứ hỏng vì bạn chỉ giả định thế giới tốt đẹp, trong khi thực ra nó không tốt như bạn nghĩ. Đó là nguy cơ của sự lạc quan.
You get taken advantage of by adversaries. What's the danger of pessimism? Well, what does it mean to be too pessimistic? It means that you assume the worst case when it's actually not that likely.
Bạn bị đối thủ lợi dụng. Còn nguy cơ của sự bi quan là gì? Vậy bi quan quá mức nghĩa là gì? Nghĩa là bạn giả định trường hợp xấu nhất trong khi thực ra nó không có nhiều khả năng xảy ra.
You see a bunny and you think it's a vampire bunny, every single bunny you see. Now that gives you a very, very scary life.
Bạn thấy một chú thỏ và nghĩ đó là thỏ ma cà rồng, con thỏ nào bạn thấy cũng vậy. Như thế thì cuộc sống rất đáng sợ.
You're constantly jumping away from things, not living very optimally if they're just tiny, little bunnies. More generally what it means — let's look at some examples for Pac-Man.
Bạn cứ liên tục nhảy tránh mọi thứ, sống không hề tối ưu chỉ vì mấy chú thỏ bé tí. Nói tổng quát hơn thì — hãy xem vài ví dụ với Pac-Man.
What we'll do here is we'll look at a grid of possible scenarios. So what do we have here?
Ở đây ta sẽ xem một lưới các kịch bản có thể xảy ra. Vậy ta có gì ở đây?
We have — Pac-Man could play minimax or play expectimax, and the ghost could be adversarial or could be random.
Pac-Man có thể chơi minimax hoặc expectimax, còn con ma có thể đối kháng hoặc ngẫu nhiên.
If the ghost is random and Pac-Man plays expectimax, that's a good way to play. You're matched up with how the world works. So let's take a look at that first.
Nếu con ma ngẫu nhiên và Pac-Man chơi expectimax, đó là cách chơi tốt. Bạn khớp với cách thế giới vận hành. Hãy xem trường hợp đó trước.
Random ghost, Pac-Man plays expectimax, and here we go. The ghost randomly stepped out of the way, Pac-Man didn't. Let's watch it again.
Ma ngẫu nhiên, Pac-Man chơi expectimax, và bắt đầu. Con ma ngẫu nhiên tránh đường, còn Pac-Man thì không. Xem lại lần nữa.
Pac-Man assumed the ghost would do something random, so wasn't afraid to get too close, and then just ate the one pellet left and won the game.
Pac-Man cho rằng con ma sẽ làm gì đó ngẫu nhiên, nên không ngại lại gần, rồi ăn viên cuối cùng và thắng ván chơi.
What do you think is going to happen in the next where we have Pac-Man play minimax and the ghost is adversarial?
Bạn nghĩ điều gì sẽ xảy ra ở trường hợp tiếp theo, khi Pac-Man chơi minimax và con ma đối kháng?
Well, adversarial ghost is going to try to chase Pac-Man, and Pac-Man's going to anticipate that and keep a safe distance and hopefully still somehow get to the food pellet.
Con ma đối kháng sẽ cố đuổi theo Pac-Man, và Pac-Man sẽ lường trước điều đó, giữ khoảng cách an toàn và hy vọng vẫn tới được viên thức ăn.
You might wonder, how come this adversarial ghost doesn't just protect the food pellet. Wouldn't that be a smarter thing to do?
Bạn có thể thắc mắc, sao con ma đối kháng này không canh viên thức ăn. Làm vậy chẳng phải thông minh hơn sao?
Well, that's what an adversarial ghost would do if they could look really, really far ahead in the game tree. But in practice, we can only look so far ahead.
Đó là điều một con ma đối kháng sẽ làm nếu nó nhìn trước được thật sự xa trong cây trò chơi. Nhưng trong thực tế, ta chỉ nhìn trước được đến một mức.
The typically evaluation function for a ghost is based on distance to Pac-Man.
Hàm đánh giá thường dùng cho con ma dựa trên khoảng cách đến Pac-Man.
And if you only look, let's say, four steps ahead and after four steps you're hoping to be as close as possible to Pac-Man, then you get this kind of behavior where you are constantly trying to move closer and you might open up the pellet for Pac-Man to eat and finish the game.
Và nếu bạn chỉ nhìn trước, giả sử, bốn bước và sau bốn bước bạn muốn ở gần Pac-Man nhất có thể, thì sẽ có kiểu hành vi này, là liên tục cố tiến lại gần và bạn có thể để hở viên thức ăn cho Pac-Man ăn và kết thúc ván chơi.
Now let's think about what happens if we assume — well, we play expectimax, but the ghost is a minimax ghost.
Giờ hãy nghĩ xem điều gì xảy ra nếu ta giả định — à, ta chơi expectimax, nhưng con ma là ma minimax.
So the ghost is playing directly against Pac-Man. Pac-Man is playing expectimax. So Pac-Man is too optimistic for their own good.
Tức con ma chơi đối đầu trực tiếp với Pac-Man. Pac-Man chơi expectimax. Vậy Pac-Man lạc quan quá mức, có hại cho chính nó.
So very optimistic, hangs out , and just made it on this one. Sometimes optimism is good, and it works out.
Rất lạc quan, đi lòng vòng, và vừa kịp thắng ván này. Đôi khi lạc quan là tốt và hiệu quả.
Sometimes it's less good. And so this will play out stochastically because just the way the game is set up — a little bit of randomness in it. And sometimes Pac-Man will succeed.
Đôi khi thì kém hơn. Và kết quả sẽ diễn ra ngẫu nhiên vì cách trò chơi được thiết lập có một chút ngẫu nhiên trong đó. Đôi khi Pac-Man thành công.
Sometimes he'll be eaten. It's not playing very safe against an adversarial ghost. How about the other scenario, the scenario in the bottom right here?
Đôi khi nó bị ăn. Nó chơi không an toàn trước một con ma đối kháng. Còn kịch bản còn lại thì sao, kịch bản ở góc dưới bên phải?
Now, bottom right — the random ghost, but then a minimax Pac-Man. Minimax means Pac-Man assumes that ghost is playing against it.
Góc dưới bên phải: con ma ngẫu nhiên, nhưng Pac-Man chơi minimax. Pac-Man. Minimax nghĩa là Pac-Man cho rằng con ma đang chơi đối đầu với nó.
So he's going to play very safe, assume that the ghost has a plan to come and chase it and eat it and going to keep a very safe distance.
Nên nó sẽ chơi rất an toàn, cho rằng con ma có kế hoạch đuổi theo và ăn nó, và sẽ giữ khoảng cách rất an toàn.
But in reality, the ghost is actually random. So the ghost is just randomly bopping around.
Nhưng thực tế con ma lại ngẫu nhiên. Con ma chỉ đi lang thang ngẫu nhiên.
Pac-Man waits off on the left, and then when finally there is room, he's daring to go. Let's look at another one of these. Ghost, he's just bopping around.
Pac-Man đợi ở bên trái, và cuối cùng khi có chỗ trống, nó mới dám đi. Hãy xem một ví dụ khác. Con ma, nó chỉ đi lang thang.
Pac-Man is worried, very worried, keep being worried, but then finally says, now there is no mastermind plan that exists anymore that can get me on the way to the dot.
Pac-Man lo lắng, rất lo lắng, cứ lo mãi, nhưng rồi cuối cùng nói: giờ không còn kế hoạch thần sầu nào của ma có thể chặn tôi trên đường đến chấm thức ăn nữa.
And now I'm willing to go. We ran this quite a few times. Here are the scores we ended up with.
Và giờ tôi sẵn sàng đi. Chúng tôi đã chạy cái này khá nhiều lần. Đây là các điểm số thu được.
So if you want to get statistically significant scores, you need to run more than 5 times. But I think this gets the picture across.
Nếu muốn điểm số có ý nghĩa thống kê thì cần chạy nhiều hơn 5 lần. Nhưng tôi nghĩ vậy cũng đủ để thấy ý chính.
If it's a random ghost in expectimax, we get the highest on average, 503, because we're in it easy environment, because the ghost is not playing against us, and we're aware we're in an easier environment and taking advantage of it.
Nếu ma ngẫu nhiên và ta dùng expectimax, ta được điểm trung bình cao nhất, 503, vì ta ở trong môi trường dễ, vì con ma không chơi đối đầu với ta, và ta biết mình đang ở môi trường dễ hơn và tận dụng điều đó.
Here we're in a difficult environment, and we are aware of it. Our score is lower, but not that bad because we realize this is a difficult environment and we play accordingly.
Ở đây ta ở trong môi trường khó, và ta nhận ra điều đó. Điểm thấp hơn, nhưng không tệ lắm vì ta nhận ra đây là môi trường khó và chơi cho phù hợp.
On the other hand, if it's a difficult environment and we're not aware of it, then we often get eaten and our score is not that great on average.
Ngược lại, nếu môi trường khó mà ta không nhận ra, thì thường bị ăn và điểm trung bình không cao.
And then over here, we have a random ghost — so easy environment, but we're not really taking advantage of it. So we have a lower score than if we take advantage of it.
Còn ở đây là ma ngẫu nhiên, môi trường dễ nhưng ta không thực sự tận dụng nó. Nên điểm thấp hơn so với khi có tận dụng.
But not that much worse in this case because we only waste so much time being scared before we dare to go for the food pellet. Any questions about this?
Nhưng trong trường hợp này không tệ hơn nhiều vì ta chỉ phí một ít thời gian sợ hãi trước khi dám đi lấy viên thức ăn. Có câu hỏi nào về phần này không?
So so far we have seen two types of games. We have seen minimax games and expectimax games. There are some other types — still turn based.
Vậy là đến giờ ta đã thấy hai loại trò chơi. Trò chơi minimax và trò chơi expectimax. Còn một số loại khác, vẫn theo lượt.
For example, backgammon — in backgammon, there is a maximizer, a minimizer, and chance. And so effectively this is the same thing.
Ví dụ cờ backgammon: trong backgammon có bên cực đại, bên cực tiểu và yếu tố may rủi. Về bản chất thì vẫn như vậy.
We just now need a dispatch node that can dispatch between terminal, max, min, exp, and we can solve these kinds of problems too. For example, what happens here?
Chỉ cần thêm một nút điều phối để chuyển giữa terminal, max, min, exp, và ta cũng giải được các bài toán này. Ví dụ, chuyện gì xảy ra ở đây?
It's maximizer's turn, chooses a move. After that move there is a roll of dice, which determines the situation minimizer gets to see, in which they get to make a move.
Đến lượt bên cực đại, chọn một nước đi. Sau nước đó có một lần tung xúc xắc, quyết định tình huống mà bên cực tiểu thấy, và họ đi một nước.
And this process repeats — very simple. In terms of algorithmic change, just a four way dispatch instead of three way dispatch.
Quá trình này lặp lại, rất đơn giản. Về thuật toán, chỉ đổi từ điều phối ba nhánh sang bốn nhánh.
Backgammon — it's actually a pretty big game in terms of state space. There's about 20 legal moves each time.
Backgammon thực ra là một trò khá lớn xét về không gian trạng thái. Mỗi lần có khoảng 20 nước đi hợp lệ.
There is a depth — if you do a depth two search, then you have 20 moves.
Về độ sâu, nếu tìm kiếm sâu hai tầng thì có 20 nước đi.
But there is also this stochasticity to account for — how many possible outcomes of rolling dice — and we get actually a very large tree, even if we only look at a very small depth.
Nhưng còn phải tính tính ngẫu nhiên: có bao nhiêu kết quả khi tung xúc xắc, và ta được một cây rất lớn, dù chỉ xét độ sâu rất nhỏ.
As the depth increases the probability of reaching a given search node shrinks.
Khi độ sâu tăng, xác suất đạt tới một nút tìm kiếm nhất định giảm đi.
So what we have happen here is that, because of the stochasticity, each particular branch is in some sense less significant than it would be in a minimax scenario.
Điều xảy ra ở đây là, do tính ngẫu nhiên, mỗi nhánh riêng lẻ ở một nghĩa nào đó ít quan trọng hơn so với trong minimax.
Because in minimax, maybe an opponent could forces down a path. In backgammon, the opponent can't really force us down anything.
Vì trong minimax, đối thủ có thể ép ta đi xuống một đường. Trong backgammon, đối thủ không thể ép ta làm gì cả.
They need to have the right roll of the dice before they can force us anywhere. And so no single branch can dominate as much as it can in minimax.
Họ cần tung được xúc xắc đúng thì mới ép được ta đi đâu. Nên không nhánh nào chi phối mạnh như trong minimax.
Historically, what that resulted into is that, for backgammon, there was actually the first AI world champion for any game.
Về mặt lịch sử, kết quả là backgammon có nhà vô địch thế giới AI đầu tiên cho bất kỳ trò chơi nào.
This was built with just a depth two search, a very good evaluation function, trained with reinforcement learning, and this achieved world champion level play.
Nó chỉ dùng tìm kiếm sâu hai tầng, một hàm đánh giá rất tốt, được huấn luyện bằng học tăng cường, và đạt trình độ vô địch thế giới.
And so the intuition here, why you can get away with a depth two search is that, if you miss this one scenario that could happen somewhere down the tree, actually it's not that likely to happen anyway because of the averaging that's happening.
Trực giác ở đây, vì sao chỉ cần tìm kiếm sâu hai tầng là: nếu bỏ sót một kịch bản có thể xảy ra ở đâu đó sâu trong cây, thì dù sao nó cũng không có nhiều khả năng xảy ra vì phép lấy trung bình đang diễn ra.
And so just depth two happens to be enough to build a world champion.
Nên độ sâu hai tình cờ là đủ để tạo ra nhà vô địch thế giới.
There are other types of games. So this is one variation where you have min, max, exp. Here we have a multiagent game.
Còn có các loại trò chơi khác. Đây là một biến thể có min, max, exp. Còn đây là trò chơi nhiều tác tử.
So we have a red player, a blue player, and a green player. What does this mean? It means, if we're at a terminal node, here let's pick one where there are all different numbers.
Có người chơi đỏ, xanh dương và xanh lá. Điều này nghĩa là gì? Nghĩa là nếu ta ở một nút kết thúc, ta chọn một nút mà các số đều khác nhau.
If we end up over here, the utility for red is 7, for blues is 2, for green is 1.
Nếu ta kết thúc ở đây, độ hữu dụng của đỏ là 7, của xanh dương là 2, của xanh lá là 1.
So what we have here is that each player has their own value of a terminal node and will optimize for their own outcome. Minimax — we kind of had that, too.
Vậy mỗi người chơi có giá trị riêng cho một nút kết thúc và sẽ tối ưu cho kết quả của riêng mình. Minimax thì ta cũng có kiểu đó.
The maximizer had the number that we were showing, and the minimizer had the negative of that number. So there were actually two numbers sitting there, but it was the negative of each other.
Bên cực đại có con số mà ta hiển thị, còn bên cực tiểu có số đối của nó. Thực ra có hai con số ở đó, nhưng chúng đối nhau.
So we only showed one. But minimax is a special case of this where we just collapse those two opposite numbers into one number that we display.
Nên ta chỉ hiển thị một. Minimax là trường hợp đặc biệt, khi ta gộp hai số đối nhau đó thành một số để hiển thị.
Different things can emerge here, though, when these numbers are not just complementary to each other. For example, what if we're over here? What would blue want to happen?
Nhưng ở đây có thể xuất hiện những điều khác khi các số không chỉ đối nhau. Ví dụ, nếu ta ở đây thì sao? Xanh dương muốn điều gì xảy ra?
Well, blue would love this 6 over here. Can they make that happen? Well, what if they play this way? What will green do?
Xanh dương sẽ rất thích số 6 ở đây. Họ có làm được điều đó không? Nếu họ đi đường này thì sao? Xanh lá sẽ làm gì?
Green will look at, well, I could have six or two. Green will choose the six, which will happen that blue also gets 6 and gets what they want.
Xanh lá sẽ nhìn: tôi có thể được sáu hoặc hai. Xanh lá sẽ chọn sáu, và thế là xanh dương cũng được 6 và có điều họ muốn.
So what have here is actually a collaboration between blue and green happens to emerge because the utilities they have over outcomes happens to be aligned in a nice way that they end up working together.
Vậy ở đây có sự hợp tác giữa xanh dương và xanh lá tự nhiên xuất hiện vì độ hữu dụng của họ đối với các kết quả tình cờ trùng khớp với nhau theo một cách rất hay nên cuối cùng họ hợp tác với nhau.
That doesn't mean they are told to work together. It's just emerging from these utilities. If the game ended up over here, what would blue want?
Điều đó không có nghĩa là họ được bảo phải hợp tác. Nó tự xuất hiện từ các độ hữu dụng này. Nếu trò chơi đi sang bên này, blue sẽ muốn gì?
Blue would say, well, I'd love to get a 7. That's the nicest thing underneath here. Let's say blue goes here. What will green say?
Blue sẽ nói: tôi rất muốn được 7. Đó là giá trị tốt nhất ở dưới này. Giả sử blue đi vào đây. Green sẽ nói gì?
Well, there's is a one here for me and a five here for me. I like the five. I'm going here, and blue ends up with two.
Ở đây có một số 1 cho tôi và một số 5 cho tôi. Tôi thích số 5. Tôi đi vào đây, và blue chỉ được 2.
Blue really should have gone this way where green would have chosen — let's see — actually, not sure if it fully works out here.
Lẽ ra blue nên đi theo hướng này nơi green sẽ chọn — để xem nào, thật ra không chắc là nó hiệu quả hoàn toàn ở đây.
Blue would have preferred — yeah, let me retake that one.
Blue sẽ thích hơn — à, để tôi nói lại chỗ đó.
What happened here on the right is that, even though blue would have preferred seven, green doesn't pay attention to that and just picks this one independently.
Điều xảy ra ở bên phải là dù blue muốn số 7 hơn, green không để ý đến điều đó và cứ chọn cái này một cách độc lập.
What happens on the left is something very similar. If blue goes here, green will still not pay attention to what blue cares about. Here is a seven.
Bên trái xảy ra điều rất tương tự. Nếu blue đi vào đây, green vẫn không để ý đến điều blue quan tâm. Đây là số 7.
Here's a two and, green will pick this side and blue will end up with one.
Đây là số 2, và green sẽ chọn phía này còn blue sẽ chỉ được 1.
And so in both branches here, we see the green the opposite of blue would have wanted, even though on this side, they're perfectly aligned.
Vậy ở cả hai nhánh này, ta thấy green làm ngược lại với điều blue muốn, dù ở phía này họ hoàn toàn trùng khớp nhau.
And that's just a consequence of whatever their utilities are for the leaf nodes. How do we solve a problem like this?
Đó chỉ là hệ quả của độ hữu dụng mà họ có tại các nút lá. Làm sao giải một bài như thế này?
In each node, we now look at the values underneath and pass them all up based on the decision the current node would make. For example, we're here, green checks 2 or 6.
Tại mỗi nút, ta xem các giá trị bên dưới và chuyển hết lên trên dựa trên quyết định mà nút hiện tại sẽ đưa ra. Ví dụ ở đây, green xét 2 hoặc 6.
6 is better. So it's being passed up — 1, 6, 6 is being passed up. Here green says 2 is better than 1. So 6, 1, 2 is being passed up.
6 tốt hơn. Nên ta chuyển lên — 1, 6, 6 được chuyển lên. Ở đây green nói 2 tốt hơn 1. Nên 6, 1, 2 được chuyển lên.
Then blue takes a look, which is the middle number. 6 is better. So 1, 6, 6 is the value over here.
Rồi blue xem số ở giữa. 6 tốt hơn. Vậy giá trị ở đây là 1, 6, 6.
Similarly on the other side, green decides at the bottom, we'll go for the 7. This is a 5, 1, 7. The other, it'll pick the 5. This is a 5, 2, 5.
Tương tự ở phía bên kia, green quyết định ở dưới cùng, ta chọn số 7. Đây là 5, 1, 7. Ở cái còn lại, nó chọn số 5. Đây là 5, 2, 5.
Then blue will pick based on the middle number. So it'll be a 5, 2, 5. And red will pick on the first number, and so it will be 5, 2, 5.
Rồi blue chọn dựa trên số ở giữa. Nên nó là 5, 2, 5. Và red chọn dựa trên số đầu tiên, nên nó sẽ là 5, 2, 5.
And this is how the game will play out.
Và trò chơi sẽ diễn ra như vậy.
So similar machinery as we've used for minimax and expectinodes, but now keep in mind that you need to propagate values for all players, not just a single value.
Cơ chế này giống như ta đã dùng cho minimax và các nút expectimax, nhưng cần nhớ là phải truyền giá trị của tất cả người chơi, chứ không chỉ một giá trị duy nhất.
Any questions about this?
Có câu hỏi nào về phần này không?
Let's take a couple of minutes break here. And after the break, we'll look at utilities.
Chúng ta nghỉ giải lao vài phút. Sau giờ nghỉ, ta sẽ xem về độ hữu dụng.
[INAUDIBLE] Sure.
[KHÔNG NGHE RÕ] Vâng.
STUDENT
So you don't how predefined office hours?
Vậy thầy không có giờ hỏi đáp định sẵn ạ?
We should ail you — PROFESSOR: They — [AUDIO OUT] OK, let's restart.
Chúng em nên gửi email cho thầy — GIÁO SƯ: Họ — [MẤT ÂM THANH] Được rồi, ta bắt đầu lại.
In the second half of the lecture, we're going to look at utilities. To think back to lecture 1, the mantra for the AI class is maximize your expected utility.
Trong nửa sau của bài giảng, ta sẽ xem về độ hữu dụng. Nhớ lại bài giảng 1, câu châm ngôn của môn AI là tối đa hóa độ hữu dụng kỳ vọng của bạn.
We've been maximizing expected utilities. We've not actually looked at those utilities and where they might come from and why it's even meaningful to have them. Should they even exist?
Ta vẫn luôn tối đa hóa độ hữu dụng kỳ vọng. Nhưng ta chưa thực sự xem xét các độ hữu dụng đó đến từ đâu và tại sao việc có chúng lại có ý nghĩa. Chúng có nên tồn tại không?
And that's what we're going to do now.
Và đó là điều ta sẽ làm bây giờ.
So one question you could have — why should we average utilities? Why not minimax? Let's think about this.
Một câu hỏi bạn có thể đặt ra: tại sao ta lại lấy trung bình độ hữu dụng? Sao không dùng minimax? Ta hãy nghĩ về điều này.
Let's say you're going to make a decision and maybe you're deciding between — I don't know — deciding between pizza and Thai food or something.
Giả sử bạn sắp đưa ra một quyết định và có thể bạn đang chọn giữa pizza và đồ ăn Thái chẳng hạn. Bạn có thể nói: độ hữu dụng của từng món là bao nhiêu.
You might say, OK, what am I utilities for each one of them. The Thai food is exciting, but it's sometimes too spicy for me. And then you assign some utility to it.
Đồ ăn Thái thì thú vị, nhưng đôi khi quá cay với tôi. Rồi bạn gán cho nó một độ hữu dụng nào đó. Pizza cũng có một độ hữu dụng.
The pizza has some utility. But the Thai food one has different outcome.
Nhưng đồ ăn Thái có kết quả khác nhau.
So you can say, well, I should maybe use the worst case where it's too spicy for me and it's going to be bad.
Nên bạn có thể nói: có lẽ tôi nên dùng trường hợp xấu nhất là nó quá cay với tôi và sẽ rất tệ.
So then Thai food is a worse choice than pizza, and I'm going to take pizza. That I would be the minimax approach to choosing what you're going to do.
Vậy đồ ăn Thái là lựa chọn tệ hơn pizza, và tôi sẽ chọn pizza. Đó sẽ là cách tiếp cận minimax để chọn việc mình sẽ làm. Nhưng có thể đó không phải cách đúng.
But maybe that's not the right way to do it. If you're constantly afraid of the worst case scenario — that's the scenario we talked about — everything is a vampire bunny.
Nếu bạn luôn sợ kịch bản xấu nhất như kịch bản ta đã nói, cái gì cũng là thỏ ma cà rồng.
In fact, what you're then going to do if you're never going to go out on the street.
Thật ra khi đó bạn sẽ không bao giờ ra đường.
You're going to say, there's always some chance that one of the drivers makes a mistake, drives onto the sidewalk, hits me. And you're minimax tells you to stay inside at all times.
Bạn sẽ nói, luôn có khả năng một tài xế nào đó mắc lỗi, lao lên vỉa hè và tông trúng tôi. Và minimax bảo bạn lúc nào cũng ở trong nhà. Rồi có thể bạn lại nói, ở trong nhà thì cũng có thể động đất và nhà sập.
Then you'll maybe say, well, if you're inside, maybe an earthquake can happen and things can collapse. And you'll just have no reasonable choices if you run minimax for all your decisions.
Và bạn sẽ chẳng còn lựa chọn hợp lý nào nếu chạy minimax cho mọi quyết định. Lúc duy nhất minimax thực sự có ích là khi bạn đã loại trước tất cả những chuyện đặc biệt hiếm khi xảy ra.
The only time minimax can actually be useful for you is if you already, ahead of time, exclude all those really special things that rarely happen.
Nhưng nếu muốn tính đến việc những sự kiện cực đoan này có thể xảy ra, thì minimax sẽ không bao giờ hiệu quả.
But if you want to incorporate that these things can happen, these extreme events, then minimax will never work.
Nhưng nếu muốn tính đến việc những chuyện này có thể xảy ra, những sự kiện cực đoan này, thì minimax sẽ không bao giờ hiệu quả.
So if you want to do a fairly comprehensive reasoning about the world, minimax will just not work for you because you're always afraid about what's going to happen.
Nên nếu bạn muốn suy luận khá toàn diện về thế giới, minimax đơn giản là sẽ không hiệu quả, vì bạn lúc nào cũng lo sợ về điều sắp xảy ra.
So then [INAUDIBLE] down to something like expectimax. What's the principle of maximum expected utility?
Vậy nên ta chuyển sang thứ như expectimax. Nguyên lý kỳ vọng độ hữu dụng cực đại là gì?
Is that the rational agent should choose the action that maximizes his expected utility given its knowledge about how the world works.
Là tác tử hợp lý nên chọn hành động cực đại hóa độ hữu dụng kỳ vọng của nó, dựa trên hiểu biết về cách thế giới vận hành.
So then the questions are, where do these utilities come from. Let's think about that. Let's say you have a agent that's supposed to clean your house.
Vậy câu hỏi là độ hữu dụng đến từ đâu. Hãy nghĩ về điều đó. Giả sử bạn có một tác tử có nhiệm vụ dọn nhà cho bạn.
Where should utilities for the agent come from? Well, we should specify them for that agent. And we should tell the agent your utilities based on how clean the house.
Độ hữu dụng của tác tử nên đến từ đâu? Ta phải chỉ định chúng cho tác tử đó. Ta phải cho tác tử biết độ hữu dụng của nó dựa trên mức độ sạch của ngôi nhà.
We can't just let the agent choose their own utility. If they choose their own utility, they might just say, oh, well, high utility no matter what. I'm just going to sit here.
Ta không thể để tác tử tự chọn độ hữu dụng. Nếu nó tự chọn, nó có thể nói: ồ, độ hữu dụng cao bất kể điều gì. Tôi cứ ngồi đây thôi.
It's easy. I'm optimizing my utility. Have to do nothing.
Dễ mà. Tôi đang tối ưu độ hữu dụng của mình. Chẳng phải làm gì cả.
So to insure that the agent does something we care about, we've got to be able to give it the utilities that we want it to optimize for. So that's where they come from.
Để đảm bảo tác tử làm điều ta quan tâm, ta phải đưa cho nó những độ hữu dụng mà ta muốn nó tối ưu. Đó là nơi chúng đến từ.
We have to give them to the agents. But that means that somehow we have to have utilities that quantify what we like or don't like about outcomes in the world.
Ta phải trao chúng cho tác tử. Nhưng điều đó có nghĩa là ta phải có độ hữu dụng định lượng được điều ta thích hay không thích ở các kết cục trong thế giới.
So how do we know that we even have those and that it's even rational to have utilities?
Vậy làm sao ta biết mình thực sự có chúng và việc có độ hữu dụng là hợp lý?
Does it even makes sense to think of the world in terms of every outcome has a utility associated with it? And let's say we do have a number for every outcome in the world.
Liệu có hợp lý không khi nghĩ về thế giới theo kiểu mỗi kết cục đều có một độ hữu dụng gắn với nó? Và giả sử ta có một con số cho mọi kết cục trong thế giới.
Why is averaging them the right thing to do? And what if you believe that your behavior just doesn't match up with utilities. Is that possible?
Tại sao lấy trung bình chúng lại là điều đúng đắn? Và nếu bạn tin rằng hành vi của mình không khớp với độ hữu dụng thì sao? Có thể như vậy không?
Is it possible that you just live your life in a way that utilities are not meaningful and then maybe you can't use utilities for your agents to help you out because it's mismatched with how you live your life?
Liệu có thể bạn sống theo cách mà độ hữu dụng không có ý nghĩa, và có thể bạn không dùng được độ hữu dụng cho tác tử để giúp mình, vì nó không khớp với cách bạn sống?
Well, let's first take a look at some of the new challenges in expectimax in terms of utilities compared to minimax. Let's look at these two game trees here.
Trước hết hãy xem một số thách thức mới của expectimax về độ hữu dụng so với minimax. Hãy nhìn hai cây trò chơi này.
What's different between them is that we squared the terminal values going to the right. So 0 squared is 0. 40 squared is 1620. 20 squared is 400.
Điểm khác nhau là ta đã bình phương các giá trị cuối ở cây bên phải. 0 bình phương là 0. 40 bình phương là 1620. 20 bình phương là 400.
30 squared is 900. Now let's see what happens if we run minimax in both of these trees. Well, in the first one, what did we end up with?
30 bình phương là 900. Giờ xem điều gì xảy ra nếu chạy minimax trên cả hai cây. Ở cây đầu, ta được gì?
Well, we end up with a 0 here, a 20 here. So we're going to play this way. What's going to happen in the second tree?
Ta được 0 ở đây, 20 ở đây. Nên ta sẽ đi hướng này. Còn cây thứ hai thì sao?
Outcome is going to be the same because, by squaring, the leaf nodes have the same ordering. So we have the same preference over leaf nodes.
Kết quả sẽ như nhau, vì khi bình phương, các nút lá vẫn giữ nguyên thứ tự. Nên ta có cùng sự ưu tiên trên các nút lá.
And in minimax, that means we end up with the same outcome. Min still prefer going left there and still prefer going left here, which will make max prefer going right here.
Và trong minimax, điều đó nghĩa là cùng một kết quả. Min vẫn thích đi trái ở đây và vẫn thích đi trái ở đây, khiến max thích đi phải ở đây.
The value is now 400 because we squared everything, but the game gets played the exact same way.
Giá trị giờ là 400 vì ta bình phương mọi thứ, nhưng ván chơi diễn ra y hệt.
What if we have expectinodes there. Well, this average is 20. This average here is 25. 25 is better.
Nếu ta có các nút expecti ở đó thì sao? Trung bình này là 20. Trung bình ở đây là 25. 25 tốt hơn.
We have 25. How about on the other side? The average here is 800. The average on the other one is 650.
Ta có 25. Còn phía bên kia? Trung bình ở đây là 800. Trung bình bên kia là 650.
So we prefer to 800, and it has changed.
Nên ta chọn 800, và lựa chọn đã thay đổi.
So by squaring the utilities, we've changed how we play the game.
Vậy bằng cách bình phương độ hữu dụng, ta đã thay đổi cách chơi.
So it means that, all of a sudden, when we work with things like expectimax where we average utilities, it's not just about ordering outcomes.
Nghĩa là bỗng nhiên, khi làm việc với expectimax, nơi ta lấy trung bình độ hữu dụng, vấn đề không chỉ là sắp thứ tự các kết cục.
It's also about the numbers we associated with these outcomes because the specifics of those numbers do matter and affect what we're going to decide.
Mà còn là các con số ta gán cho các kết cục đó, vì giá trị cụ thể của những con số này có ý nghĩa và ảnh hưởng đến quyết định của ta.
So let's look at some examples. Our utilities are functions from outcomes that is states of the world to real numbers that describe an agent's preferences. For example, maybe there's three possible outcomes.
Hãy xem vài ví dụ. Độ hữu dụng là hàm từ các kết cục, tức các trạng thái của thế giới, sang số thực mô tả sở thích của tác tử. Ví dụ, có ba kết cục khả dĩ.
You have an ice cream cone. You have an ice cream cone with one scoop. That's probably better. We have the ice cream cone with two scoops, which you might think is even better.
Bạn có một cây kem ốc quế. Bạn có cây kem ốc quế một viên. Cái đó có lẽ tốt hơn. Rồi cây kem ốc quế hai viên, mà bạn có thể nghĩ còn tốt hơn nữa.
And so you might say it's this kind of preference relationship.
Và bạn có thể nói đây là kiểu quan hệ ưu tiên.
That's great. But if you want to do expectimax, it's not enough to know which outcome is preferred over which outcome. We actually need associate numbers which each one of those to reason appropriately.
Tuyệt. Nhưng nếu muốn chạy expectimax, chỉ biết kết cục nào được ưu tiên hơn kết cục nào là chưa đủ. Ta thực sự cần gán một con số cho mỗi kết cục để suy luận cho đúng.
In a simple game, the numbers are easy. Just the rules of the game will tell you — maybe plus one for a win, negative 1 a loss, zero for a draw.
Trong một trò chơi đơn giản, các con số rất dễ. Chỉ cần luật chơi là cho bạn biết, có thể cộng một cho thắng, âm 1 cho thua, không cho hòa.
It turns out there is a theorum that, even beyond games, for any rational preferences, we can summarize them with a utility function, and we'll see the theorum in a moment.
Hóa ra có một định lý, ngay cả ngoài trò chơi, rằng với mọi sở thích hợp lý, ta có thể tóm tắt chúng bằng một hàm độ hữu dụng, và ta sẽ thấy định lý đó ngay sau đây.
So we prefer two scoops over one scoop over just a cone. But when we make decisions, we might not get to decide just between those three.
Vậy ta thích hai viên hơn một viên, hơn chỉ cái ốc quế. Nhưng khi ra quyết định, ta có thể không chỉ được chọn giữa ba thứ đó.
There might be probabilistic outcomes. For example, we might get a single or a double. Single makes us pretty happy. Double is more complex.
Kết quả có thể mang tính xác suất. Ví dụ, ta có thể nhận một viên hoặc hai viên kem. Một viên thì ta khá hài lòng. Hai viên thì phức tạp hơn.
When we get a double, we might drop it, much harder to balance. And now we only have the cone. Or we might really be happy and have the two scoops to enjoy.
Khi có hai viên, ta có thể làm rơi, vì khó giữ thăng bằng hơn nhiều. Và lúc đó ta chỉ còn lại cái ốc quế. Hoặc ta có thể rất vui và được thưởng thức cả hai viên kem.
Now if we need to decide whether to go for a single or double, it matters what the probabilities are of us dropping it and it matters what the actual utility numbers are here.
Giờ nếu cần quyết định chọn một viên hay hai viên, thì xác suất ta làm rơi kem rất quan trọng, và các giá trị độ hữu dụng thực tế ở đây cũng quan trọng.
It's not enough to know that two is better than one is better than zero. We need to know the numbers and the probabilities and that will determine which choice we make over here.
Chỉ biết rằng hai viên tốt hơn một viên, và một viên tốt hơn không có gì là chưa đủ. Ta cần biết các con số và các xác suất, và chúng sẽ quyết định ta chọn phương án nào ở đây.
So we need to deal with utilities of distributions over outcomes. Outcomes here — the terminology that people use is prizes.
Vậy ta cần xử lý độ hữu dụng của các phân phối trên các kết quả. Các kết quả này, thuật ngữ người ta dùng là prize (giải thưởng).
Don't think about it as some kind of prize you win for something amazing you've done. It's just terminology.
Đừng nghĩ nó là giải thưởng nào đó bạn nhận được vì làm điều gì tuyệt vời. Đó chỉ là thuật ngữ thôi.
You can just call it outcomes or leaf nodes in one of those trees, and that could be a prize that's called a, one that's called b, and so forth.
Bạn có thể gọi là kết quả hay nút lá trong một cây nào đó, và đó có thể là một prize gọi là a, một cái gọi là b, v.v.
A lottery is a situation with uncertain prizes. So it's a expectinode over outcome could be A or B. And then our notation is that, if you prefer a over b, we write this.
Lottery là tình huống có các prize không chắc chắn. Nó là một nút expectimax với kết quả có thể là A hoặc B. Và ký hiệu là, nếu bạn thích a hơn b, ta viết thế này.
If they're equally good to us, we write this thing.
Nếu hai thứ tốt như nhau với ta, ta viết ký hiệu này.
Now when we talk about lottery, again, this is a terminology in this context. That means something specific. This is what it means to be a lottery.
Khi nói về lottery, một lần nữa, đây là thuật ngữ trong ngữ cảnh này. Nó mang một nghĩa cụ thể. Lottery nghĩa là như thế này.
It doesn't mean there is some kind of game involved where you're scratching things and seeing what's underneath. It just means that a probabilistic event is going to happen.
Nó không có nghĩa là có trò chơi nào đó mà bạn cào và xem bên dưới có gì. Nó chỉ có nghĩa là một sự kiện xác suất sắp xảy ra.
We end up with either A or B with some probability distribution.
Ta nhận được A hoặc B theo một phân phối xác suất nào đó.
Now let's see what it means to be rational. One thing we want from a rational agent is that it has transitivity of its preferences. What does that mean?
Giờ ta xem thế nào là có tính hợp lý. Một điều ta muốn ở tác tử hợp lý là các sở thích của nó có tính bắc cầu. Nghĩa là gì?
If the agent prefers A over B and prefers B over C, the agent should also prefer A over C. That seems pretty logical.
Nếu tác tử thích A hơn B và thích B hơn C, thì nó cũng phải thích A hơn C. Điều đó khá logic.
Can we make this even more explicit that this is really the only right way to go in some sense? Well, we can. Imagine we have an agent who does not satisfy this property.
Ta có thể làm rõ hơn nữa rằng đây thực sự là cách duy nhất đúng theo một nghĩa nào đó không? Có, được. Hãy tưởng tượng một tác tử không thỏa tính chất này.
Then we can essentially acquire all their money.
Thì về cơ bản ta có thể lấy hết tiền của nó.
The way it is what happened is that, if they don't satisfy the property — let's say they prefer B over C — then if they had C when they start out, they would happily pay a little bit of money to give us C and in exchange get B.
Cách xảy ra là, nếu nó không thỏa tính chất đó, giả sử nó thích B hơn C, thì nếu lúc đầu nó có C, nó sẽ sẵn lòng trả một ít tiền để đưa ta C và đổi lấy B.
And we get one sent along the way by giving them B and getting C. If they don't prefer A over B, then they just B from us.
Và ta kiếm được một xu khi đưa nó B và nhận lại C. Nếu nó không thích A hơn B thì nó chỉ có B từ ta.
They can give B now and pay a little extra to get A instead from us. And we again made some money, then now have A. Now remember, we got C from them initially.
Nó có thể đưa B và trả thêm một ít để nhận A từ ta. Ta lại kiếm được tiền, và giờ nó có A. Nhớ rằng ban đầu ta đã nhận C từ nó.
If they're non-transitive, they decide C is better than A. And we have C ready to go, and they'll give us A again with a bit of money, because C is worth more to them.
Nếu nó không bắc cầu, nó cho rằng C tốt hơn A. Ta có sẵn C, và nó sẽ lại đưa ta A cùng một ít tiền, vì C có giá trị hơn với nó.
Now they have C, and we've got some money. And we're back to where we started.
Giờ nó có C, còn ta có thêm tiền. Và ta quay về điểm xuất phát.
So we went around in a circle where, at the end of it, all that happened is we made $0.3 and everybody's holding the same prizes as they were holding in the beginning.
Ta đi một vòng tròn, và cuối cùng chỉ có việc ta kiếm được 0,3 đô và mọi người vẫn giữ các prize như lúc đầu.
So being transitive seems pretty important. Otherwise, this cycle is going to be put into play against you, and you're going to lose everything over time.
Vậy tính bắc cầu có vẻ khá quan trọng. Nếu không, chu trình này sẽ bị khai thác để chống lại bạn, và bạn sẽ mất hết theo thời gian.
What are some other actions that people have posited rational agents should satisfy? You are required to either prefer A over B, B over A or be indifferent to them.
Còn những tiên đề nào khác người ta cho rằng tác tử hợp lý phải thỏa? Bạn buộc phải hoặc thích A hơn B, B hơn A, hoặc thờ ơ với cả hai.
Those are the only three options for two prizes. Transitivity, we just discussed.
Chỉ có ba lựa chọn đó cho hai prize. Tính bắc cầu thì ta vừa bàn.
Continuity — if you prefer over B and B over C, then there must be a lottery between A and C that is equivalent to B because B lies between A and C.
Tính liên tục: nếu bạn thích A hơn B và B hơn C, thì phải có một lottery giữa A và C tương đương với B, vì B nằm giữa A và C.
So some distribution over A and C should match up with B.
Tức là một phân phối nào đó trên A và C phải khớp với B.
Substitutability — if A and B are equally good to you, then a lottery that involves A with some probability is equivalent to you to the same lottery that involves B rather than A. Monotonicity says that, if you prefer A over B, then if P is a probability that's higher than Q,
Tính thay thế: nếu A và B tốt như nhau với bạn, thì một lottery có A với một xác suất nào đó tương đương với cùng lottery đó nhưng có B thay vì A. Tính đơn điệu nói rằng, nếu bạn thích A hơn B, thì nếu P là xác suất cao hơn Q,
then a lottery that has a higher probability on A compared to this one here should be preferable. If you prefer A over B, you increase the probability of A.
một lottery có xác suất cao hơn cho A so với lottery kia sẽ được ưa thích hơn. Nếu bạn thích A hơn B, bạn tăng xác suất của A.
Then you should prefer that lottery that has increased probability of A and decreased probability of B. These all seem pretty logical that you would want from your agents.
Thì bạn nên thích lottery có xác suất A tăng và xác suất B giảm. Tất cả những điều này đều khá logic mà bạn muốn ở tác tử của mình.
There is some theory that shows that, if your agent's preferences satisfy, or your preference, satisfy these actions with rationality, then your optimal behavior can be described as maximization of expected utility.
Có một lý thuyết chỉ ra rằng, nếu các sở thích của tác tử, hay sở thích của bạn, thỏa các tiên đề về tính hợp lý này, thì hành vi tối ưu có thể được mô tả là cực đại hóa độ hữu dụng kỳ vọng.
So rationality confirmed if you satisfy these actions. And a more formal theorum says this — [INAUDIBLE] Von Neumann-Morgenstern theorum, and also from Ramsey in 1931.
Vậy tính hợp lý được xác nhận nếu bạn thỏa các tiên đề này. Và một định lý hình thức hơn nói thế này: [KHÔNG NGHE RÕ] định lý Von Neumann-Morgenstern, và cả của Ramsey năm 1931.
Given any preference of satisfying these constraints, there exists a real value function U, the utility function, such that if your preference is A over B, then that function U will satisfy U of A bigger than or equal to U of B and the utility of a lottery will be the weight sum of the utility of each of the entries, each
Với mọi sở thích thỏa các ràng buộc này, tồn tại một hàm giá trị thực U, hàm độ hữu dụng, sao cho nếu sở thích của bạn là A hơn B, thì hàm U đó sẽ thỏa U của A lớn hơn hoặc bằng U của B, và độ hữu dụng của một lottery sẽ là tổng có trọng số của độ hữu dụng từng thành phần, tức từng
of the prizes in the lottery. This is what we're doing in expectimax. The averaging step is exactly this. We're averaging utilities based on their probabilities.
prize trong lottery. Đây chính là điều ta làm trong expectimax. Bước lấy trung bình chính là như vậy. Ta lấy trung bình các độ hữu dụng theo xác suất của chúng.
So this is saying that that is the right thing to do if you have rational preference.
Vậy điều này nói rằng đó là cách làm đúng nếu bạn có sở thích hợp lý.
So if you're happy with these actions, then the consequence is that there exists a utility function where averaging is the right thing to do.
Vậy nếu bạn đồng ý với các tiên đề này, thì hệ quả là tồn tại một hàm hữu dụng mà việc lấy trung bình là điều đúng đắn cần làm.
The maximum expected utilities principal is then to maximize that expected value.
Nguyên lý độ hữu dụng kỳ vọng cực đại là cực đại hóa giá trị kỳ vọng đó.
Let's now think about human utilities because, if we're going to have agents make decisions for us, we need to think about our utilities and give them to the agent so they can maximize our expected utility.
Bây giờ hãy nghĩ về độ hữu dụng của con người vì nếu để tác tử ra quyết định thay chúng ta, ta cần nghĩ về độ hữu dụng của mình và đưa cho tác tử để nó cực đại hóa độ hữu dụng kỳ vọng của ta.
How do you assess the utility values for outcomes? What do we use to normalize them?
Làm sao đánh giá độ hữu dụng của các kết cục? Ta dùng gì để chuẩn hóa chúng?
You could say the best possible thing in the world is a 1, and the worst possible thing in the world is a 0.
Bạn có thể coi điều tốt nhất trên đời là 1, và điều tệ nhất trên đời là 0.
For example, maybe the worst thing is being death and then you could start quantifying things like micromorts.
Ví dụ, điều tệ nhất có thể là cái chết, rồi bạn có thể bắt đầu định lượng bằng micromort.
If you have a one in a million chance of death, what is that worth to you to avoid that?
Nếu có một phần triệu khả năng tử vong, bạn sẵn sàng trả bao nhiêu để tránh nó?
And you start quantifying things that are extreme because we want to look at the extremes. Quality adjusted life years is another metric often used.
Ta định lượng những thứ cực đoan vì ta muốn xét các trường hợp cực biên. Số năm sống điều chỉnh theo chất lượng là một thước đo khác hay được dùng.
It's also important to keep in mind, when we say there is a utility function consistent with your preferences, you can actually add a constant to it and rescale it with a positive scaler and nothing will change in your behavior because that is compatible with how averaging operations also work out.
Cũng cần nhớ rằng, khi nói có một hàm hữu dụng nhất quán với sở thích của bạn, thì bạn có thể cộng thêm một hằng số và nhân với một số vô hướng dương mà hành vi của bạn không đổi, vì điều đó tương thích với cách phép lấy trung bình hoạt động.
Now if we don't consider lotteries, all we can do when asking people questions is understand what they prefer over what and have a ranking.
Nếu không xét các lottery, khi hỏi mọi người ta chỉ có thể biết họ thích cái nào hơn cái nào và có một bảng xếp hạng.
But once we start giving them lotteries, we can start understanding the actual utility values. And that's what we need to do to infer their actual utility values. So here's how we do this.
Nhưng khi đưa ra các lottery, ta có thể bắt đầu hiểu các giá trị hữu dụng thực sự. Và đó là điều cần làm để suy ra độ hữu dụng thực sự của họ. Cách làm như sau.
Standard way of getting some of these utilities — you say, OK, you can spin the wheel or pay to pass.
Cách chuẩn để có các độ hữu dụng này: bạn nói, được, bạn có thể quay vòng quay hoặc trả tiền để bỏ qua.
When you spin the wheel, there's some small chance it lands on dead, instant death. That's it. So nobody would like to play this game probably.
Khi quay, có một xác suất nhỏ rơi vào ô chết, tử vong ngay lập tức. Chỉ vậy thôi. Chắc không ai muốn chơi trò này.
But the question is, how much are you willing to pay to not have to play this / and that tells us something about what, let's say, this is worth to you.
Nhưng câu hỏi là, bạn sẵn sàng trả bao nhiêu để khỏi phải chơi, và điều đó cho ta biết phần nào giá trị của số tiền đó với bạn.
So best possible prize is, in this case, could be life stays as is or something. Worst case is you're dead.
Giải thưởng tốt nhất, trong trường hợp này, có thể là cuộc sống cứ như hiện tại. Tệ nhất là bạn chết.
And so the game would be, you could say, OK, how much would be willing to pay to avoid dead. Well, maybe I'm willing to pay $30 bucks to avoid death.
Và trò chơi là, bạn hỏi, bạn sẵn sàng trả bao nhiêu để tránh cái chết. Có thể tôi sẵn sàng trả 30 đô để tránh chết.
If it's some kind of Michael Moore thing where there is, let's say, a one in a million chance of dying — if that is your decision here, what that means is then, on the scale from 0 to 1, on this standardized utility scale, $30 to you is worth 0.000001 micromorts OK.
Giả sử như kiểu của Michael Moore, có một phần triệu khả năng chết... nếu đó là quyết định của bạn, thì nghĩa là, trên thang từ 0 đến 1, thang độ hữu dụng chuẩn hóa này, 30 đô với bạn đáng giá 0.000001, tức một micromort.
Or 0.0001 morts, which is one micromort. So we now have a scale. That's how much you value $30. We can do this for everything.
Hay 0.0001 mort, mà là một micromort. Vậy ta đã có một thang đo. Đó là mức bạn đánh giá 30 đô. Ta làm được điều này với mọi thứ.
For everything, we can say, OK — maybe you ask, how much do you value your laptop. And you might say, well, maybe there's a choice or something else.
Với mọi thứ, ta có thể hỏi, chẳng hạn bạn đánh giá chiếc laptop bao nhiêu. Và bạn có thể nói, có lẽ có một lựa chọn nào khác.
Maybe how much do you value getting a new bicycle. And then you might say, OK, there's a choice between getting a new bicycle or not having to play this game.
Hay bạn đánh giá việc có xe đạp mới bao nhiêu. Rồi bạn có thể nói, có lựa chọn giữa nhận xe đạp mới hoặc không phải chơi trò này.
And then you say, well, I'd rather play the game and get a bicycle than to not play the game. You look at the equivalence.
Và bạn nói, tôi thà chơi trò đó để lấy xe đạp còn hơn không chơi. Bạn xét sự tương đương.
What probabilities land them here such that you're equally happy with one situation versus the other? And that tells you the utility value of a bicycle, a new bicycle for you.
Xác suất nào khiến bạn hài lòng như nhau giữa hai tình huống? Và điều đó cho biết độ hữu dụng của một chiếc xe đạp, một chiếc xe đạp mới với bạn.
How about money? Isn't money a way people measure utility? It turns out money is not the same as utilities.
Còn tiền thì sao? Chẳng phải tiền là cách mọi người đo độ hữu dụng sao? Hóa ra tiền không giống độ hữu dụng.
For example, let's say we have a lottery, some probability of winning x, 1 minus p, the probability of winning y. Then the expected monetary value is this quantity over here.
Ví dụ, ta có một lottery, xác suất p thắng x, xác suất 1 trừ p thắng y. Thì giá trị tiền tệ kỳ vọng là đại lượng này.
That's averaging the money. But the utility of this lottery is this over here.
Đó là trung bình của số tiền. Nhưng độ hữu dụng của lottery này là đại lượng ở đây.
So the utility of the lottery is the way that some of the utilities of each outcomes, which is not the same as the utility of the average money you would get.
Độ hữu dụng của lottery là tổng các độ hữu dụng của từng kết cục theo xác suất, không giống độ hữu dụng của số tiền trung bình bạn nhận được.
In fact, often the utility of the lottery will be smaller than utility of the average money that you would get. That means most people are risk averse.
Thực tế, độ hữu dụng của lottery thường nhỏ hơn độ hữu dụng của số tiền trung bình bạn nhận được. Nghĩa là hầu hết mọi người ngại rủi ro.
And when deep in debt, people tend to be risk prone. Let's make this a little more explicit.
Còn khi nợ nần chồng chất, người ta có xu hướng chấp nhận rủi ro. Hãy làm rõ hơn một chút.
Imagine you want to understand utility of money. This is money. This is utility. How much is money worth in utility values?
Hãy tưởng tượng bạn muốn hiểu độ hữu dụng của tiền. Đây là tiền. Đây là độ hữu dụng. Tiền đáng giá bao nhiêu theo độ hữu dụng?
Well, who wants a million dollars? Most people. Some people don't. You missed your chance.
Ai muốn một triệu đô nào? Hầu hết mọi người. Có người không. Bạn lỡ cơ hội rồi.
Now the million dollars means it's worth something positive to you because you like it. How about a billion dollars? A lot of people. Whoever doesn't want, come talk to me.
Một triệu đô có giá trị dương với bạn vì bạn thích nó. Còn một tỷ đô thì sao? Nhiều người. Ai không muốn thì đến nói chuyện với tôi.
Maybe how much is it worth to get a billion dollars? Well, worth more. How much more? Well, maybe some amount more.
Nhận một tỷ đô đáng giá bao nhiêu? Đáng giá hơn. Hơn bao nhiêu? Có lẽ hơn một mức nào đó.
Now let's think about it again. Now you have your billion dollars in hand. You still want a million dollars. Yeah, probably you still want a million dollars.
Giờ hãy nghĩ lại. Giờ bạn đã có một tỷ đô trong tay. Bạn vẫn muốn một triệu đô. Ừ, chắc là bạn vẫn muốn một triệu đô.
More is always better. But the first million is much more special than once you already have the billion.
Càng nhiều càng tốt. Nhưng triệu đô đầu tiên đặc biệt hơn nhiều so với khi bạn đã có sẵn một tỷ đô.
See, the additional value here from utility you would get from going from zero to a million is much higher than if here you got an extra million maybe and only end up over here.
Thấy không, độ hữu dụng tăng thêm ở đây khi bạn đi từ 0 lên một triệu cao hơn nhiều so với việc ở đây bạn được thêm một triệu và chỉ dừng ở chỗ này.
So we see that somehow we look at these utility curves, they end up starting to saturate — not saturate, but climb more slowly as you have more and then the other way around here.
Vậy là khi nhìn các đường cong độ hữu dụng này, chúng bắt đầu bão hòa — không hẳn bão hòa, mà tăng chậm hơn khi bạn có nhiều hơn, và phía bên này thì ngược lại.
Once you're in debt a lot, once you have lost a billion dollars, you cannot pay it off ever anyway most likely. So what is it to then lose a little more?
Khi đã nợ rất nhiều, khi bạn đã mất một tỷ đô, thì nhiều khả năng bạn không bao giờ trả nổi. Vậy mất thêm một chút nữa thì có là gì?
It's all the same. And so that's what's happening on this side over here.
Cũng như nhau thôi. Đó là điều xảy ra ở phía bên này.
How can we quantify this? Imagine there's a lottery between $1,000 and $0. What is the expected monetary value of $500? But most people would prefer a guaranteed other amount.
Làm sao định lượng điều này? Hãy tưởng tượng một xổ số giữa $1.000 và $0. Giá trị tiền tệ kỳ vọng là $500. Nhưng hầu hết mọi người thích một khoản chắc chắn khác hơn.
Would you prefer $10 guaranteed over the lottery? Probably not. Would you prefer $900 guaranteed over the lottery. Yes, definitely $900 guaranteed is better than this.
Bạn có thích $10 chắc chắn hơn xổ số không? Chắc là không. Bạn có thích $900 chắc chắn hơn xổ số không? Có, chắc chắn $900 đảm bảo thì tốt hơn.
How about $400? Maybe $400 because it's guaranteed, and on average you get $500 and $400 is pretty close and now you're guaranteed. That's where most people will land, around $400.
Còn $400 thì sao? Có thể chọn $400 vì nó chắc chắn, và trung bình bạn được $500, $400 khá gần, mà lại được đảm bảo. Hầu hết mọi người sẽ dừng ở khoảng $400.
So that means is that the equivalent lies lower than the average. That's where insurance companies come in.
Nghĩa là giá trị tương đương thấp hơn mức trung bình. Đó là chỗ các công ty bảo hiểm xuất hiện.
If you are holding a lottery ticket of this type, an insurance company will say, this is worth $400 to you. I'll buy it off of you for $400.
Nếu bạn đang giữ một vé xổ số loại này, công ty bảo hiểm sẽ nói: nó đáng $400 với bạn. Tôi mua lại với $400.
I'll take the ticket. Your insurance company now has a lottery, but it has so many lotteries in its pool of lotteries that a central limit theorem kicks in.
Tôi lấy tờ vé. Giờ công ty bảo hiểm có một vé xổ số, nhưng họ có rất nhiều vé trong danh mục nên định lý giới hạn trung tâm phát huy tác dụng.
And for the insurance company, that averages out and that lottery ticket is actually worth $500. Even for you, it's the equivalent the $400.
Với công ty bảo hiểm, nó được trung bình hóa và vé đó thực sự đáng $500. Còn với bạn, nó tương đương $400.
And so that's how you actually get a win-win situation where there is a difference between the $400 and the $500. That's where the opportunity lies to have a win-win.
Và đó là cách có tình huống đôi bên cùng có lợi khi có chênh lệch giữa $400 và $500. Đó là cơ hội để cả hai cùng thắng.
In fact, if the insurance company gave you $450, they would still make $50 on it.
Thật vậy, nếu công ty bảo hiểm trả bạn $450, họ vẫn lời $50.
And so between 400 and 500 is the wiggle room for negotiation where all the win-wins lie between you and the insurance company. Now let's take a little test.
Vậy khoảng từ 400 đến 500 là chỗ để thương lượng, nơi mọi thỏa thuận đôi bên cùng có lợi giữa bạn và công ty bảo hiểm. Giờ ta làm một bài kiểm tra nhỏ.
Let's say you can choose between lottery A or B. A is 80% chance for $1,000, 20% chance nothing. B is guaranteed $3,000. Who prefers A?
Giả sử bạn chọn giữa xổ số A hoặc B. A là 80% được $1.000, 20% không được gì. B là chắc chắn được $3.000. Ai thích A?
Who prefers B? Most people prefer B. Here's another lottery. Choice C, 20% chance for a $1,000, 80% nothing, versus D, 25% $3,000, 75% nothing.
Ai thích B? Hầu hết thích B. Đây là một xổ số khác. Lựa chọn C: 20% được $1.000, 80% không được gì, so với D: 25% được $3.000, 75% không được gì.
Who prefers C? Who prefers D?
Ai thích C? Ai thích D?
So most people preferred C. That is pretty typical for general population to prefer B over A and C over D. So slides also predicted that. Now let's do a little bit of math.
Vậy hầu hết thích C. Đó là điều khá điển hình ở dân số nói chung: thích B hơn A và C hơn D. Các slide cũng dự đoán vậy. Giờ ta tính một chút.
If the utility of $0 is 0, because we can shift and rescale anyway, then B better than A means utility of 3k is better than 0.8 utility of 4k.
Nếu độ hữu dụng của $0 là 0, vì ta có thể dịch và co giãn tùy ý, thì B tốt hơn A nghĩa là độ hữu dụng của 3k lớn hơn 0,8 lần độ hữu dụng của 4k.
If C better than D, then we have this equation over here. That's the exact opposite statement. So people who prefer B over A and C over D have reached a contradiction.
Nếu C tốt hơn D thì ta có phương trình này. Đó là phát biểu hoàn toàn ngược lại. Vậy những người thích B hơn A và C hơn D đã rơi vào mâu thuẫn.
What does that mean? It means, as far as this is concerned, you had irrational preferences because there's no utility function that can satisfy both at the same time.
Điều đó nghĩa là gì? Nghĩa là xét theo cách này, sở thích của bạn là phi lý tính, vì không có hàm hữu dụng nào thỏa mãn cả hai cùng lúc.
Or maybe there is. Maybe it's not that you're irrational. Maybe there's something else at play. When you look at the utilities — and people studied this paradox a lot.
Hoặc có thể có. Có thể bạn không phi lý tính. Có thể có yếu tố khác đang tác động. Khi nhìn vào các độ hữu dụng, và người ta đã nghiên cứu nghịch lý này rất nhiều.
They say, well, maybe it's not because people are irrational. Maybe it's because we don't model the situation the right way.
Họ nói, có thể không phải vì con người phi lý tính. Có thể là vì ta không mô hình hóa tình huống đúng cách.
Maybe what happens — the reason you prefer B over A is because, when A is being chosen and you end up over here, you don't just get 0.
Có thể lý do bạn thích B hơn A là vì khi chọn A và rơi vào chỗ này, bạn không chỉ nhận 0.
You also get a very, very stupid feeling that you could have had a lot of money and you didn't.
Bạn còn có cảm giác rất ngu ngốc rằng lẽ ra mình đã có rất nhiều tiền mà lại không có.
And so there was 0 plus stupidity here, and utility of 0 plus stupidity is lower than the utility of zero.
Vậy ở đây là 0 cộng với sự ngu ngốc, và độ hữu dụng của 0 cộng ngu ngốc thấp hơn độ hữu dụng của 0.
And it makes it all work out again. Next time we'll look at MDPs.
Và như vậy mọi thứ lại khớp. Lần sau ta sẽ học về MDP.
STUDENT
Professor, I find this stuff really interesting. So I was wondering, what —
Thưa thầy, em thấy phần này rất thú vị. Nên em muốn hỏi là, cái gì —
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.