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ả.
[NO AUDIO] [SIDE CONVERSATION]
[KHÔNG CÓ ÂM THANH] [NÓI CHUYỆN RIÊNG]
PROFESSOR
Hi, everyone. Welcome to the sixth lecture of CS 188.
Chào các bạn. Chào mừng đến với bài giảng thứ sáu của CS 188.
Couple of announcements for today — your homework 2 was due yesterday. So this is an after-the-fact announcement, but it's good if you missed it that you know that next time not to miss it.
Có vài thông báo cho hôm nay. Bài tập về nhà 2 đã hết hạn hôm qua. Nên đây là thông báo muộn, nhưng nếu bạn lỡ hạn thì cũng nên biết để lần sau đừng bỏ lỡ nữa.
Also, your homework going forward always has three components. There is an electronic part, a written part, and a self-assessment of the previous written homework, so just a reminder of that.
Ngoài ra, từ giờ bài tập về nhà luôn có ba phần. Có phần làm trên máy, phần viết, và phần tự chấm bài viết của bài tập trước, nên tôi nhắc lại một chút.
For the written and for the self-assessment, use the template we provide such that it matches exactly up with what we have and fill in the blanks as you solve the problem.
Với phần viết và phần tự chấm, hãy dùng mẫu chúng tôi cung cấp để khớp chính xác với bản của chúng tôi, và điền vào chỗ trống khi bạn giải bài.
There is a mini contest — a little more about that in a second. Homework 3 games will go out soon, probably tonight, otherwise tomorrow. It will be due next Monday.
Có một cuộc thi nhỏ, lát nữa tôi sẽ nói thêm về nó. Bài tập 3 về trò chơi sẽ sớm được đăng, có thể tối nay, nếu không thì ngày mai. Hạn nộp là thứ Hai tuần sau.
We'll again have three components. And project 2 games will go out probably tomorrow and will be due next week Friday at 4:00 PM.
Vẫn sẽ có ba phần. Còn project 2 về trò chơi có thể được đăng ngày mai và hạn nộp là 4 giờ chiều thứ Sáu tuần sau.
The contest that's part of project 1, this is optional but we think very exciting. So I want to highlight a little bit what's going on there.
Cuộc thi nằm trong project 1 là tùy chọn nhưng chúng tôi thấy rất thú vị. Nên tôi muốn nói qua một chút về nó.
So this only counts for extra credit and for glory, not for regular points. What do you get to do in this contest?
Cuộc thi chỉ tính điểm cộng và để lấy danh dự, không tính vào điểm chính thức. Trong cuộc thi này các bạn làm gì?
In project 1, the mazes were relatively small, and there was only one Pac-Man trying to eat the food.
Ở project 1, các mê cung khá nhỏ, và chỉ có một Pac-Man đi ăn thức ăn.
In the mini contest, you get to control multiple agents who together are supposed to clear out the board. And in addition to controlling multiple agents on large boards, you also get to be time-constrained.
Trong cuộc thi nhỏ, bạn điều khiển nhiều tác tử cùng nhau dọn sạch bản đồ. Và ngoài việc điều khiển nhiều tác tử trên bản đồ lớn, bạn còn bị giới hạn thời gian.
So we all know that if you get infinite time, you can even run uniform cost search on these problems and ultimately return a solution. But that's not useful in practice.
Ai cũng biết nếu có thời gian vô hạn, bạn thậm chí có thể chạy tìm kiếm chi phí đồng nhất cho các bài này và cuối cùng cũng ra lời giải. Nhưng điều đó không hữu ích trong thực tế.
In mini contest 1, you get penalized for time used. The more time you use, the more you get penalized. If you can make fast decisions, you lose less points.
Ở cuộc thi 1, bạn bị phạt theo thời gian sử dụng. Dùng càng nhiều thời gian thì càng bị phạt nhiều. Nếu quyết định nhanh, bạn mất ít điểm hơn.
And then if you eat dots, you win points. So this is an example of a board there. If you submit — so a couple things to note — this will be closing on Sunday.
Còn ăn được chấm thì bạn được điểm. Đây là một ví dụ về bản đồ. Có vài điều cần lưu ý: cuộc thi sẽ đóng vào Chủ nhật.
So there's about a week left. You get 0.5 points of extra credit on project 1 per staff bot beaten. There is two staff bots coincidentally named staff bot 3 and staff bot 2.
Vậy còn khoảng một tuần. Bạn được cộng 0,5 điểm vào project 1 cho mỗi staff bot bạn đánh bại. Có hai staff bot, tình cờ tên là staff bot 3 và staff bot 2.
And there is 0.5 points for submitting any bot. So just go in there, get yourself a bot, and submit. You get 0.5 points already.
Và có 0,5 điểm cho việc nộp bất kỳ bot nào. Cứ vào đó, lấy một bot rồi nộp. Bạn đã có 0,5 điểm rồi.
And then we'll also rank students based on performance of their bots. And there is a little bit of extra credit related to that. And there's a leaderboard. Here is the current leader board.
Chúng tôi cũng xếp hạng sinh viên dựa trên hiệu suất bot của họ. Và có thêm một chút điểm cộng liên quan đến đó. Và có bảng xếp hạng. Đây là bảng xếp hạng hiện tại.
Staff bot's not on top anymore. Jason [? Lu ?] here — here? Congratulations, you're currently first. That's awesome.
Staff bot không còn đứng đầu nữa. Jason [? Lu ?] có ở đây không? Chúc mừng, bạn đang đứng nhất. Tuyệt vời.
[APPLAUSE] [INAUDIBLE] here? [INAUDIBLE]? Anybody just want to claim it? Don't do that.
[VỖ TAY] [KHÔNG NGHE RÕ] có ở đây không? [KHÔNG NGHE RÕ]? Có ai muốn nhận không? Đừng làm thế.
[LAUGHS] White guy claiming [INAUDIBLE].. [LAUGHTER] You can choose the name of your team freely. It doesn't have to be your own name.
[CƯỜI] Một anh da trắng nhận là [KHÔNG NGHE RÕ]... [CƯỜI] Bạn có thể tự do chọn tên đội. Không nhất thiết phải là tên của bạn.
You can do it in teams of two, just like for the project itself. And when you submit, your agent will appear on the leaderboard. Right now, this is the first 20.
Bạn có thể làm theo nhóm hai người, giống như project vậy. Và khi nộp, tác tử của bạn sẽ xuất hiện trên bảng xếp hạng. Hiện giờ đây là 20 hạng đầu.
But actually, there is six of those pages for about 120 total agents in competition now. Some agents have one student behind them. Some agents have two students working together behind them.
Nhưng thực ra có sáu trang như vậy, tổng cộng khoảng 120 tác tử đang thi đấu. Có tác tử chỉ có một sinh viên đứng sau. Có tác tử do hai sinh viên cùng làm.
So I encourage you to check it out. It's set up such that once you've completed project 1, getting a starter agent going should take extremely little time.
Nên tôi khuyến khích các bạn xem thử. Cuộc thi được thiết lập sao cho khi bạn đã xong project 1, việc chạy được một tác tử khởi đầu mất rất ít thời gian.
Then, of course, to do something more interesting requires some extra thought about what it takes to get two agents or multiple agents to work together and how to work under time constraints.
Dĩ nhiên, để làm được điều thú vị hơn thì cần suy nghĩ thêm về việc làm sao cho hai hay nhiều tác tử phối hợp với nhau và làm việc dưới giới hạn thời gian.
Any questions about logistics? Yes.
Có câu hỏi nào về các vấn đề hậu cần không? Vâng, bạn.
STUDENT
So you find the string for the how long it takes to find a path or how long it takes Pac-Man to move on the path?
Vậy là tính theo thời gian tìm đường đi, hay thời gian Pac-Man di chuyển trên đường đi ạ?
PROFESSOR
OK. So you get penalized for amount of time you use before you decide what your next action is. So the interface is the environment waits for the next action to be given.
Được. Bạn bị phạt theo lượng thời gian dùng trước khi quyết định hành động tiếp theo. Cách hoạt động là môi trường chờ hành động tiếp theo được đưa ra.
And the agent is computing, computing, computing, finally gives the next action. Then the environment says, how much time did you take? Based on that, points get subtracted and then executes the action.
Tác tử cứ tính toán, tính toán, tính toán, rồi cuối cùng đưa ra hành động tiếp theo. Sau đó môi trường hỏi: bạn đã mất bao nhiêu thời gian? Dựa vào đó, điểm bị trừ rồi môi trường thực hiện hành động.
And thanks to the action, you might get new points. And this process repeats. If you have a shorter path, you might collect more points than if you used the longer path.
Nhờ hành động đó, bạn có thể được điểm mới. Và quá trình này lặp lại. Nếu có đường đi ngắn hơn, bạn có thể thu được nhiều điểm hơn so với đường đi dài hơn.
But if you take a very long time thinking to get a short path, you might still do worse than somebody who has an agent who chooses a longer path but can find it quickly.
Nhưng nếu bạn nghĩ rất lâu để có đường ngắn, bạn vẫn có thể thua người nào đó có tác tử chọn đường dài hơn nhưng tìm ra nó nhanh.
STUDENT
[INAUDIBLE] [LAUGHTER] PROFESSOR: Any other questions about logistics?
[KHÔNG NGHE RÕ] [CƯỜI] GIÁO SƯ: Còn câu hỏi nào khác về hậu cần không?
OK, let's start with the technical content of this lecture, adversarial search. This is about game playing in many ways. So let's take a look at game playing state of the art.
Được rồi, ta bắt đầu phần nội dung kỹ thuật của bài này, tìm kiếm đối kháng. Về nhiều mặt, đây là bài về chơi trò chơi. Hãy xem hiện trạng của AI chơi trò chơi.
Checkers — one of the first games for which there were good AI players. In the '50s, there was a computer player — decent. In '94, there was the first computer champion.
Cờ đam, một trong những trò chơi đầu tiên có người chơi AI khá tốt. Những năm 1950 đã có chương trình máy tính chơi khá ổn. Năm 1994 có nhà vô địch máy tính đầu tiên.
This computer champion took over from Marion Tinsley, who had for 40 years straight been the number one in the world in playing checkers.
Nhà vô địch máy tính này kế vị Marion Tinsley, người suốt 40 năm liền là số một thế giới về cờ đam.
So this was somebody who was just superior to everybody else in the world for 40 years. But then a computer came in and took it from him in '94.
Tức là một người vượt trội hơn tất cả những người còn lại trên thế giới suốt 40 năm. Nhưng rồi một máy tính xuất hiện và giành lấy ngôi vị đó năm 1994.
Then in 2007, checkers was "solved." What does it mean to be "solved" versus beating the best humans? Beating the best humans is something where it's just the level of play that you're at.
Rồi năm 2007, cờ đam được "giải xong". "Giải xong" nghĩa là gì so với việc thắng những người giỏi nhất? Thắng người giỏi nhất chỉ là nói về trình độ chơi của bạn.
Being "solved" will become more clear later in lecture, but it means that you know that you can force a win or force a draw if both sides play optimally.
"Giải xong" sẽ rõ hơn ở phần sau của bài, nhưng nó nghĩa là bạn biết mình có thể ép được thắng hoặc ép được hòa nếu cả hai bên chơi tối ưu.
And we'll find out more about what that means. But for now, let's already put it on the chart — checkers solved.
Chúng ta sẽ tìm hiểu kỹ hơn điều đó. Nhưng bây giờ hãy cứ ghi lên biểu đồ: cờ đam, đã giải xong.
Chess — '97, Deep Blue defeated Kasparov, the human champion, in a six-game match. Deep Blue was able to examine 200 positions per second at that time, with computers from 20 years ago.
Cờ vua: năm 1997, Deep Blue đánh bại Kasparov, nhà vô địch loài người, trong trận đấu sáu ván. Deep Blue xem xét được 200 thế cờ mỗi giây vào lúc đó, với máy tính của 20 năm trước.
Used a very sophisticated evaluation function, which we'll see more about today, and some undisclosed methods that IBM did not tell anybody.
Nó dùng một hàm đánh giá rất tinh vi, mà hôm nay chúng ta sẽ tìm hiểu thêm, và một số phương pháp không công bố mà IBM không nói cho ai.
And some searches were 40-ply deep, which we'll also see more about today, but that's searching very deep in your game tree of possible scenarios of how things could play out.
Có những lần tìm kiếm sâu tới 40 ply, điều này hôm nay cũng sẽ nói thêm, đó là tìm kiếm rất sâu trong cây trò chơi gồm các kịch bản có thể diễn ra.
Current programs are even better, but a little less historic because the best human player has been beaten.
Các chương trình hiện nay còn giỏi hơn, nhưng ít mang tính lịch sử hơn vì người chơi giỏi nhất đã bị đánh bại.
Chess is not solved in the sense that checkers is solved in that we don't know for sure who is guaranteed to win or whether it's guaranteed to be a draw if both players play optimally.
Cờ vua chưa được giải xong theo nghĩa như cờ đam, tức là ta không biết chắc ai chắc chắn thắng hay liệu chắc chắn sẽ hòa nếu cả hai chơi tối ưu.
A lot of people suspect it's a draw, but it's not been proven. Go — this is what we would say just a few years ago.
Nhiều người đoán là hòa, nhưng chưa được chứng minh. Cờ vây: đây là điều ta sẽ nói cách đây vài năm.
Human champions are now starting to be challenged by machines. And that's a recent thing as of the 2010s. Before the 2010s, humans wouldn't play against computer Go players, because it was just too boring.
Các nhà vô địch loài người giờ bắt đầu bị máy thách thức. Và đó là chuyện mới, từ những năm 2010. Trước những năm 2010, con người sẽ không chơi với máy tính chơi cờ vây, vì quá chán.
It would be an insult to be asked to spend your time that way. Why was it so hard to build good Go players?
Bị mời bỏ thời gian như vậy gần như là một sự xúc phạm. Vì sao khó xây dựng người chơi cờ vây giỏi?
So on Go, the branching factor is 300 roughly on average throughout the game. And that means there's a lot of possible future scenarios. So classic programs used knowledge bases.
Ở cờ vây, hệ số phân nhánh trung bình khoảng 300 trong suốt ván cờ. Nghĩa là có rất nhiều kịch bản tương lai có thể xảy ra. Các chương trình cổ điển dùng cơ sở tri thức.
But then a lot of advances started to come in through Monte Carlo.
Nhưng rồi nhiều tiến bộ bắt đầu đến từ Monte Carlo.
Expansion methods, which essentially means something along the lines of, from the current situation, if I let both players play randomly a few times, who wins more often?
Các phương pháp mở rộng, về cơ bản nghĩa là kiểu như: từ tình huống hiện tại, nếu cho hai bên chơi ngẫu nhiên vài lần thì ai thắng nhiều hơn?
And you use that to decide whether that's a good position for white or for black to be in. But this changed.
Và bạn dùng đó để quyết định đây có phải thế tốt cho bên trắng hay bên đen. Nhưng điều này đã thay đổi.
In 2016, AlphaGo defeated the human champion using still Monte Carlo tree search but also learned evaluation functions of a quality nobody had really anticipated were achievable anytime soon.
Năm 2016, AlphaGo đánh bại nhà vô địch loài người, vẫn dùng tìm kiếm cây Monte Carlo nhưng còn học được các hàm đánh giá với chất lượng mà không ai thực sự nghĩ có thể đạt được sớm như vậy.
And again, we'll see more about evaluation functions in this lecture. But that's where the big surprise was. A lot of people thought Go was maybe still 10, 20, 30 years away.
Và một lần nữa, ta sẽ học thêm về hàm đánh giá trong bài này. Nhưng đó là chỗ gây bất ngờ lớn. Nhiều người nghĩ cờ vây có thể còn 10, 20, 30 năm nữa.
But the quality of evaluation functions completely changed that. And then Pac-Man — that's what we all want to know here. Still have to figure it out.
Nhưng chất lượng của các hàm đánh giá đã thay đổi hoàn toàn điều đó. Còn Pac-Man: đó là điều tất cả chúng ta muốn biết. Vẫn phải tìm ra.
Maybe we'll figure it out by the end of the semester. Open problem for now. OK, so let's take a look at Pac-Man in action.
Có thể ta sẽ tìm ra vào cuối học kỳ. Hiện vẫn là bài toán mở. Được rồi, hãy xem Pac-Man hoạt động.
So here is — where is the game? There it is. Here is a game situation. Now there are ghosts.
Đây là... trò chơi đâu rồi nhỉ? Đây rồi. Đây là một tình huống trong trò chơi. Giờ có các con ma.
Let's watch a mastermind Pac-Man in action.
Hãy xem một Pac-Man bậc thầy hoạt động.
In the terminal window, you see a bunch of competition happening, which we'll understand more about later.
Trong cửa sổ terminal, bạn thấy nhiều tính toán đang diễn ra, mà sau này ta sẽ hiểu rõ hơn.
For now, the thing to pay attention to is that indeed it is somehow avoiding the ghosts, eating food pellets, and periodically eating one of the power pellets.
Còn bây giờ, điều cần chú ý là quả thật nó đang né các con ma, ăn các viên thức ăn, và thỉnh thoảng ăn một viên năng lượng.
And when it eats power pellets, it can eat ghosts and get extra score for eating the ghosts at that time.
Và khi ăn viên năng lượng, nó có thể ăn ma và được thêm điểm khi ăn ma vào lúc đó.
OK. That's how I mastermind Pac-Man.
Được rồi. Đó là Pac-Man bậc thầy của tôi.
And that's what we we're going to be after in this lecture, to try to understand what it takes to build something like this but while not having to write lines of code of the type "if a ghost is nearby on that side, move in the other direction.
Và đó là điều ta hướng tới trong bài này, là hiểu cần gì để xây dựng một thứ như vậy mà không phải viết những dòng mã kiểu "nếu có ma ở gần phía đó, hãy đi hướng ngược lại.
If there's a power pellet in that direction, move in that direction."
Nếu có viên năng lượng ở hướng đó, hãy đi hướng đó."
We want it to reason about the consequences of its actions and the ghosts' actions to infer from that what is the right thing to do.
Ta muốn nó suy luận về hệ quả của hành động của nó và của các con ma, rồi từ đó suy ra việc đúng cần làm là gì.
OK, so let's first do a quick step back and talk about types of games. There are many different types of games.
Được rồi, trước hết hãy lùi lại một chút và nói về các loại trò chơi. Có rất nhiều loại trò chơi khác nhau.
You've already probably in your free time played a lot of games — computer games, board games, and so forth. What are some axes along which we can categorize them?
Có lẽ lúc rảnh các bạn đã chơi nhiều trò: trò chơi máy tính, trò chơi bàn cờ, v.v. Ta có thể phân loại chúng theo những trục nào?
Well, one axis is whether they're deterministic or stochastic. So an example of deterministic would be checkers, or chess, or Go.
Một trục là chúng tất định hay ngẫu nhiên. Ví dụ tất định là cờ đam, cờ vua, hay cờ vây.
Example of stochastic would be backgammon, where there is a roll of dice that determines which moves are available to you. Then the number of players — one, two, or more players.
Ví dụ ngẫu nhiên là cờ backgammon, nơi có việc tung xúc xắc quyết định những nước đi bạn có thể thực hiện. Tiếp theo là số người chơi — một, hai, hoặc nhiều người chơi.
Solitaire would be a canonical game to play alone. Two players — checkers, chess, Go, backgammon. More players — poker. A lot of board games have more than two players.
Solitaire là ví dụ điển hình của trò chơi một người. Hai người chơi — cờ đam, cờ vua, cờ vây, backgammon. Nhiều người chơi — poker. Nhiều trò chơi bàn cờ có hơn hai người chơi.
Then another axis along which you could categorize games is whether they are zero-sum or not. We'll see a little more on that very soon.
Một trục khác để phân loại trò chơi là chúng có tổng bằng không hay không. Chúng ta sẽ nói kỹ hơn về điều này rất sớm.
But the general notion here is, are you all playing against each other or is there some notion that you're not all playing against each other?
Nhưng ý chung ở đây là: có phải tất cả mọi người đều chơi đối kháng nhau hay có khái niệm rằng không phải tất cả đều đối kháng nhau?
And then there is a question of perfect information or not. Do you know everything about the current state of the game when you decide on your action? Or do you not know everything?
Rồi còn câu hỏi về thông tin hoàn hảo hay không. Bạn có biết mọi thứ về trạng thái hiện tại của trò chơi khi chọn hành động của mình không? Hay là bạn không biết hết mọi thứ?
An example of knowing everything would be chess, checkers, Go. You see the board, and that's all there is to it. An example of not knowing everything would be poker.
Ví dụ biết mọi thứ là cờ vua, cờ đam, cờ vây. Bạn nhìn bàn cờ, và chỉ có vậy. Ví dụ không biết hết mọi thứ là poker.
You don't know the cards of the other players.
Bạn không biết bài của những người chơi khác.
So that's an imperfect information game where you have to think about possible scenarios — what cards might they be holding; as a function of what cards they're holding, what might I want to do; and so forth.
Đó là một trò chơi thông tin không hoàn hảo mà bạn phải nghĩ đến các kịch bản có thể xảy ra — họ có thể đang cầm những lá bài nào; tùy theo những lá bài họ đang cầm, mình nên làm gì; và cứ thế.
What we want in this setting — any one of those settings — is somehow an approach that allows us to calculate a strategy, a policy that tells us what to do in a current situation and then again in future situations.
Điều chúng ta muốn trong bối cảnh này — bất kỳ bối cảnh nào trong số đó — là một cách tiếp cận cho phép ta tính ra một chiến lược, một chính sách cho biết phải làm gì trong tình huống hiện tại và rồi trong các tình huống tương lai.
So this is going to be a little different, the result of this, than what we get in regular planning. In regular planning, we just generate a sequence of actions that we can just execute.
Vì vậy kết quả ở đây sẽ hơi khác so với những gì ta có trong lập kế hoạch thông thường. Trong lập kế hoạch thông thường, ta chỉ tạo ra một chuỗi hành động rồi cứ thế thực thi.
But here, because there's an opponent that we don't control very often, we need to find a strategy which prescribes what to do as a function of the situation we are currently in or going to be in.
Nhưng ở đây, vì có một đối thủ mà ta thường không điều khiển được, ta cần tìm một chiến lược quy định phải làm gì tùy theo tình huống mà ta đang ở hoặc sắp rơi vào.
Well, folks, in deterministic games for now, we'll see stochastic games next lecture.
Nào các bạn, hiện giờ ta xét trò chơi tất định, trò chơi ngẫu nhiên sẽ học ở bài sau.
Now, the same thing we've done with search and with CSPs is that we want to find a unified interface for all these real-world problems such that once we have the unified interface, we can then have one implementation of an algorithm that applies to any of the real-world problems that's cast into this interface.
Cũng như với tìm kiếm và CSP, ta muốn có một giao diện thống nhất cho tất cả các bài toán thực tế này, sao cho khi đã có giao diện thống nhất đó, ta có thể có một cài đặt thuật toán duy nhất áp dụng cho bất kỳ bài toán thực tế nào được đưa vào giao diện này.
So here's one way to formalize the interface for games. There is a set of states and a start state as 0. There is a set of players which often take turns.
Đây là một cách hình thức hóa giao diện cho trò chơi. Có một tập các trạng thái và một trạng thái bắt đầu s0. Có một tập người chơi, thường là luân phiên nhau.
Definitely in what we consider, they take turns. Then there is a set of actions. This can depend on which player you are, what actions are available to you.
Trong phạm vi ta xét thì chắc chắn là luân phiên. Rồi có một tập các hành động. Tập này có thể phụ thuộc vào bạn là người chơi nào, bạn có những hành động nào.
There is a transition function, which is a lot like a successor function in regular search — state and action to next state. There is a terminal test.
Có một hàm chuyển trạng thái, rất giống hàm kế tiếp trong tìm kiếm thông thường — từ trạng thái và hành động ra trạng thái kế tiếp. Có một phép kiểm tra kết thúc.
Is the game over or not in the current situation? And then there are terminal utilities. This is maybe the newest type of thing.
Trong tình huống hiện tại, trò chơi đã kết thúc chưa? Và rồi có các độ hữu dụng tại trạng thái kết thúc. Đây có lẽ là thứ mới nhất.
But what we're going to do is every outcome of a game will be scored. Simple games might have just three types of outcomes — win, draw, or lose.
Nhưng điều ta làm là mỗi kết cục của trò chơi sẽ được chấm điểm. Trò chơi đơn giản có thể chỉ có ba loại kết cục — thắng, hòa, hoặc thua.
But more complicated games might have a wider range of outcomes. For example, in poker, the amount of money you make might be the utility assigned to an outcome.
Nhưng trò chơi phức tạp hơn có thể có nhiều kết cục đa dạng hơn. Ví dụ trong poker, số tiền bạn kiếm được có thể là độ hữu dụng gán cho một kết cục.
And then it could be a range of values rather than just win, lose, or draw. Solution to something put into this interface is a policy.
Và đó có thể là một khoảng giá trị chứ không chỉ là thắng, thua hay hòa. Lời giải cho bài toán đưa vào giao diện này là một chính sách.
And a policy is something that tells you for every possible situation you could be in what action you should be taking.
Và chính sách là thứ cho bạn biết với mọi tình huống có thể gặp, bạn nên thực hiện hành động nào.
What's this zero-sum thing that we're going to be focusing on in this lecture? In zero-sum games, agents have opposite utilities. They have to fight over one resource or set of resources that's available.
Vậy thứ tổng bằng không mà ta sẽ tập trung trong bài này là gì? Trong trò chơi tổng bằng không, các tác tử có độ hữu dụng đối nghịch nhau. Họ phải tranh nhau một tài nguyên hoặc một tập tài nguyên đang có.
And if one agent gets it, the other one doesn't get it. And so the more the other one gets, the less you get.
Nếu một tác tử có được thì tác tử kia không có. Và đối phương được càng nhiều thì bạn được càng ít.
This allows us to think of utilities as not separate utilities for each agent for each situation. We just need one number. We have the utility for agent 1.
Điều này cho phép ta nghĩ về độ hữu dụng không phải là các độ hữu dụng riêng cho từng tác tử ở từng tình huống. Ta chỉ cần một con số. Ta có độ hữu dụng của tác tử 1.
And then agent 2 we know has the opposite utility, the negative of the utility of agent 1. So this models situations where it's pure competition. It's one agent against the other.
Và tác tử 2 thì ta biết có độ hữu dụng ngược lại, tức là số âm của độ hữu dụng của tác tử 1. Vì vậy nó mô hình hóa các tình huống cạnh tranh thuần túy. Tác tử này đối đầu với tác tử kia.
There are other types of games — and we'll see some of them in the future — where agents have independent utilities. And sometimes this opens up more opportunities.
Có những loại trò chơi khác — và ta sẽ gặp một vài loại trong tương lai — trong đó các tác tử có độ hữu dụng độc lập. Và đôi khi điều này mở ra nhiều cơ hội hơn.
This opens up opportunities for win-win outcomes where you say, I might not care so much about the orange ones. I don't care about the green ones. But the other way around, you do care.
Nó mở ra cơ hội cho kết cục đôi bên cùng có lợi, khi bạn nói: tôi có thể không quan tâm lắm đến những chấm cam. Tôi không quan tâm đến những chấm xanh lá. Nhưng ngược lại, bạn thì có quan tâm.
And so here, blue agent collects all the green ones. Red agent collects all the orange ones. And in the process, they're helping each other, making it easier to collect the ones they're looking for.
Và ở đây, tác tử xanh dương thu hết các chấm xanh lá. Tác tử đỏ thu hết các chấm cam. Và trong quá trình đó, họ giúp lẫn nhau, khiến việc thu thập thứ mình cần dễ hơn.
Many real-world scenarios, in some sense, are of this type. But often, the essence can still be simplified in many situations to zero-sum games. And those are the ones we're studying today.
Theo một nghĩa nào đó, nhiều tình huống thực tế thuộc loại này. Nhưng thường thì bản chất vẫn có thể được đơn giản hóa về trò chơi tổng bằng không trong nhiều trường hợp. Và đó là loại ta nghiên cứu hôm nay.
OK, so to solve zero-sum games, we'll use a set of approaches called adversarial search.
Để giải trò chơi tổng bằng không, ta sẽ dùng một nhóm phương pháp gọi là tìm kiếm đối kháng.
It's something where you, as an agent, have to think about as a function of what you do what will the other agent do who's working against you, what opportunities will you then see after that, what will they see after that, and keep thinking about what if, if, if, if, and so forth through, ideally, the end of the game.
Với tư cách một tác tử, bạn phải nghĩ xem tùy theo việc bạn làm, tác tử kia, người đang chống lại bạn, sẽ làm gì, rồi bạn sẽ thấy những cơ hội nào sau đó, họ sẽ thấy gì sau đó, và cứ tiếp tục nghĩ nếu thế, nếu thế, nếu thế, nếu thế, và cứ vậy, lý tưởng là đến hết trò chơi.
So let's first look at something we're already familiar with, which is a single-agent game tree. A lot like search, but we'll formalize it as a game tree.
Trước tiên hãy xem thứ ta đã quen thuộc, đó là cây trò chơi cho một tác tử. Rất giống tìm kiếm, nhưng ta sẽ hình thức hóa nó thành cây trò chơi.
And then from there, we'll generalize to multiple agents — two agents for today. OK, here is Pac-Man trying to collect food — simple maze. Two actions available — west or east.
Và từ đó, ta sẽ tổng quát hóa sang nhiều tác tử — hai tác tử cho bài hôm nay. Đây là Pac-Man đang đi ăn thức ăn — trong một mê cung đơn giản. Có hai hành động: sang trái (west) hoặc sang phải (east).
Then after that, again two actions available and so forth. All the way on the right, it's done. The other ones, it can still keep going.
Sau đó lại có hai hành động nữa, và cứ thế tiếp tục. Ở tận cùng bên phải thì trò chơi kết thúc. Các nhánh khác thì vẫn có thể đi tiếp.
In these game scenarios, with each terminal state, we associate a utility.
Trong các trò chơi này, với mỗi trạng thái kết thúc, ta gắn một độ hữu dụng.
So for example, this has a utility of 8 — which is a standard scoring we have in our Pac-Man games — minus 1 for every time step spent, every action taken, plus 10 for every pellet eaten.
Ví dụ, trạng thái này có độ hữu dụng là 8 — theo cách tính điểm chuẩn trong trò chơi Pac-Man của chúng ta — trừ 1 cho mỗi bước thời gian, mỗi hành động thực hiện, cộng 10 cho mỗi viên thức ăn ăn được.
So two steps, one pellet eaten, that's 10 minus 2, 8. And maybe the numbers for the other ones end up being something like 2, 0, 2, 6, 4, 6, and so forth.
Hai bước, ăn một viên, tức là 10 trừ 2, được 8. Và các con số còn lại có thể là 2, 0, 2, 6, 4, 6, và cứ thế.
If you're a single-agent, you control where you go in this tree. So things are actually relatively easy. You would say, OK, let me look at the tree. What do I see here?
Nếu chỉ có một tác tử, bạn tự kiểm soát việc đi đâu trong cây này. Nên mọi thứ khá dễ. Bạn sẽ nói: để tôi nhìn cây xem. Tôi thấy gì ở đây?
Well, 8 is the highest. So I should do this and then this. And that solves the game. But let's formalize this a little bit more.
À, 8 là cao nhất. Vậy tôi đi hướng này rồi hướng này. Thế là giải xong trò chơi. Nhưng hãy hình thức hóa thêm một chút.
So each state in the game has a value associated with it, which is the best achievable outcome from that state. So for example, for this data over here, that's very easy.
Mỗi trạng thái trong trò chơi có một giá trị đi kèm, là kết quả tốt nhất có thể đạt được từ trạng thái đó. Ví dụ, với trạng thái ở đây thì rất dễ.
It's a terminal state. The best achievable outcome? Well, there's only one outcome from that state. It's that you terminate the game, and you get 8.
Đó là trạng thái kết thúc. Kết quả tốt nhất có thể đạt được? Chỉ có một kết quả từ trạng thái đó. Là trò chơi kết thúc và bạn nhận 8.
So the value of this state is 8. How about a state like this one? What would be the value of that state? Well, it's the best you can achieve starting from that state.
Vậy giá trị của trạng thái này là 8. Còn trạng thái như thế này thì sao? Giá trị của trạng thái đó là bao nhiêu? Đó là kết quả tốt nhất bạn có thể đạt được bắt đầu từ trạng thái đó.
And it looks like from looking at this tree that you can end up with a 4, with a 6, or with an 8. 8 is the best achievable.
Nhìn vào cây này thì thấy bạn có thể kết thúc với 4, 6 hoặc 8. 8 là tốt nhất có thể đạt được.
And so the value here would also be 8. How about the value of this state over here? Well, it looks like there's opportunities for a 2, a 0, a 2, a 6.
Nên giá trị ở đây cũng là 8. Còn giá trị của trạng thái ở đây? Có vẻ có các khả năng là 2, 0, 2, 6.
6 is the highest. So the value would be 6. How about this one at the top here? Well, you can either go to the left or to the right.
6 là cao nhất. Vậy giá trị là 6. Còn nút ở trên cùng này? Bạn có thể đi sang trái hoặc sang phải.
Either you end up with a value of 6 or with a value of 8. 8 is better. You control that. So 8 would be the value of your state over here.
Hoặc được giá trị 6, hoặc được giá trị 8. 8 tốt hơn. Bạn là người quyết định. Nên giá trị của trạng thái này là 8.
And so the way we did this is that for non-terminal states, we looked at the children and took the max of the values of the children, because we control where we go and that's the value of that non-terminal state.
Vậy cách ta làm là với các trạng thái không kết thúc, ta xem các nút con và lấy max của các giá trị của con, vì ta kiểm soát việc đi đâu, và đó chính là giá trị của trạng thái không kết thúc đó.
Let's now generalize this to adversarial games. So here we have Pac-Man and ghosts. They're working against each other. Pac-Man tries to maximize score.
Giờ hãy tổng quát hóa sang các trò chơi đối kháng. Ở đây ta có Pac-Man và các con ma. Họ chống lại nhau. Pac-Man cố cực đại hóa điểm số.
The ghost wants to minimize score by eating Pac-Man. So let's see what happens. First, Pac-Man gets to take an action. So we're assuming alternating moves here.
Con ma muốn cực tiểu hóa điểm bằng cách ăn Pac-Man. Hãy xem chuyện gì xảy ra. Đầu tiên, Pac-Man được đi một hành động. Ở đây ta giả sử các lượt đi luân phiên.
Could be going left or right. Then after that, the ghost gets to take an action. Then after that, things keep repeating.
Có thể đi trái hoặc phải. Sau đó, con ma được đi một hành động. Rồi mọi thứ cứ lặp lại.
And then for each sequence of alternating actions, at some point the game might end. And then with the end of that game, some utility is associated.
Và với mỗi chuỗi hành động luân phiên, đến một lúc nào đó trò chơi có thể kết thúc. Và khi trò chơi kết thúc, sẽ có một độ hữu dụng đi kèm.
If Pac-Man survives and has eaten all the food pellets, it would probably be a high score. If Pac-Man doesn't survive, it'd be a very low score.
Nếu Pac-Man sống sót và ăn hết các viên thức ăn, thì có lẽ điểm sẽ cao. Nếu Pac-Man không sống sót, điểm sẽ rất thấp.
So let's zone in on a smaller version of this to annotate this with some concepts. Let's assume that the game is over after each player has made a move.
Hãy xét một phiên bản nhỏ hơn của trò chơi này để chú thích một số khái niệm. Giả sử trò chơi kết thúc sau khi mỗi người chơi đi một nước.
This is not how the real game works, but just to get it on a slide. This is a very short game — one move for Pac-Man, one move for the ghost.
Trò chơi thật không chạy như vậy, chỉ là để vừa vào một slide. Đây là một trò chơi rất ngắn — một nước cho Pac-Man, một nước cho con ma.
And here are the scores we have associated with that. There is a minus 8, a minus 5, a minus 10, a plus 8. You might say, well, I'd love the plus 8.
Và đây là các điểm số gắn với nó. Có trừ 8, trừ 5, trừ 10, cộng 8. Bạn có thể nghĩ: tôi thích cộng 8.
That sounds pretty good to me. And you might say, well, OK, I should try to get here.
Nghe rất ổn với tôi. Và bạn nghĩ: được, tôi nên cố đến đây.
But that's not how it works in this kind of game, because actually the ghost controls this node.
Nhưng trong loại trò chơi này không phải vậy, vì thật ra con ma kiểm soát nút này.
And if you were to end up in this node, ghost would prefer to have the lowest possible outcome.
Và nếu bạn đến nút này, con ma sẽ muốn kết quả thấp nhất có thể.
So ghost would say, I'm going to do this, and it's going to end up with minus 10, such the value of this node over here is minus 10.
Con ma sẽ nói: tôi sẽ đi hướng này, và kết quả sẽ là trừ 10, nên giá trị của nút này là trừ 10.
The plus 8 is just there. It might be tempting you. You might want to try to get it. But you're just not going to get it.
Cộng 8 chỉ nằm đó thôi. Nó có thể cám dỗ bạn. Bạn có thể muốn cố lấy nó. Nhưng bạn sẽ không lấy được.
The ghost is not going to give it to you. So this value here is minus 10. Similarly, on the other side there's a minus 8, minus 5.
Con ma sẽ không nhường cho bạn. Vậy giá trị ở đây là trừ 10. Tương tự, ở phía bên kia có trừ 8, trừ 5.
Ghost working against you will decide it's going to be minus 8. So the value over here is minus 8.
Con ma chống lại bạn sẽ quyết định là trừ 8. Nên giá trị ở đây là trừ 8.
Going one level up — again, from bottom to top — now, what's the value of this node over here?
Lên một tầng nữa, vẫn đi từ dưới lên trên — giờ giá trị của nút ở đây là bao nhiêu?
Well, it's the maximum of the values of the leaves — not the leaves, but nodes below it. What's below it? An option to get minus 8 and an option to get minus 10.
Đó là giá trị lớn nhất trong các giá trị của lá — không phải lá, mà là các nút bên dưới nó. Bên dưới có gì? Một lựa chọn được trừ 8 và một lựa chọn được trừ 10.
Minus 8 is better. So the value here is minus 8. Pac-Man will choose this move, after which the ghost will choose this move.
Trừ 8 tốt hơn. Vậy giá trị ở đây là trừ 8. Pac-Man sẽ chọn nước đi này, sau đó con ma sẽ chọn nước đi này.
And that's how the game will play out if both players are playing optimally. Formalizing this a little bit, terminal states, we have known values.
Và trò chơi sẽ diễn ra như vậy nếu cả hai người chơi đều chơi tối ưu. Hình thức hóa một chút, với các trạng thái kết thúc, ta đã biết giá trị.
v of s is whatever we annotated it with when this slide was not written on yet. Then states under opponent's control, we have a minimization happening of the utility.
v của s chính là giá trị ta đã ghi lên khi slide này chưa được viết gì. Tiếp theo, các trạng thái do đối thủ điều khiển thì ta lấy cực tiểu của độ hữu dụng.
And states under our own control, for the maximizer agent, we have a maximization happening. And again, keep in mind there is a plus 8 here, but we're not going to get that.
Còn các trạng thái do ta điều khiển, tức tác tử cực đại hóa, thì ta lấy cực đại. Và nhớ rằng ở đây có một giá trị cộng 8, nhưng ta sẽ không đạt được nó.
What we're actually going to get is this outcome over here. OK, let's look at a very simple board game — Tic-Tac-Toe. Has anyone not played Tic-Tac-Toe before?
Thứ ta thực sự nhận được là kết quả ở bên này. OK, ta xét một trò chơi bàn cờ rất đơn giản, Tic-Tac-Toe. Có ai chưa từng chơi Tic-Tac-Toe không?
OK, so everybody knows Tic-Tac-Toe. You need to get three in a row. It starts with an empty board. You can choose any of the nine squares to put your mark in.
OK, vậy ai cũng biết Tic-Tac-Toe. Bạn cần xếp được ba ô liên tiếp. Bắt đầu với bàn cờ trống. Bạn chọn một trong chín ô bất kỳ để đánh dấu.
Then the other player goes. And this process repeats until either one player has three in a row or the board is full and then the game is over with a draw.
Rồi đến lượt người chơi kia. Quá trình này lặp lại cho đến khi một người có ba ô liên tiếp, hoặc bàn cờ đầy, và khi đó ván cờ kết thúc với kết quả hòa.
What is the value of this node over here? Well, you have to think about this. You have to think about, well, I mean, there is a plus 1 at the bottom somewhere.
Giá trị của nút này ở đây là bao nhiêu? Các em phải suy nghĩ một chút. Ở dưới đáy chắc chắn có chỗ có giá trị cộng 1.
There's many plus 1's for various outcomes. There's various 0's and various negative 1's. But what can you get to when you're playing against an opponent who's really playing cleverly against you?
Có nhiều kết quả cộng 1 khác nhau. Có nhiều kết quả 0 và nhiều kết quả âm 1. Nhưng ta đạt được gì khi chơi với một đối thủ chơi rất khôn ngoan để chống lại ta?
Well, one thing we definitely know is that either the value here is going to be negative 1, or 0, or plus 1.
Có một điều ta chắc chắn biết là giá trị ở đây sẽ là âm 1, hoặc 0, hoặc cộng 1.
It's not going to be anything else, because the values are obtained by just taking maxes and mins of values that are leafing out to leaf nodes.
Không thể là gì khác, vì các giá trị có được chỉ bằng cách lấy max và min của các giá trị từ các nút lá đi lên.
And by taking maxes and mins of negative 1, 0, and plus 1, you never end up with anything else than those three. But which one it is?
Và lấy max, min của âm 1, 0 và cộng 1, thì không bao giờ ra giá trị nào ngoài ba giá trị đó. Nhưng nó là giá trị nào?
Well, for that, you have to work through the game tree. You figure out the entire tree.
Muốn biết, ta phải duyệt qua cây trò chơi. Bạn xác định toàn bộ cây.
You work through the process that we just did on the previous slide here, taking maxes and mins at each respective node till you're all the way out the top.
Bạn làm theo quá trình ta vừa làm ở slide trước, lấy max và min tại từng nút tương ứng cho đến khi lên tới đỉnh.
And it turns out that if you work through this carefully, you find out that the value is 0, which means that if you're two smart people who are going to play this game, you know ahead of time it's going to be a draw.
Và hóa ra nếu tính cẩn thận, bạn thấy giá trị là 0, nghĩa là nếu hai người thông minh chơi trò này, ta biết trước kết quả sẽ hòa.
And that's actually what it means when I referred to at the very beginning of this lecture for a game to be "solved."
Và đó chính là ý nghĩa của điều tôi nhắc ngay đầu bài giảng, khi nói một trò chơi được "giải xong".
The game of Tic-Tac-Toe is solved because we know that if both players play optimally, the value of the top node is 0. Same thing is true for checkers.
Trò Tic-Tac-Toe đã được giải vì ta biết nếu cả hai người chơi tối ưu, giá trị của nút trên cùng là 0. Cờ đam cũng vậy.
People have worked through it with more efficient algorithms than just drawing out the whole game tree but have worked through it in efficient ways to conclude that for checkers it's also 0, I believe.
Người ta đã giải nó bằng các thuật toán hiệu quả hơn việc vẽ ra toàn bộ cây trò chơi, tức là giải theo những cách hiệu quả để kết luận rằng cờ đam cũng là 0, tôi nghĩ vậy.
But I'm not 100% sure whether it's 0 or 1. So that's what it means to be "solved." OK.
Nhưng tôi không chắc 100% là 0 hay 1. Vậy đó là nghĩa của "được giải xong". OK.
So now let's design an algorithm that is more computer executable than us looking at trees. Yes.
Giờ ta thiết kế một thuật toán máy tính thực thi được, thay vì ta nhìn cây. Mời em.
STUDENT
Back to the last slide for a second.
Cho em quay lại slide trước một chút.
PROFESSOR
OK.
OK.
STUDENT
A game with the possibility for an arbitrarily long cycle of states, how could you end up solving it?
Với một trò chơi có khả năng có chu trình trạng thái dài tùy ý, thì làm sao giải được ạ?
PROFESSOR
OK, so the question is, what if there is a way to keep playing? So the tree would be infinite in that scenario, right?
OK, câu hỏi là nếu có cách để chơi mãi thì sao? Khi đó cây sẽ vô hạn, đúng không?
For example, what if in Tic-Tac-Toe maybe you could erase something and then you could keep going?
Ví dụ, nếu trong Tic-Tac-Toe ta có thể xóa một nước đi rồi tiếp tục chơi?
So a lot of games have setups where you cannot repeat the same move over and over to avoid getting into loops.
Nhiều trò chơi được thiết lập để không thể lặp lại cùng một nước đi mãi, nhằm tránh bị lặp vòng.
But if there is a possibility to get into a loop that indeed the tree could keep going, and then you'd somehow have to — well, you then have to decide what that even means.
Nhưng nếu có khả năng rơi vào vòng lặp thì đúng là cây có thể kéo dài mãi, và khi đó bằng cách nào đó ta phải... à, ta phải quyết định điều đó nghĩa là gì.
If both players decide to keep playing forever, is that a draw or — I mean, it's not very clear what the definition is of what that means if both players just keep playing forever.
Nếu cả hai người quyết định chơi mãi mãi, thì đó là hòa hay... ý tôi là, không rõ định nghĩa của việc đó là gì nếu cả hai người chỉ tiếp tục chơi mãi mãi.
But you somehow have to come up with a definition of what that means. Let's say you call it a draw.
Nhưng bằng cách nào đó ta phải đưa ra định nghĩa cho nó. Giả sử ta coi đó là hòa.
That's what some games might do, are just forbid it to go in the same cycle again. Then all of a sudden, you have something again.
Một số trò chơi làm như vậy, tức là cấm đi lại cùng một chu trình. Thế là đột nhiên ta lại có cây hữu hạn.
Because now we've gone through a cycle a certain number of times, that's the limit. Now it's a draw. They could begin so the trees are infinite in other ways without having repeats.
Vì giờ ta đã đi qua một chu trình một số lần nhất định, đó là giới hạn. Khi đó là hòa. Cây cũng có thể vô hạn theo cách khác mà không có lặp lại.
Maybe you have some kind of infinite board you can play on in principle, and you can keep expanding in many, many directions.
Có thể bạn có một bàn cờ vô hạn mà về nguyên tắc có thể chơi trên đó, và bạn có thể mở rộng theo rất nhiều hướng.
Then you might need a little bit extra machinery compared to what we're seeing today in lecture. So we're not going to specifically look at that.
Khi đó ta cần thêm một chút công cụ so với những gì thấy trong bài hôm nay. Nên ta sẽ không xét trường hợp đó.
OK, so let's formalize this. We've been looking at deterministic zero-sum games. Examples are Tic-Tac-Toe, chess, checkers. One player maximizes the utility at the leaf nodes.
OK, giờ ta hình thức hóa việc này. Ta đang xét các trò chơi tổng bằng không, tất định. Ví dụ là Tic-Tac-Toe, cờ vua, cờ đam. Một người chơi cực đại hóa độ hữu dụng ở các nút lá.
The other one minimizes it. In minimax search, we have a state space search tree. Players alternate turns. And to compute minimax values at each node, we can work from the bottom to the top.
Người kia cực tiểu hóa nó. Trong tìm kiếm minimax, ta có cây tìm kiếm không gian trạng thái. Các người chơi luân phiên lượt. Và để tính giá trị minimax tại mỗi nút, ta đi từ dưới lên trên.
For example, for this here, we have minimizer says this is 2. Minimizer says this is 5. And then the maximizer knows that the value at the top is 5.
Ví dụ ở đây, bên cực tiểu nói giá trị này là 2. Bên cực tiểu nói giá trị này là 5. Rồi bên cực đại biết giá trị ở đỉnh là 5.
And the game would be played out this way. That's the minimax solution to the game, with both players playing minimax strategy.
Và ván cờ sẽ diễn ra theo cách này. Đó là lời giải minimax của trò chơi, khi cả hai người chơi theo chiến lược minimax.
This is illustrated on the slides. How do we formalize this? Well, at a max node, what we're doing is we're initializing our estimate of the value of that node as negative infinity.
Điều này được minh họa trên slide. Ta hình thức hóa việc này như thế nào? Tại một nút max, việc ta làm là khởi tạo giá trị ước lượng của nút đó bằng âm vô cùng.
And then we start inspecting all the children, see what the value are of the successor nodes, and if they're higher than what we have so far, we increase and ultimately return the maximum value we've seen among all successors.
Rồi ta bắt đầu duyệt tất cả các nút con, xem giá trị của các nút kế tiếp là bao nhiêu, và nếu chúng cao hơn giá trị ta đang có, ta cập nhật tăng lên và cuối cùng trả về giá trị lớn nhất mà ta thấy trong tất cả các nút kế tiếp.
Min, that's the exact counterpart. Start out plus infinity when you've seen nothing. And then whenever you have examined a new successor, you check if it's better for the minimizer than what you've seen before.
Min thì hoàn toàn ngược lại. Bắt đầu từ dương vô cùng khi chưa thấy gì. Và mỗi khi xét một nút kế tiếp mới, bạn kiểm tra xem nó có tốt hơn cho người chơi min so với những gì đã thấy trước đó không.
And if so, you update the value. And you keep looping till you have gone through everything.
Nếu có, bạn cập nhật giá trị. Và bạn lặp cho đến khi duyệt hết mọi thứ.
Of course, if you just use this, this is a recursion where you go from min to max from max to min and keep going. There is no base case here.
Tất nhiên, nếu chỉ dùng như vậy thì đây là một đệ quy đi từ min sang max, từ max sang min và cứ thế tiếp tục. Ở đây không có trường hợp cơ sở.
So this actually wouldn't really work. So in your code, you'll have to install a base case of some type so you'd have dispatch function that computes value of a state.
Nên thực ra nó sẽ không chạy được. Vì vậy trong code, bạn phải cài đặt một trường hợp cơ sở nào đó, tức là bạn có một hàm điều phối tính giá trị của một trạng thái.
First checks, am I hitting a base case? If I'm hitting a base case that is a terminal state, return the value of that terminal state.
Trước tiên kiểm tra: mình có gặp trường hợp cơ sở không? Nếu gặp trường hợp cơ sở, tức là trạng thái kết thúc, thì trả về giá trị của trạng thái kết thúc đó.
If not, then check what kind of node I'm in. Am I in a maximizer node? Then call max. If I am in a minimizer node, call the min value function and execute that.
Nếu không, thì kiểm tra xem mình đang ở loại nút nào. Mình có đang ở nút max không? Thì gọi max. Nếu đang ở nút min, gọi hàm min value và thực thi nó.
And to the earlier question, if the game keeps going forever, then some of these occasions you will never hit the terminal state, and you'll have to somehow decide how your algorithm is going to stop early.
Còn về câu hỏi trước, nếu trò chơi cứ tiếp diễn mãi, thì trong một số trường hợp bạn sẽ không bao giờ gặp trạng thái kết thúc, và bạn sẽ phải quyết định bằng cách nào đó khi nào thuật toán dừng sớm.
It might say, after I am a million moves deep in the game, I'm just calling it done on this branch and have some kind of resolution calling it nevertheless a terminal state because it's been going for so long.
Nó có thể nói: sau khi đi sâu một triệu nước trong trò chơi, tôi dừng ở nhánh này và có một cách quy ước nào đó để vẫn coi nó là trạng thái kết thúc vì nó đã kéo dài quá lâu.
STUDENT
Question.
Em có câu hỏi.
PROFESSOR
Question — yes.
Câu hỏi, mời em.
STUDENT
So if there's an algorithm, are we [INAUDIBLE] to move step-by-step? For example, the one Pac-Man question where we first moved Pac-Man then the ghost movement, is it a different type on all [INAUDIBLE]??
Nếu có một thuật toán, liệu chúng ta có [KHÔNG NGHE RÕ] đi từng bước một không? Ví dụ, câu hỏi Pac-Man mà ta di chuyển Pac-Man trước rồi mới đến ma di chuyển, thì nó có là một loại khác so với [KHÔNG NGHE RÕ] không ạ?
PROFESSOR
Correct. In everything we're looking at here, it's going to be turn-based games, where the moves are alternating between players. There are other types of games where players takes decisions simultaneously.
Đúng vậy. Trong mọi thứ ta xét ở đây, đều là trò chơi theo lượt, trong đó các nước đi luân phiên giữa các người chơi. Có những loại trò chơi khác mà người chơi ra quyết định đồng thời.
We're not going to look at those in the current two lectures.
Ta sẽ không xét chúng trong hai bài giảng này.
OK, now we have an algorithm. This is essentially the counterpart of our tree search or graph search from when we did search in the first — well, in lecture 2 and 3.
Được rồi, giờ ta đã có một thuật toán. Về bản chất nó tương ứng với tìm kiếm trên cây hoặc tìm kiếm trên đồ thị khi ta học về tìm kiếm ở bài đầu, à ở bài 2 và 3.
And we can now run this. This is a lot like depth-first search. It's just traversing the entire tree. It's not skipping anything.
Và giờ ta có thể chạy nó. Nó giống tìm kiếm theo chiều sâu. Nó duyệt toàn bộ cây. Không bỏ qua thứ gì.
It's not prioritizing anything over anything else. Just going successor, by successor, by successor, and going deeper, deeper, deeper before it's coming back up.
Không ưu tiên cái nào hơn cái nào. Chỉ đi hết nút kế tiếp này đến nút kế tiếp khác, cứ đi sâu, sâu, sâu hơn trước khi quay ngược lên.
So if you had a game tree and the program was running through it, it would start with the start state.
Nên nếu có một cây trò chơi và chương trình chạy qua nó, nó sẽ bắt đầu từ trạng thái ban đầu.
It wouldn't draw out the entire tree like we've been doing and then from the bottom push things up. It would actually start at the top. It would say, OK, what are the successors?
Nó sẽ không vẽ ra toàn bộ cây như ta đã làm rồi mới đẩy giá trị từ dưới lên. Nó thực sự bắt đầu từ trên cùng. Nó sẽ hỏi: các nút kế tiếp là gì?
Three successors. Let me look at the first one. Let me dispatch that one. It's a min node.
Ba nút kế tiếp. Để xem cái đầu tiên. Để điều phối cái đó. Đó là nút min.
OK, let me call min value on that. What does it mean to call min value on this one? It means to call its successors and loop through them.
Được, gọi min value cho nó. Gọi min value cho nút này nghĩa là gì? Nghĩa là gọi các nút kế tiếp của nó và lặp qua chúng.
Oh, looks like the first successor is a terminal state, value of 3. That can be passed back up. And now we have v equal 3 here as our estimate.
À, có vẻ nút kế tiếp đầu tiên là trạng thái kết thúc, giá trị 3. Giá trị đó được trả ngược lên. Giờ ta có v bằng 3 làm giá trị ước lượng ở đây.
Next one is 12. Since we're minimizing, v stays 3. Next one is 8. v stays 3. At this point, we're done.
Nút tiếp theo là 12. Vì đang tối thiểu hóa, v vẫn là 3. Nút tiếp theo là 8. v vẫn là 3. Đến đây là xong.
We've seen all successors. And we can pass this back up. And our estimate at the top here is now 3.
Ta đã thấy hết các nút kế tiếp. Và có thể trả giá trị này ngược lên. Và giá trị ước lượng ở trên cùng giờ là 3.
But it might still change, because we've only seen one of the successor nodes, not all of them yet. Now the depth-first search goes down next branch. Oh, it's a minimizer node again.
Nhưng nó vẫn có thể thay đổi, vì ta mới thấy một nút kế tiếp, chưa phải tất cả. Giờ tìm kiếm theo chiều sâu đi xuống nhánh tiếp theo. À, lại là một nút min.
Look at its successors — terminal state. This now says, oh, the value here is 2. But it might still change as we see other successors. 4 is not going to change that.
Xét các nút kế tiếp của nó, trạng thái kết thúc. Giờ nó nói: à, giá trị ở đây là 2. Nhưng nó vẫn có thể thay đổi khi ta thấy các nút kế tiếp khác. 4 sẽ không làm thay đổi điều đó.
6 is not going to change that. So it's 2. We pass this back up. The maximizer says, I had 3 so far.
6 cũng không. Vậy là 2. Ta trả giá trị này ngược lên. Người chơi max nói: cho đến giờ mình có 3.
This new option is 2. That's worse. So I'm sticking with 3. Going to the next successor, again minimizer.
Lựa chọn mới này là 2. Tệ hơn. Nên mình giữ 3. Sang nút kế tiếp, lại là nút min.
Here, the value would be 14 right now. Then the minimizer looks at the next successor. 5 — so updates to 5. Then sees 2.
Ở đây, giá trị hiện giờ sẽ là 14. Rồi người chơi min xét nút kế tiếp. 5, nên cập nhật thành 5. Rồi thấy 2.
Updates to 2. 2 over here. That gets passed back up. Maximizer says, well, 2 is worse than 3.
Cập nhật thành 2. 2 ở đây. Giá trị đó được trả ngược lên. Người chơi max nói: 2 tệ hơn 3.
3 is the best I've seen. I've seen all my successors. 3 it is.
3 là tốt nhất mình đã thấy. Mình đã xét hết các nút kế tiếp. Vậy là 3.
And I will take the corresponding action, which is going this way, after which the minimizer would take the corresponding action, which is going this way. And the game would end up over here.
Và mình sẽ thực hiện hành động tương ứng, là đi theo hướng này, sau đó người chơi min sẽ thực hiện hành động tương ứng, tức là đi về phía này. Và ván chơi sẽ kết thúc ở đây.
So that's the procedural execution of how the minimax search would work. Any questions about this?
Đó là cách thực thi từng bước của tìm kiếm minimax. Các em có câu hỏi nào không?
OK. Then let's take a look at some properties.
Được rồi. Vậy ta hãy xem một vài tính chất.
Let's say we have this tree over here.
Giả sử ta có cây này ở đây.
And the question we're asking ourselves here is along the lines of we're faced with a real-world situation in some sense, and we've formalized it into a game tree.
Và câu hỏi ta tự đặt ra là kiểu như: ta đứng trước một tình huống thực tế, và ta đã hình thức hóa nó thành một cây trò chơi.
And what will minimax give us? Well, look at this. What's the value for the top player, max? Top node?
Vậy minimax sẽ cho ta kết quả gì? Các em nhìn này. Giá trị cho người chơi trên cùng, max, là bao nhiêu? Nút trên cùng?
STUDENT
10.
10.
PROFESSOR
10? Saying 10. Why 10?
10? Em nói 10. Tại sao là 10?
STUDENT
Because if you go in the other direction, the other player is going to do 9.
Vì nếu đi hướng còn lại, đối thủ sẽ chọn 9.
PROFESSOR
So the answer is well, it looks very tempting here to go for the 100 maybe. But there is a 9 there, and the minimizer would force the 9.
Đúng vậy, ở đây rất hấp dẫn khi muốn đi tới 100. Nhưng có một số 9 ở đó, và minimizer sẽ ép về 9.
So the value here would be 9. On the other side, it's 10. So the value of the game is 10. OK.
Nên giá trị ở đây là 9. Ở nhánh bên kia là 10. Vậy giá trị của ván chơi là 10. Được rồi.
So we have a value of the game that's 10. So that's when you play against a perfect player, like a mastermind player. You would always assume that they get it really, really, really right.
Vậy giá trị của ván chơi là 10. Đó là khi ta chơi với một người chơi hoàn hảo, như một bậc thầy. Ta luôn giả sử họ chơi cực kỳ, cực kỳ chính xác.
But what if you play against a player like this one? Maybe you are willing to take your chances. Maybe you don't think playing Tic-Tac-Toe is a waste of your time.
Nhưng nếu ta chơi với một người như thế này thì sao? Có thể bạn sẵn sàng đánh cược. Có thể bạn không nghĩ chơi cờ ca-rô là phí thời gian.
You can actually win a few games. Even though the value of the game in principle for Tic-Tac-Toe is 0 against this player, it might be plus 1 for you, because they might make mistakes.
Bạn thực sự có thể thắng vài ván. Dù về nguyên tắc, giá trị của ván cờ ca-rô với người này là 0, nó có thể là cộng 1 cho bạn, vì họ có thể mắc lỗi.
And so when you play against a player that might make mistakes, maybe you want to go this way, because maybe they would go there.
Và khi chơi với một người có thể mắc lỗi, có lẽ bạn muốn đi hướng này, vì có thể họ sẽ đi tới đó.
And if they don't, 9 is not that much worse than 10. But if they do make a mistake, a hundred is so much better than 10.
Còn nếu không, 9 không tệ hơn 10 bao nhiêu. Nhưng nếu họ mắc lỗi, 100 tốt hơn 10 rất nhiều.
And so, if just periodically they were to make a mistake, it's worth it going that way. So now we're doing some probabilistic calculation, really.
Nên nếu thỉnh thoảng họ mắc lỗi, thì đi hướng đó là đáng. Vậy thực ra ta đang tính toán xác suất rồi.
It's like, what's the chances that they might make a mistake?
Kiểu như: khả năng họ mắc lỗi là bao nhiêu?
And based on that, maybe we go that way, if the chances are high enough and the payoff is high enough for when they make a mistake.
Và dựa vào đó, có thể ta đi hướng đó, nếu khả năng đủ cao và phần lợi đủ lớn khi họ mắc lỗi.
That's a different kind of way of looking at modeling the world. It's modeling the opponent not as a optimal mastermind playing against you but as somebody who might do some things stochastically.
Đó là một cách khác để nhìn và mô hình hóa thế giới. Ta mô hình đối thủ không phải như một bậc thầy tối ưu chơi chống lại bạn mà như người có thể hành động một cách ngẫu nhiên.
We're not going to look at the details of how that works in this lecture. That's for next lecture.
Bài này ta sẽ không đi vào chi tiết cách nó hoạt động. Để bài sau.
But let's look at some of the consequences of the differences of how you look at the world will affect what you do.
Nhưng hãy xem hệ quả của việc nhìn thế giới theo những cách khác nhau sẽ ảnh hưởng đến hành động của ta thế nào.
So here we'll look at — well, some apologies for the situation we're putting Pac-Man into here.
Ở đây ta sẽ xem — xin lỗi trước về tình huống mà ta đặt Pac-Man vào.
Pretty grim situation — no dots nearby, just ghosts. What's our scoring system? Plus 10 for eating a dot. Negative 1 for each action you take.
Khá bi đát: không có chấm nào gần, chỉ có ma. Cách tính điểm là gì? Cộng 10 khi ăn một chấm. Trừ 1 cho mỗi hành động.
So what do you think Pac-Man should do in this scenario?
Theo các em Pac-Man nên làm gì trong tình huống này?
STUDENT
[INAUDIBLE] PROFESSOR: Some people are pointing to the right. What does that mean? There is a ghost right there. Why would you go to the right, dive-bomb the ghost?
[KHÔNG NGHE RÕ] GIÁO SƯ: Có bạn chỉ sang phải. Nghĩa là sao? Có một con ma ngay đó. Sao lại đi sang phải, lao thẳng vào ma?
Well, it turns out to give you a higher score. If you can manage to be eaten by the ghost in one step, you only lose 1 point due to time.
Hóa ra như vậy lại được điểm cao hơn. Nếu bạn bị ma ăn chỉ sau một bước, bạn chỉ mất 1 điểm do thời gian.
If you get eaten after more steps, you lose more points. So you want to get eaten as quickly as possible in this case. [LAUGHTER] That's the minimax solution.
Nếu bị ăn sau nhiều bước hơn, bạn mất nhiều điểm hơn. Nên bạn muốn bị ăn càng nhanh càng tốt trong trường hợp này. [CƯỜI] Đó là lời giải minimax.
Let's see what happens. So Pac-Man playing minimax. Boom — one step, and game is over. But now let's consider this again.
Xem chuyện gì xảy ra. Pac-Man chơi minimax. Bùm, một bước là hết ván. Nhưng giờ hãy xét lại tình huống này.
And let's think back to the not-so-smart players and look at the ghosts. Maybe they're not that smart. You say, they look a little bleary-eyed. They're not that smart, probably.
Và nghĩ lại về những người chơi không thông minh lắm và nhìn vào các con ma. Có thể chúng không thông minh lắm. Các em thấy trông chúng hơi lờ đờ. Chắc chúng không thông minh đâu.
Maybe I should take my chances. Well, what does it mean to take your chances? The red one is always going to come towards you. It only has one way to go.
Có lẽ mình nên đánh cược. Đánh cược nghĩa là gì? Con màu đỏ luôn lao về phía bạn. Nó chỉ có một đường đi.
But the blue one could go up or down. So maybe half the time it will come towards, half the time it'll go away from you.
Nhưng con màu xanh có thể đi lên hoặc xuống. Nên có thể một nửa số lần nó đến gần, một nửa số lần nó đi xa bạn.
If it goes away from you, then you're lucky, because the ghosts keep running the direction they're going whenever there's no intersection. And it'll keep going away from you.
Nếu nó đi xa bạn, thì bạn may mắn, vì ma cứ chạy theo hướng đang đi khi không có ngã rẽ. Và nó sẽ tiếp tục đi xa bạn.
You'll be able to eat all the dots and win the game. Of course, you're taking the risk that you live longer.
Bạn sẽ ăn hết các chấm và thắng ván. Dĩ nhiên bạn chấp nhận rủi ro là sống lâu hơn.
If it does come towards you, then you could have just dive-bombed the red ghost. So let's see what happens.
Nếu nó đến gần bạn, thì lẽ ra bạn đã có thể lao vào con ma đỏ. Xem chuyện gì xảy ra.
Of course, if the ghost is really taking random actions to choose whether to go up or down, we don't know right now what's going to happen. But let's see what happens.
Dĩ nhiên nếu con ma chọn đi lên hay xuống một cách ngẫu nhiên, giờ ta chưa biết điều gì sẽ xảy ra. Nhưng hãy xem.
Pac-Man took their chances. And indeed, blue ghost moved away. And got lucky and ate everything just in time.
Pac-Man đã đánh cược. Và đúng là con ma xanh đi ra xa. May mắn ăn hết mọi thứ vừa kịp lúc.
Now, if we play the game again, it might be that it doesn't work out the same way. I'm going to try this. OK, let's see what happens this time.
Bây giờ, nếu ta chơi lại ván này, có thể kết quả sẽ không giống như lần trước. Em thử cái này nhé. Nào, xem lần này thế nào.
Got lucky again. But in principle, after it runs a few times, half the time it would be lucky, half the time unlucky. But it might be better than always dive-bombing into the red ghost.
Lại may mắn nữa. Nhưng về nguyên tắc, chạy vài lần thì một nửa số lần là may, một nửa là xui. Nhưng vậy vẫn có thể tốt hơn là cứ lao thẳng vào con ma đỏ.
So the second scenario here is when you're saying, well, I'm playing one of these kind of players. So it's worth taking my chances.
Vậy kịch bản thứ hai là khi bạn nghĩ, mình đang đấu với kiểu đối thủ như thế này. Nên đáng để mạo hiểm.
And we'll see how to compute optimal strategies for that in next lecture.
Và ta sẽ xem cách tính chiến lược tối ưu cho trường hợp đó ở bài giảng sau.
How much compute do we need to do this minimax computation? Well, we already covered depth-first search and how much compute it needs in the second lecture. What was it?
Tính toán minimax này cần bao nhiêu tài nguyên tính toán? Ta đã học tìm kiếm theo chiều sâu và lượng tính toán của nó ở bài giảng thứ hai. Nó là bao nhiêu nhỉ?
Well, it's order branching factor to the power depth of the game, so b to the m, where m is depth of the game. Space — b times m.
Đó là bậc của hệ số nhánh mũ độ sâu của trò chơi, tức b mũ m, trong đó m là độ sâu của trò chơi. Không gian: b nhân m.
So space complexity is pretty good, but time complexity is pretty bad. For chess, branching factor about 35. Of course, not the same in every moment of the game, but some average — 35.
Vậy độ phức tạp không gian khá tốt, nhưng độ phức tạp thời gian khá tệ. Với cờ vua, hệ số nhánh khoảng 35. Tất nhiên không phải lúc nào cũng vậy, mà là giá trị trung bình nào đó, 35.
Maybe a hundred moves total. Then 35 to the 100, which is completely infeasible to search the entire tree. So that's not how Deep Blue beat Kasparov.
Có thể tổng cộng khoảng một trăm nước đi. Thì 35 mũ 100 là hoàn toàn bất khả thi để tìm kiếm toàn bộ cây. Vậy Deep Blue không thắng Kasparov theo cách đó.
It's not by searching the entire tree. Other machinery was needed to get there. And we'll see some of that machinery now.
Nó không tìm kiếm toàn bộ cây. Cần có những kỹ thuật khác để làm được điều đó. Và giờ ta sẽ xem một số kỹ thuật đó.
OK, since we only have finite compute, we cannot explore the entire game tree. So what are we going to do? A first method we'll look at is game tree pruning.
Vì tài nguyên tính toán có hạn, ta không thể khám phá toàn bộ cây trò chơi. Vậy ta sẽ làm gì? Phương pháp đầu tiên là cắt tỉa cây trò chơi.
The question here is, do we really need to look at the entire tree to find a solution?
Câu hỏi ở đây là, liệu ta có thật sự cần xem toàn bộ cây để tìm lời giải không?
If we look back at previous weeks in solving CSPs, we had backtracking whenever filtering said that there will be no solution down here.
Nhìn lại các tuần trước khi giải CSP, ta quay lui mỗi khi bước lọc cho biết phía dưới này sẽ không có lời giải.
It's not worth doing more work because we've already determined that the domain of one of the variables is empty. So it's waste of time to go look further here.
Không đáng làm thêm vì ta đã xác định miền giá trị của một biến bị rỗng. Nên xem tiếp ở đây là phí thời gian.
We don't have domains of variables here that can go empty.
Ở đây ta không có miền giá trị của biến để mà bị rỗng.
But maybe there's something similar we can do where at some point we can conclude this part of the search tree is just not useful to explore anymore to find a solution that we need to find.
Nhưng có lẽ ta làm được điều gì đó tương tự, tức là đến một lúc nào đó ta kết luận được phần này của cây tìm kiếm không còn hữu ích để khám phá nữa trong việc tìm lời giải cần tìm.
So let's do this by example first. Here's our minimax simple example again. And let's say we run depth-first search. As a reminder, what happens — we keep going left to right through the tree.
Ta làm việc này qua ví dụ trước. Đây lại là ví dụ minimax đơn giản của ta. Giả sử ta chạy tìm kiếm theo chiều sâu. Nhắc lại, chuyện xảy ra là ta đi từ trái sang phải qua cây.
We're straight through, collect values. So at this point, this is a 3, which has been passed up. This guy thinks it might be 3, but it might still be something else.
Ta đi thẳng xuống, thu thập các giá trị. Đến đây, đây là 3, đã được truyền lên. Nút này nghĩ nó có thể là 3, nhưng vẫn có thể là giá trị khác.
Here we now have 2. And now stays 2. Stays 2. The 2 gets passed up.
Ở đây giờ ta có 2. Và giờ vẫn là 2. Vẫn là 2. Số 2 được truyền lên.
This one stays 3, and so forth. Do we really need to look at all these numbers to solve this problem?
Nút này vẫn là 3, và cứ thế tiếp tục. Ta có thật sự cần xem hết các số này để giải bài toán không?
Another way to phrase this, is there is something — like, are there any nodes at the bottom here, leaf nodes, where I could have changed their value to anything else and the outcome would have been the same, the value would have still been 3?
Nói cách khác, liệu có nút nào ở dưới đáy, nút lá, mà tôi có thể đổi giá trị thành bất kỳ số nào khác mà kết quả vẫn như cũ, giá trị vẫn là 3?
Because if that's the case, if I can change the value of leaf node to anything else and the value was still 3 and I could know that while I'm doing the search that that leaf node, no matter what the value, the top — the evaluation will remain the same, then we don't need to go look at that leaf node, and we can skip it.
Vì nếu vậy, nếu tôi đổi giá trị của nút lá thành bất kỳ số nào mà giá trị vẫn là 3 và tôi biết điều đó ngay khi đang tìm kiếm, rằng nút lá đó, dù giá trị là bao nhiêu, thì ở trên cùng — kết quả đánh giá vẫn không đổi, thì ta không cần xem nút lá đó, và có thể bỏ qua nó. Đó chính là điều ta đang hướng tới.
So that's what we're after now. OK, let's see how we can achieve this. We start out just the same way. Right now we have no information about the game.
Nào, xem làm thế nào đạt được điều này. Ta bắt đầu giống hệt như trước. Hiện giờ ta chưa có thông tin nào về trò chơi.
So it's going to be very hard to make any claims like, oh, I can skip this because such and such. We don't know anything yet.
Nên rất khó để khẳng định kiểu như, tôi có thể bỏ qua cái này vì lý do nọ kia. Ta chưa biết gì cả.
After we've gone through the left bottom-most node and we know this value is 3, we can propagate this back up. We have maybe 3 here.
Sau khi đi qua nút dưới cùng bên trái và biết giá trị này là 3, ta có thể truyền nó lên trên. Ở đây có thể là 3. Giờ ta có chút hiểu biết về trò chơi.
Now we have a little bit of knowledge about the game. We know that one way of ending the game is by going to this before-last node where the minimizer will choose 3.
Ta biết một cách kết thúc trò chơi là đi tới nút áp chót này nơi người chơi cực tiểu sẽ chọn 3. Ta có thể bỏ qua nút nào trong các nút này không?
Could we have skipped any of these or these nodes? No, because if it had been lower than 3, the minimizer would have chosen it. So there's nothing we could have skipped here so far.
Không, vì nếu nó nhỏ hơn 3, người chơi cực tiểu sẽ chọn nó. Nên cho đến giờ ta không thể bỏ qua nút nào ở đây. Giờ sang nút tiếp theo.
Now go to the next one. Is there anything we can do here? Can we just say, let's skip it? No, we can't, because the minimizer is sitting there.
Ở đây ta có thể làm gì không? Ta có thể nói là bỏ qua nó không? Không, vì có người chơi cực tiểu ở đó. Và nếu các lựa chọn của người chơi cực tiểu chỉ từ một trăm trở lên thì sao?
And what if the minimizer's options are only a hundred and above? Then definitely we need to know about that. But if they're below 3, we also need to know about that.
Thì chắc chắn ta cần biết điều đó. Nhưng nếu chúng nhỏ hơn 3, ta cũng cần biết.
Essentially, what we'll need to know, if there are going to be options here below or above 3, because that's what we have right now at the top. So let's take a look.
Về cơ bản, điều ta cần biết là liệu ở đây có lựa chọn nào dưới hay trên 3 không, vì đó là giá trị ta đang có ở trên cùng. Ta cùng xem nhé. Giá trị đầu tiên là 2.
The first one is 2. What does that tell us? This tells us that the value of this minimizer node is less than or equal to 2. We don't know if it's 2 or less.
Điều đó cho ta biết gì? Nó cho biết giá trị của nút cực tiểu này nhỏ hơn hoặc bằng 2. Ta không biết nó là 2 hay nhỏ hơn. Ta không biết nó là 2 hay có thể là giá trị nào khác, nhưng ta biết nó không lớn hơn 2.
We don't know if it's 2 or maybe another other value, but we know it's less than 2. Once we know it's less than 2, we know the maximizer would never prefer this.
nhưng ta biết nó không lớn hơn 2. Một khi biết nó nhỏ hơn 2, ta biết nút maximizer sẽ không bao giờ chọn nhánh này.
It would always prefer going that way. So it does not matter what the values are here.
Nó luôn thích đi hướng kia hơn. Nên các giá trị ở đây là bao nhiêu cũng không quan trọng.
Because no matter what they are, the maximizer would never let the game get to that node, because it would be worse than going to a node where you get a 3 guaranteed.
Vì dù chúng là gì đi nữa, maximizer cũng sẽ không để ván chơi đi đến nút đó, vì nó sẽ tệ hơn việc đi đến một nút mà ta chắc chắn được 3.
The guaranteed 3 it already has up here is better than anything that could happen down there, no matter what lives over here. So we can just skip over these.
Giá trị 3 chắc chắn mà nó đã có ở trên này tốt hơn bất cứ điều gì có thể xảy ra ở dưới đó, bất kể bên này có gì. Vậy ta có thể bỏ qua các nút này.
Don't need to look at them. And note this would be true even if these were not terminal nodes.
Không cần xem chúng. Và lưu ý điều này vẫn đúng ngay cả khi chúng không phải nút kết thúc.
Imagine we're a whole big tree living underneath here — a whole big tree living underneath here.
Hãy tưởng tượng có cả một cây lớn nằm bên dưới đây — cả một cây lớn nằm bên dưới đây.
We don't have to explore any of that tree because we know the maximizer would never let the game go that way because minimizer will be able to make it less than or equal to 2, and maximizer could force a 3.
Ta không cần khám phá phần nào của cây đó vì ta biết maximizer sẽ không bao giờ để ván chơi đi hướng đó, vì minimizer sẽ có thể ép giá trị nhỏ hơn hoặc bằng 2, còn maximizer có thể ép được 3.
And so we could prune massive amounts of computation if there are big subtrees over there. We continue. OK, we have a minimizer node again. At this point, we know nothing yet about this branch.
Và như vậy ta cắt tỉa được rất nhiều phép tính nếu bên đó có những cây con lớn. Ta tiếp tục. Được, lại có một nút minimizer. Lúc này ta chưa biết gì về nhánh này.
We know the maximizer can force a 3. We don't know if this might be a better or worse option than the 3 it can already force. Now we see a value of 14.
Ta biết maximizer có thể ép được 3. Ta chưa biết lựa chọn này tốt hay tệ hơn so với 3 mà nó đã ép được. Giờ ta thấy giá trị 14.
Oh, wow. This looks promising. We know the value here is less than or equal to 14. But if it could be 14, that would be great.
Ồ, tuyệt. Trông có vẻ hứa hẹn. Ta biết giá trị ở đây nhỏ hơn hoặc bằng 14. Nếu được 14 thì quá tốt.
Can we stop here and just ignore these? No, we can't, because we're not guaranteed to get 14. It could be negative infinity for all we know, and then we don't want to go there.
Ta có thể dừng ở đây và bỏ qua các nút này không? Không, vì ta không được đảm bảo có 14. Biết đâu nó là âm vô cùng, và khi đó ta không muốn đi đến đó.
So we need to keep looking. Now it's 5. So we know this one is less than or equal to 5. 5 would be great.
Nên ta cần xem tiếp. Giờ là 5. Vậy nút này nhỏ hơn hoặc bằng 5. 5 thì tốt.
It's better than 3. But there are still other parts that we haven't seen. And as long as we haven't seen that, we don't know what the minimizer will force us to get there.
Tốt hơn 3. Nhưng vẫn còn những phần ta chưa thấy. Và chừng nào ta chưa thấy chúng, ta chưa biết minimizer sẽ ép ta nhận giá trị nào ở đó.
So we need to keep looking. What is it? A 2? Now we know that it's actually 2.
Nên ta cần xem tiếp. Là gì đây? Một số 2? Giờ ta biết nó thực sự là 2.
That's worse. And maximizer will conclude to go this way, and the game will end up over here. What computation did we save? All of the computation that would have happened over here.
Tệ hơn. Và maximizer sẽ kết luận đi hướng này, và ván chơi sẽ kết thúc ở đây. Ta đã tiết kiệm được phép tính nào? Toàn bộ phép tính lẽ ra phải làm ở bên này.
In a small tree like this, it might not be a lot. But this principle can be reused everywhere in your game tree. It's called alpha-beta pruning. So what's the general version?
Với cây nhỏ như thế này thì có thể không nhiều. Nhưng nguyên lý này có thể dùng lại ở mọi nơi trong cây trò chơi. Nó được gọi là cắt tỉa alpha-beta. Vậy dạng tổng quát là gì?
We have a game tree. And in this game tree, we're computing the min value at some node, n, over here. To do that, we loop over n's children.
Ta có một cây trò chơi. Và trong cây này, ta đang tính giá trị min tại một nút n ở đây. Để làm vậy, ta duyệt qua các con của n.
As we loop over n's children, the estimate of the value of that node will keep dropping. It will never go up.
Khi duyệt các con của n, giá trị ước lượng của nút đó sẽ cứ giảm dần. Nó sẽ không bao giờ tăng.
Any time you see a next child's value, it can only go down what your estimate is, never go back up.
Mỗi khi thấy giá trị của con tiếp theo, ước lượng chỉ có thể giảm xuống, không bao giờ tăng lại.
So if at some point our estimate here — we said at this node, the value of this node is, let's say, less than or equal to some value, x.
Nên nếu tại một lúc nào đó ước lượng của ta ở đây — giả sử tại nút này, giá trị của nút là nhỏ hơn hoặc bằng một giá trị x nào đó.
If any time x is smaller than a, which is a value the maximizer can guarantee over here, then we know that no matter what else is still in other successor nodes, it's only going to make it worse than x.
Nếu bất cứ lúc nào x nhỏ hơn a, tức là giá trị maximizer có thể đảm bảo ở đây, thì ta biết dù các nút kế tiếp còn lại có gì đi nữa, chúng cũng chỉ làm giá trị tệ hơn x.
And so what we know is that it's already worse than a. Maximizer can force a.
Và như vậy ta biết nó đã tệ hơn a rồi. Maximizer có thể ép được a.
So maximizer will never let this path happen, because that would open up the opportunity to end up with something worse.
Nên maximizer sẽ không bao giờ để đường này xảy ra, vì điều đó sẽ mở ra khả năng kết thúc với một kết quả tệ hơn.
So what we now know is that maximizer will never let the game get over here.
Vậy giờ ta biết maximizer sẽ không bao giờ để ván chơi đi đến đây.
So we don't really care about the exact value of the node over there because the game will not end up over there.
Nên ta không thực sự quan tâm giá trị chính xác của nút ở đó vì ván chơi sẽ không kết thúc ở đó.
We know it's a worse value than what the maximizer can force over here. And that's all we need to know. And we can stop exploring the successors and just pass up that value, x.
Ta biết nó tệ hơn giá trị maximizer có thể ép được ở đây. Và đó là tất cả những gì ta cần biết. Và ta có thể ngừng khám phá các nút kế tiếp và chỉ cần trả giá trị x lên trên.
As a substitute, we know the value is not necessarily really x. But we know it's x or worse.
Thay vào đó, ta biết giá trị không nhất thiết thực sự là x. Nhưng ta biết nó là x hoặc tệ hơn.
And that's good enough a value to pass up for the maximizer to conclude, I'm never going to go there, and we're good to go.
Và giá trị đó đủ tốt để trả lên cho maximizer kết luận: tôi sẽ không đi đến đó, thế là xong.
And so this way you might be able to prune a large amount of computation over here.
Và bằng cách này bạn có thể cắt tỉa được rất nhiều phép tính ở đây.
Note when looking at the comparison, when we compare with this value a over here, what are we actually comparing with?
Lưu ý khi nhìn vào phép so sánh, khi ta so sánh với giá trị a ở đây, thực ra ta đang so sánh với cái gì?
We take a path from the node that we're currently exploring all the way to the root of the tree.
Ta lấy một đường đi từ nút ta đang khám phá lên tới gốc của cây.
And anywhere along the path to the root, we look at maximizer nodes. There's a maximizer node here. There's one here. Maybe one here.
Và ở bất cứ đâu dọc đường lên gốc, ta xét các nút maximizer. Có một nút maximizer ở đây. Có một nút ở đây. Có thể có một nút ở đây.
And for each of the maximizer nodes, we see, what have they already been able to guarantee themselves?
Và với mỗi nút maximizer, ta xem chúng đã đảm bảo được cho mình điều gì.
And the best thing that's been guaranteed by any of the maximizer nodes so far is the thing we compare with. And that's what we call a.
Và giá trị tốt nhất đã được đảm bảo bởi bất kỳ nút maximizer nào cho đến giờ chính là thứ ta so sánh. Và đó là cái ta gọi là a.
Formally, what does this look like, a or alpha? Alpha is the maximizer's best option on the path to root from the current node we're working on.
Về mặt hình thức, a hay alpha trông như thế nào? Alpha là lựa chọn tốt nhất của maximizer trên đường từ nút hiện tại ta đang xử lý lên gốc.
And there will be a counterpart, beta, which is min's best option on the path to the root. We were talking about min. So let's go here. We're working on a min value node.
Và sẽ có một đối ứng, beta, là lựa chọn tốt nhất của min trên đường đi về gốc. Ta đang nói về min. Vậy ta đi xuống đây. Ta đang xử lý một nút giá trị min.
As before, we initialize with plus infinity. We loop over successors. There's a recursive call in there to get the value of the successor.
Như trước, ta khởi tạo bằng cộng vô cùng. Ta lặp qua các nút kế tiếp. Ở đó có một lời gọi đệ quy để lấy giá trị của nút kế tiếp.
You compare the value of the successor with the current value estimate. If it's lower, you update, because that means you can get even lower than you thought before.
Bạn so sánh giá trị của nút kế tiếp với giá trị ước lượng hiện tại. Nếu nó thấp hơn thì bạn cập nhật, vì điều đó có nghĩa là bạn đạt được giá trị thấp hơn so với tưởng.
You do pass along alpha and beta in the recursive call. And what are alpha and beta? It's from where you currently are all the way to the root.
Bạn có truyền alpha và beta trong lời gọi đệ quy. Vậy alpha và beta là gì? Là từ chỗ bạn đang đứng suốt đường đi về gốc.
For alpha, you check what's max best option already available. And for beta, you check what's min's best option already available on that path. So those you can just pass on to your child.
Với alpha, bạn kiểm tra lựa chọn tốt nhất mà max đã có. Còn với beta, bạn kiểm tra lựa chọn tốt nhất mà min đã có trên đường đi đó. Những giá trị này bạn cứ truyền cho nút con.
Then if the value we see is less than alpha — so min can do something that guarantees less than alpha, which max can already force somewhere else — then we know we're done.
Rồi nếu giá trị ta thấy nhỏ hơn alpha — tức là min có thể làm được điều đảm bảo nhỏ hơn alpha, mà max đã có thể ép được ở chỗ khác — thì ta biết là xong rồi.
This part of the tree is not going to be visited because max will not allow it.
Phần này của cây sẽ không được duyệt tới vì max sẽ không cho phép.
So we might as well just return the current v that we have, which is not a precise value of that node. It's just a value that signals it's going to be v or worse.
Nên ta cứ trả về v hiện có, đó không phải giá trị chính xác của nút này. Nó chỉ là giá trị báo hiệu rằng kết quả sẽ là v hoặc tệ hơn.
And that's enough information from max to know further up the tree to never go there.
Và thế là đủ thông tin cho max để biết ở các tầng trên không bao giờ đi vào đó.
If along the way as min is checking options it sees something that is a better option than beta, the best thing it's seen on the path to the root, then of course I should update beta.
Nếu trên đường đi, khi min đang kiểm tra các lựa chọn mà thấy một lựa chọn tốt hơn beta, tức là điều tốt nhất nó đã thấy trên đường về gốc, thì dĩ nhiên tôi nên cập nhật beta.
Note that these betas are local. If it updates beta here — I'm going back into this drawing.
Lưu ý các beta này mang tính cục bộ. Nếu nó cập nhật beta ở đây — tôi quay lại hình vẽ này.
If this min node has a beta that goes down by seeing something, that does not get passed back up. Beta is about things you can guarantee on the path to the root.
Nếu nút min này có beta giảm đi do thấy một giá trị nào đó, thì giá trị đó không được truyền ngược lên. Beta là những gì bạn đảm bảo được trên đường đi về gốc.
And if you're over here, that option down there is not on the path to the root. So the update of beta will only get passed into children, not passed back up.
Và nếu bạn đang ở bên này, thì lựa chọn ở dưới kia không nằm trên đường về gốc. Nên việc cập nhật beta chỉ được truyền xuống các nút con, không truyền ngược lên.
What's being passed back up is only v. OK. Any questions about this?
Thứ được truyền ngược lên chỉ là v. OK. Có câu hỏi nào về phần này không?
There.
Bạn kia.
STUDENT
Isn't the calculation of the value of a node requires you to convert the tree?
Việc tính giá trị của một nút chẳng phải đòi hỏi phải duyệt qua cây sao?
Because you get the value of the node, but to get to the value of that part, you have to traverse the tree or have some sort of heuristic or — PROFESSOR: Yeah, so the question is — if I can rephrase it, there's really two parts to the question.
Vì bạn lấy giá trị của nút, nhưng để có giá trị của phần đó, bạn phải duyệt cây hoặc dùng một hàm heuristic nào đó hoặc — GIÁO SƯ: Vâng, câu hỏi là — nếu tôi diễn đạt lại, thật ra có hai phần trong câu hỏi.
One part of the question is, when we're doing this work, the value of successor, what does that mean to do that work?
Phần một là, khi ta làm việc này, tính giá trị nút kế tiếp, thì làm việc đó nghĩa là gì?
And the second part of your question was, can we even afford to do that work? Because it sounds like a recursion, and that recursion could be really deep.
Phần hai của bạn là, liệu ta có đủ khả năng làm việc đó không? Vì nghe như một đệ quy, và đệ quy đó có thể rất sâu.
And the answer is yes. You will have to do a recursion. That's what it is doing. And this could go very, very deep and branching very widely and could be very expensive.
Và câu trả lời là có. Bạn sẽ phải thực hiện đệ quy. Đó chính là việc nó làm. Nó có thể đi rất sâu, phân nhánh rất rộng và có thể rất tốn kém.
We're hoping to reduce how expensive it is by the alpha-beta pruning, which allows us to skip over subtrees in various places. But even then, there might still be too much work.
Ta hy vọng giảm chi phí đó bằng cắt tỉa alpha-beta, giúp ta bỏ qua các cây con ở nhiều chỗ. Nhưng dù vậy, vẫn có thể còn quá nhiều việc.
And we'll look at how much we can prune soon.
Ta sẽ sớm xem có thể cắt tỉa được bao nhiêu.
And then we'll see what else we'll need in additional machinery for many, many games to make it all work together to get to something that you can actually run.
Rồi ta sẽ xem cần thêm những công cụ nào nữa cho rất nhiều trò chơi để mọi thứ phối hợp với nhau thành thứ mà bạn thực sự chạy được.
This will probably still run out of time just running it this way on a big game. You're absolutely right.
Với một trò chơi lớn, chạy theo cách này có lẽ vẫn hết thời gian. Bạn hoàn toàn đúng.
What are the properties of alpha-beta pruning? One is that it has no effect on the minimax value computed at the root.
Các tính chất của cắt tỉa alpha-beta là gì? Thứ nhất là nó không ảnh hưởng đến giá trị minimax tính được ở gốc.
Because we only skip over things that we know no matter what the values are there, we'll end up with the same result. That's how we started out inventing this process.
Vì ta chỉ bỏ qua những thứ mà dù giá trị ở đó là bao nhiêu ta cũng ra cùng một kết quả. Đó là cách ta bắt đầu phát minh ra quy trình này.
The intermediate nodes might have incorrect values.
Các nút trung gian có thể có giá trị không chính xác.
So when you go through this process, if you were to then keep the tree around and look at the values passed around, they will not be exact very often, because you've decided to not compute them exactly to save time because you don't need them exactly to know what to do at the top.
Nên khi bạn chạy quy trình này, nếu bạn giữ cây lại rồi xem các giá trị được truyền đi, chúng thường sẽ không chính xác, vì bạn đã quyết định không tính chính xác để tiết kiệm thời gian vì bạn không cần giá trị chính xác để biết phải làm gì ở trên cùng.
And all we care about is to do the right thing at the top. Then, actually, we can repeat this process. When it's next time our turn, we can run this again.
Và ta chỉ quan tâm làm đúng ở trên cùng. Rồi, thực ra ta có thể lặp lại quy trình này. Lần tới đến lượt ta, ta có thể chạy lại.
So effectively, we end up with a replanning type of agent. The next time, we just run it again. Note that in the most naive way, you don't get enough information.
Nên thực chất ta có một tác tử kiểu lập kế hoạch lại. Lần sau, ta chỉ việc chạy lại. Lưu ý rằng theo cách ngây thơ nhất, bạn không có đủ thông tin.
Because if all you have is the value at the top, you might say, oh, it's 0. We shouldn't even play.
Vì nếu bạn chỉ có giá trị ở trên cùng, bạn có thể nói, ồ, nó bằng 0. Ta thậm chí không nên chơi.
And then maybe you can convince the other person it's 0 and you shouldn't play. But actually, the other person says, no, no, no. I want to play.
Và có thể bạn thuyết phục được đối thủ là nó bằng 0 và họ không nên chơi. Nhưng thực ra đối thủ nói, không không không. Tôi muốn chơi.
Just knowing that it's 0 doesn't tell you what to do. You need to know which of these are the right one. For example, if we run alpha-beta pruning, we would first go down here.
Chỉ biết nó bằng 0 thì không cho bạn biết phải làm gì. Bạn cần biết trong số này cái nào là đúng. Ví dụ, nếu ta chạy cắt tỉa alpha-beta, trước hết ta đi xuống đây.
We would get a 10. Pass that up. We say 10 so far. Then we go down here.
Ta được 10. Truyền nó lên. Ta nói cho đến giờ là 10. Rồi ta đi xuống đây.
Min says it's going to be less than or equal to 10. Well, we already have a 10 that we can force. So we don't need to look at any of this.
Min nói nó sẽ nhỏ hơn hoặc bằng 10. Chà, ta đã có một giá trị 10 mà ta ép được rồi. Nên ta không cần xem chỗ này.
No matter what's there, we would go there. So we pass up the 10. And we end up with a 10 over here.
Dù ở đó có gì đi nữa, ta cũng sẽ chọn nhánh kia. Nên ta chuyển giá trị 10 lên trên. Và ta có 10 ở đây.
But we actually need to remember in the process not just that we have a 10 at the top but that this 10 is one that we're able to guarantee.
Nhưng trong quá trình này ta cần nhớ không chỉ là ở trên cùng có 10, mà số 10 này là giá trị mà ta có thể đảm bảo.
And what came from this side was a 10. That didn't mean you're going to get a 10 here. But that meant it's going to be a 10 or worse.
Còn bên này trả về 10. Điều đó không có nghĩa là ở đây bạn sẽ được 10. Mà nghĩa là nó sẽ là 10 hoặc tệ hơn.
So probably don't take this one. Take the one where you're guaranteed a 10. How do we keep this information around? There is a few different ways of doing it.
Nên có lẽ đừng chọn nhánh này. Hãy chọn nhánh mà bạn được đảm bảo 10. Làm sao giữ lại thông tin này? Có vài cách khác nhau.
The simplest way to do it is then it turns out that the first one you find is the one that tells you're able to guarantee something.
Cách đơn giản nhất là nhánh đầu tiên mà bạn tìm thấy chính là nhánh cho bạn một giá trị đảm bảo được.
So if you just remember which one was first, that's the one that told you for the other ones not to do all the work. So you keep around the one that you found first.
Nên nếu bạn chỉ cần nhớ nhánh nào đến trước, thì chính nhánh đó báo cho các nhánh còn lại là không cần làm hết việc. Vậy bạn giữ lại nhánh tìm thấy đầu tiên.
You can take that action.
Và chọn hành động đó.
If you have a hard time bookkeeping that, other options are you could instead of running the search from the top, you could run it from the children of the top node.
Nếu bạn khó theo dõi điều đó, thì cách khác là thay vì chạy tìm kiếm từ gốc, bạn có thể chạy từ các nút con của nút gốc.
Compute the exact values for these nodes. And then you can say, OK, these are the exact values for each of my children obtained by alpha beta pruning. Let me see which child is best.
Tính giá trị chính xác cho các nút này. Rồi bạn nói: được rồi, đây là giá trị chính xác của từng nút con, có được nhờ cắt tỉa alpha-beta. Xem nút con nào tốt nhất.
Or you could decide that you only prune on inequality, not on equality. So you'd say, I prune if the value — oh, that's a little big.
Hoặc bạn có thể chỉ cắt tỉa khi bất đẳng thức chặt, không phải khi bằng nhau. Tức là bạn nói: tôi cắt tỉa nếu giá trị — ồ, hơi lớn.
I'll prune on strict inequality, strict smaller than — rather than allowing for equality.
Tôi cắt tỉa với bất đẳng thức chặt, nhỏ hơn hẳn — thay vì cho phép bằng nhau.
So there's three different ways you can do this — keep track of which one was first, because that one you guaranteed it, whereas the other ones you skipped computation and just said, might be this or worse; run it on the children; or prune on only strict inequalities.
Vậy có ba cách để làm — theo dõi nhánh nào đến đầu tiên, vì nhánh đó bạn đã đảm bảo được, còn các nhánh khác bạn bỏ qua tính toán và chỉ nói là có thể bằng hoặc tệ hơn; chạy trên các nút con; hoặc chỉ cắt tỉa khi bất đẳng thức chặt.
Good child ordering improves effectiveness of pruning. What does this mean?
Sắp xếp thứ tự nút con tốt giúp cắt tỉa hiệu quả hơn. Điều này nghĩa là gì?
Well, when you get to prune, when the other player already has a good guarantee somewhere else — what does it mean to have a good guarantee?
Bạn được cắt tỉa khi đối thủ đã có một đảm bảo tốt ở chỗ khác — có đảm bảo tốt nghĩa là gì?
That means that the other player somehow looked at some good options already.
Nghĩa là đối thủ bằng cách nào đó đã xem xét một số lựa chọn tốt rồi.
So if somehow you're clever about exploring good options first and then the bad options, then more often this pruning might be triggered.
Nên nếu bạn khéo khám phá các lựa chọn tốt trước, rồi mới đến lựa chọn xấu, thì việc cắt tỉa sẽ xảy ra thường xuyên hơn.
With a perfect ordering, you can show that the time complexity drops to order b to the m over 2, so square root amount of computation from doing regular minimax if you have the perfect ordering of how you explore the tree.
Với thứ tự hoàn hảo, có thể chứng minh độ phức tạp thời gian giảm xuống O(b^(m/2)), tức là chỉ còn căn bậc hai lượng tính toán so với minimax thông thường nếu bạn có thứ tự hoàn hảo khi duyệt cây.
This doubles how deep you can look. If you have a fixed compute budget, you can look twice as deep, which is a lot.
Điều này nhân đôi độ sâu bạn có thể nhìn. Với ngân sách tính toán cố định, bạn nhìn sâu gấp đôi, thế là rất nhiều.
If you look twice as deep as your opponent, you're going to probably beat them.
Nếu bạn nhìn sâu gấp đôi đối thủ, nhiều khả năng bạn sẽ thắng.
But even then, just the square root — to the question earlier — is not often enough to solve something like chess all the way to the bottom.
Nhưng dù vậy, chỉ căn bậc hai thôi — như câu hỏi lúc nãy — thường chưa đủ để giải một trò như cờ vua đến tận đáy cây.
This is a simple example of meta-reasoning. What do we mean with meta-reasoning? It's where you do compute to decide about what you're going to compute.
Đây là một ví dụ đơn giản của meta-reasoning. Meta-reasoning nghĩa là gì? Là bạn tính toán để quyết định xem mình sẽ tính toán cái gì.
So we compute alpha beta values, which allow us to then decide that for a certain subtree, we're not going to do any compute.
Ta tính các giá trị alpha beta, từ đó quyết định rằng với một cây con nào đó, ta sẽ không tính gì cả.
And so we do a little bit of extra compute to then be able to discard other compute.
Vậy ta tốn thêm một chút tính toán để có thể bỏ đi những phần tính toán khác.
Let's take a one-minute break here. And then after the break, let's do a quick quiz and look at what we still need to solve problems like chess and so forth.
Nghỉ một phút nhé. Sau giờ nghỉ, ta làm một bài kiểm tra nhanh và xem ta còn cần gì để giải các bài toán như cờ vua và những trò tương tự.
[SIDE CONVERSATION] All right, let's restart.
[NÓI CHUYỆN RIÊNG] Được rồi, bắt đầu lại nào.
Any questions about the first part of lecture?
Có câu hỏi nào về phần đầu bài giảng không?
Question there.
Bạn ở đằng kia.
STUDENT
Can you go back to the last one?
Thầy quay lại slide cuối được không ạ?
PROFESSOR
Sure.
Được.
STUDENT
So what is m here on the [INAUDIBLE]??
SINH VIÊN: m ở đây là gì ạ, trên [KHÔNG NGHE RÕ]?
PROFESSOR
Oh. The question is, what is m? m stands for the number of moves before the game ends. So let's say it takes in Tic-Tac-Toe nine moves to fill the board.
À. Câu hỏi là m là gì? m là số nước đi cho đến khi ván đấu kết thúc. Ví dụ trong Tic-Tac-Toe cần chín nước để lấp đầy bàn cờ.
I mean, sometimes it stops earlier. But then m would be 9. And with alpha-beta pruning, theoretically of the optimal expansion ordering, you would have an effective depth of 4 and 1/2 instead of 9.
Đôi khi nó kết thúc sớm hơn. Nhưng khi đó m sẽ là 9. Và với cắt tỉa alpha-beta, về lý thuyết với thứ tự mở rộng tối ưu, độ sâu hiệu dụng sẽ là 4,5 thay vì 9.
STUDENT
A different question also — so if we do strict inequality for minimax, would that mean that we have to do more nodes that — PROFESSOR: Correct.
Em hỏi thêm câu nữa — nếu dùng bất đẳng thức chặt cho minimax, thì có phải ta phải duyệt nhiều nút hơn không ạ — GIÁO SƯ: Đúng vậy.
If you do strict inequality for pruning, you might lose a lot. Especially if a lot of nodes have similar values, then you would lose out on a lot of pruning.
Nếu cắt tỉa với bất đẳng thức chặt, bạn có thể mất rất nhiều. Nhất là khi nhiều nút có giá trị tương tự nhau, thì bạn sẽ bỏ lỡ rất nhiều lần cắt tỉa.
So your effectiveness will go down as a consequence of your approach.
Nên hiệu quả sẽ giảm do cách tiếp cận của bạn.
STUDENT
All those methods that we can start of the three, which one is the best?
Trong ba phương pháp đó, phương pháp nào là tốt nhất ạ?
PROFESSOR
The most — the one that requires the least compute will be the one where you carefully keep track of which was the first one that guaranteed you a certain outcome.
Cách tốn ít tính toán nhất là cách bạn theo dõi cẩn thận nhánh nào đầu tiên đảm bảo cho bạn một kết quả nhất định.
And you prune also on equality.
Và bạn cũng cắt tỉa cả khi bằng nhau.
OK, let's do a quick quiz here. Let's have you look at this game tree. Talk with your neighbors and think about what would happen if you run alpha-beta pruning on this game tree.
Được rồi, làm một bài kiểm tra nhanh nhé. Các bạn hãy nhìn cây trò chơi này. Trao đổi với bạn bên cạnh và nghĩ xem điều gì sẽ xảy ra nếu chạy cắt tỉa alpha-beta trên cây trò chơi này.
I'll give you 30 seconds. Just talk to each other. What's the value of the game? Which nodes might you be able to prune?
Tôi cho các bạn 30 giây. Cứ trao đổi với nhau. Giá trị của trò chơi là bao nhiêu? Bạn có thể cắt tỉa những nút nào?
[STUDENTS DISCUSSING QUIZ] OK, let's see.
[SINH VIÊN THẢO LUẬN BÀI TẬP] Được rồi, xem nào.
What is the value of this game, the minimax value of the game or alpha-beta value of the game? Any thoughts?
Giá trị của trò chơi này là bao nhiêu, giá trị minimax của trò chơi hay giá trị alpha-beta của trò chơi? Có ý kiến nào không?
What's the value?
Giá trị là bao nhiêu?
Anyone?
Có ai không?
STUDENT
8.
8.
PROFESSOR
8 — value 8. Do we need to run alpha-beta pruning to know the value is 8? No, we don't, because we know alpha-beta pruning will give us the same value as minimax.
8, giá trị là 8. Ta có cần chạy cắt tỉa alpha-beta để biết giá trị là 8 không? Không cần, vì ta biết cắt tỉa alpha-beta sẽ cho cùng giá trị với minimax.
So if I ask you, what's the result of running alpha-beta pruning on this, you could say, well, that's a complicated procedure. You need to think about a lot of things.
Nên nếu tôi hỏi kết quả của việc chạy cắt tỉa alpha-beta trên cây này là gì, bạn có thể nói, đó là một thủ tục phức tạp. Phải cân nhắc rất nhiều thứ.
But I know it computes the same as minimax. And minimax I can just read off. On one side, min forces 8. On the other side, min forces 4.
Nhưng tôi biết nó cho kết quả giống minimax. Và minimax thì tôi chỉ cần đọc ra. Ở một bên, min ép về 8. Ở bên kia, min ép về 4.
8 is a better thing to be forced. So the value of the game is this. And this is how the game will play out, with a value of 8.
Bị ép về 8 thì tốt hơn. Vậy giá trị của trò chơi là giá trị này. Và trò chơi sẽ diễn ra như thế, với giá trị 8.
So even though the question might have been about alpha-beta pruning, you could have solved it and found the answer without doing it. Now, what will happen when you run alpha-beta printing?
Vì vậy, dù câu hỏi có thể là về cắt tỉa alpha-beta, bạn vẫn có thể giải và tìm ra đáp án mà không cần chạy nó. Vậy khi chạy cắt tỉa alpha-beta thì chuyện gì xảy ra?
Are there any nodes — and this is a question we love to ask. It's like, OK, which nodes will not be expanded when running alpha-beta pruning? Well, let's see.
Có nút nào không, và đây là câu hỏi tụi tôi rất thích hỏi. Đó là: nút nào sẽ không được mở rộng khi chạy cắt tỉa alpha-beta? Xem nào.
And let's assume we go from left to right and then see where we get to skip expansion of nodes, or inspection of terminal values.
Giả sử ta đi từ trái sang phải và xem ở đâu ta bỏ qua được việc mở rộng nút, hoặc xem giá trị các nút lá.
OK, initially, we have no way of skipping, because we don't know anything yet. Then here, we don't know anything yet either. So keep going. We see a 10.
Ban đầu, ta chưa thể bỏ qua gì cả, vì ta chưa biết gì. Ở đây cũng vậy, ta chưa biết gì. Nên cứ tiếp tục. Ta thấy một số 10.
Can we skip the next one? No, because it might be a better option for min. And it actually is better. It's 8.
Có bỏ qua được nút tiếp theo không? Không, vì nó có thể là lựa chọn tốt hơn cho min. Và thực sự nó tốt hơn. Là 8.
Now it's 8. That's being passed back up. We have a 8 over here. What now?
Giờ giá trị là 8. Giá trị đó được truyền ngược lên. Ta có số 8 ở đây. Giờ thì sao?
Can we skip anything? Can we skip this next one? No, because maybe there's only good options down there, and min cannot force us to anything bad. So we need to go look.
Có bỏ qua được gì không? Có bỏ qua được nút tiếp theo này không? Không, vì biết đâu dưới đó toàn lựa chọn tốt, và min không thể ép ta vào kết quả xấu. Nên ta cần xuống xem.
Min looks here, finds a 4. That means things are going to be less than or equal to 4 down here. Max can already force an 8 that way.
Min nhìn ở đây, thấy số 4. Nghĩa là giá trị ở dưới này sẽ nhỏ hơn hoặc bằng 4. . Max đã có thể ép được 8 bằng nhánh kia.
Doesn't matter what's here. No matter how good or bad, the game's not going to end up over there. We can just pass up this 4 and continue.
Nên ở đây có gì cũng không quan trọng. Dù tốt hay xấu đến đâu, trò chơi cũng sẽ không đi vào nhánh đó. Ta chỉ cần truyền số 4 này lên và tiếp tục.
And also, it doesn't matter how big the tree is. If it happens to be a terminal node — it could be a huge tree there — you can completely skip over it.
Và cây lớn đến đâu cũng không quan trọng. Dù nó chỉ là một nút lá, hay có thể là một cây khổng lồ, ta vẫn có thể bỏ qua hoàn toàn.
How about this one here? What's the value of the game and which nodes can be pruned in the process?
Còn cây này thì sao? Giá trị của trò chơi là bao nhiêu và những nút nào có thể bị cắt tỉa trong quá trình đó?
I'll give you a minute to think about it. And feel free to talk with your neighbors, see what you conclude.
Tôi cho các bạn một phút suy nghĩ. Cứ thoải mái trao đổi với bạn bên cạnh, xem các bạn kết luận thế nào.
[STUDENTS DISCUSSING QUIZ] All right.
[SINH VIÊN THẢO LUẬN BÀI TẬP] Được rồi.
What's the value of the game? What do we get from running minimax or alpha-beta pruning? They all give the same result. Anybody?
Giá trị của trò chơi là bao nhiêu? Chạy minimax hay cắt tỉa alpha-beta thì ta được gì? Chúng đều cho cùng kết quả. Ai trả lời được?
STUDENT
Is that a 10?
Là 10 phải không ạ?
PROFESSOR
10, OK. How do we get 10? Again, whether we run alpha-beta pruning or minimax, it's going to be the same thing. We can just look at this is going to be 10.
10, đúng. Làm sao ta có 10? Một lần nữa, dù chạy cắt tỉa alpha-beta hay minimax, kết quả vẫn như nhau. Ta chỉ cần nhìn: chỗ này sẽ là 10.
This is going to be a hundred. This is going to be 2. This is going to be 20. That means min can force a 2 here.
Chỗ này sẽ là một trăm. Chỗ này sẽ là 2. Chỗ này sẽ là 20. Nghĩa là min có thể ép về 2 ở đây.
It can only force a 10 over here. 10 is better. Value of the game. But now we looked at everything.
Còn bên này chỉ ép được về 10. 10 tốt hơn. Đó là giá trị của trò chơi. Nhưng lúc này ta đã xem hết mọi thứ.
The question is if we ran alpha-beta pruning, could we have skipped looking at some things? OK, let's see.
Câu hỏi là nếu ta chạy cắt tỉa alpha-beta, liệu ta có thể bỏ qua một số nút không? Được rồi, xem nào.
What nodes can be skipped? Any thoughts?
Có thể bỏ qua những nút nào? Có ý kiến nào không?
Over there.
Bạn ở đằng kia.
STUDENT
The third branch.
Nhánh thứ ba ạ.
PROFESSOR
Can you give the letter on the branch that you're referring to?
Bạn cho biết chữ cái của nhánh mà bạn đang nói tới được không?
STUDENT
I.
I.
PROFESSOR
I? So the suggestion is that we can skip I. Any other things?
I à? Vậy đề xuất là ta bỏ qua I. Còn gì nữa không?
STUDENT
L and M.
L và M.
STUDENT
After we look at I, we can skip L.
Sau khi xem I, ta có thể bỏ qua L.
PROFESSOR
After looking at I, we might be able to skip L. So that would be something not just a terminal node but in a tree that's bigger than just terminal node.
Sau khi xem I, ta có thể bỏ qua L. Vậy đó sẽ không chỉ là nút lá mà là một cây lớn hơn một nút lá.
Any other branches we can skip? G? G over here. So we can skip going down that one.
Còn nhánh nào khác bỏ qua được không? G? G ở đây. Vậy ta có thể bỏ qua việc đi xuống nhánh đó.
Any other ones?
Còn nhánh nào nữa không?
OK, let's see if it's true, what happens. We go down this way. Can't skip anything. No information yet.
Được rồi, xem thử điều đó có đúng không, chuyện gì xảy ra. Ta đi xuống lối này. Không bỏ qua được gì. Chưa có thông tin gì.
We always have to first do the left bottom-most one. We're always going to have to look at everything. That's just always going to be the case.
Ta luôn phải xem nút dưới cùng bên trái trước. Lúc nào ta cũng phải xem hết phần đó. Điều đó lúc nào cũng đúng.
If you work through it, you'll see this one has 10. Once we have this, we can pass it up. This means that min can get less than or equal to 10 over here.
Nếu tính ra, bạn sẽ thấy nút này có giá trị 10. Có rồi thì ta chuyển giá trị này lên trên. Nghĩa là min có thể đạt được nhỏ hơn hoặc bằng 10 ở bên này.
We go down here. Max is looking at some things. Max says, I also already see a hundred. So I'm going to do better than or equal to a hundred.
Ta đi xuống đây. Max đang xem xét vài giá trị. Max nói: tôi đã thấy 100 rồi. Vậy tôi sẽ đạt được ít nhất là 100.
But min can force less than or equal to 10 over here and force 10 that side. So a hundred is worse. No matter what's here, doesn't matter. We can prune it.
Nhưng min có thể ép kết quả nhỏ hơn hoặc bằng 10 ở bên này và ép ra 10 ở phía đó. Nên 100 là tệ hơn. Dù ở đây có gì cũng không quan trọng. Ta có thể cắt tỉa nó.
G was correct. Doesn't need to be looked at. The hundred gets passed back up, and min concludes it's 10.
G đúng rồi. Không cần xem nó. Giá trị 100 được truyền lên, và min kết luận là 10.
And then the 10 gets passed back up. And now max knows they can get at least 10 over here. Now we can go down the other branch. Min has to look for things here.
Rồi giá trị 10 được truyền lên tiếp. Giờ max biết mình đạt được ít nhất 10 ở bên này. Giờ ta đi xuống nhánh còn lại. Min phải xem xét các giá trị ở đây.
As long as you haven't seen anything, you can't really say, I can skip the rest. So you have to go look here. Then here we're at a max.
Chừng nào chưa thấy gì thì bạn chưa thể nói được là tôi bỏ qua phần còn lại. Nên phải xem ở đây. Rồi ở đây ta đến một nút max.
Max has to look around. Hasn't seen anything yet. And min hasn't guaranteed anything above max. So there's nothing max could do here.
Max phải xem xét xung quanh. Chưa thấy gì cả. Và min chưa đảm bảo được gì phía trên max. Nên max chẳng làm gì được ở đây.
So we have to look at this one as 1. Then 2 is better. It becomes 2. Pass 2 back up.
Nên ta phải xem nút này là 1. Rồi 2 tốt hơn. Nó thành 2. Truyền 2 lên trên.
Now this node here can force something. It can force to be 2 or less. It specifically forced a 2 by going this way. Now I'll look over here.
Giờ nút này có thể ép được một giá trị. Nó có thể ép kết quả là 2 hoặc nhỏ hơn. Nó đã ép ra đúng 2 khi đi theo hướng này. Giờ tôi sẽ xem bên này.
Actually, we know that we can force 2. We look up to what max can force. Max on the path to the root can force 10.
Thật ra ta đã biết mình ép được 2. Ta nhìn lên xem max có thể ép được gì. Max trên đường về gốc có thể ép được 10.
So that means max will never let the game over here. This can get cut off. And we pass up the 2, and we're done. So L was also correct.
Nghĩa là max sẽ không bao giờ để ván đấu đi tới đây. Phần này có thể bị cắt bỏ. Ta truyền 2 lên và xong. Vậy L cũng đúng.
We chopped off L and G in our expansion and saved some time. OK. That was alpha-beta. In terms of intuition, probably one of the harder things to wrap your head around.
Ta đã cắt L và G khỏi quá trình mở rộng và tiết kiệm được thời gian. OK. Đó là alpha-beta. Về mặt trực giác, đây có lẽ là một trong những phần khó để nắm bắt.
But after you've seen a few more examples that you've done on your own, it'll probably start coming together pretty well.
Nhưng sau khi bạn tự làm thêm vài ví dụ thì có lẽ sẽ dần hiểu khá rõ.
Now, even when we use alpha-beta pruning and we have maybe only square root of the number of nodes to be expanded, it's still often too much.
Bây giờ, ngay cả khi dùng cắt tỉa alpha-beta và có thể chỉ phải mở rộng khoảng căn bậc hai số nút, thì vẫn thường là quá nhiều.
We cannot go all the way to the bottom of the tree. So what do we do? We do depth-limited search. So we might say instead of going to the bottom, we stop here.
Ta không thể đi hết xuống đáy của cây. Vậy ta làm gì? Ta dùng tìm kiếm giới hạn độ sâu. Tức là thay vì đi xuống tận đáy, ta dừng ở đây.
And we call these in some sense terminal nodes. They're not really terminal nodes. We say it's done after two moves and associate values with those nodes and then propagate that off.
Và ta gọi đó là các nút kết thúc theo một nghĩa nào đó. Chúng không thật sự là nút kết thúc. Ta coi như ván đấu xong sau hai nước đi, gán giá trị cho các nút đó rồi truyền lên.
That means if these are the actual values of those nodes, that's great. Typically, we wouldn't know the actual values, because that's exactly what we're trying to find. And we'll have some approximations there.
Nếu đây là giá trị thật của các nút đó thì tuyệt. Thường thì ta không biết giá trị thật, vì đó chính là thứ ta đang đi tìm. Và ta sẽ có vài giá trị xấp xỉ ở đó.
And we pass up the approximations. And we hope that these approximations are good enough. Remember A* heuristics, we had an approximation of distance to the goal? Same thing here.
Rồi ta truyền các giá trị xấp xỉ lên. Và hy vọng các giá trị xấp xỉ này đủ tốt. Nhớ hàm heuristic của A* chứ? Ta có giá trị xấp xỉ của khoảng cách đến đích. Ở đây cũng vậy.
We will have some approximation of value of that node and work with it instead of the real value to achieve something. In this case, solve for minimax with — well, evaluated against these numbers.
Ta sẽ có một giá trị xấp xỉ cho nút đó và dùng nó thay cho giá trị thật để đạt được mục đích. Trong trường hợp này là giải minimax với — à, được đánh giá dựa trên những con số này.
So now suppose we have a hundred seconds. We can explore 10,000 nodes per second. That means we can check a million nodes per move.
Giờ giả sử ta có một trăm giây. Ta có thể khám phá 10.000 nút mỗi giây. Nghĩa là ta kiểm tra được một triệu nút cho mỗi nước đi.
Alpha-beta can then reach a depth of about 8 on a decent chess program. So we would do this at depth 8. Guarantee of optimal play is gone, because these numbers will not be precise.
Khi đó alpha-beta có thể đạt độ sâu khoảng 8 trong một chương trình cờ vua khá tốt. Vậy ta sẽ làm việc này ở độ sâu 8. Không còn đảm bảo chơi tối ưu nữa, vì các con số này sẽ không chính xác.
And once they are not precise and we use them to decide what to do, we're not solving the actual game. We're solving some approximation that we hope is going to be good enough.
Và khi chúng không chính xác mà ta vẫn dùng để quyết định, thì ta không giải ván đấu thật. Ta giải một bài toán xấp xỉ mà ta hy vọng là đủ tốt.
And so the deeper we can go, the better, because then later we have to bring in our approximation.
Nên ta đi càng sâu càng tốt, vì như vậy phần phải dùng xấp xỉ sẽ đến muộn hơn.
And often in practice, if you don't know how much time you have left, you might run iterative deepening. You say, I'll go up to depth 2.
Và trong thực tế, nếu bạn không biết còn bao nhiêu thời gian, bạn có thể chạy iterative deepening. Bạn nói: tôi sẽ đi đến độ sâu 2.
And if I still have time left after I'm done, I run again up to depth 3. If I still have time left, I run up to depth 4.
Nếu xong mà vẫn còn thời gian, tôi chạy lại đến độ sâu 3. Nếu vẫn còn thời gian, tôi chạy đến độ sâu 4.
And just like we had when we tried to combine the best of breadth-first and depth-first search through iterative deepening and where the last search really takes all the time because it's the next level in a tree which is much larger than anything you've seen before, same thing here.
Và giống như trước đây khi ta cố kết hợp ưu điểm của tìm kiếm theo chiều rộng và chiều sâu thông qua iterative deepening, lần tìm kiếm cuối tốn gần hết thời gian vì đó là tầng kế tiếp của một cây lớn hơn nhiều so với mọi thứ bạn đã thấy trước đó, ở đây cũng vậy.
So very quickly, the shallow depths and you keep taking more and more time for next one, next one.
Các độ sâu nông chạy rất nhanh và bạn tốn ngày càng nhiều thời gian cho lần tiếp theo, rồi lần tiếp theo nữa.
But if at some time in that process your clock runs out, you have the solution from the previous search to tell you what to do.
Nhưng nếu đến lúc nào đó trong quá trình ấy mà hết giờ, bạn vẫn có lời giải từ lần tìm kiếm trước cho biết cần làm gì.
OK, let's take a look at this in action. So demo 6 — we run depth-limited minimax here or alpha-beta. It'll give the same result. Depth 2.
OK, giờ ta xem việc này chạy thực tế. Demo 6 — ở đây ta chạy minimax giới hạn độ sâu hoặc alpha-beta. Kết quả sẽ giống nhau. Độ sâu 2.
This is the behavior we get. What's going on here? Why does it keep thrashing back and forth? Well, let's think about this.
Đây là hành vi mà ta thu được. Chuyện gì đang xảy ra vậy? Tại sao nó cứ dao động qua lại? Để ta nghĩ thử xem.
We have Pac-Man in this world. Two options — left or right. Then only one option left, two options left.
Ta có Pac-Man trong thế giới này. Hai lựa chọn — trái hoặc phải. Rồi chỉ còn một lựa chọn bên trái, hai lựa chọn bên trái.
In our scoring, this would be a — let's see. 8 plus 10 for one dot, negative 2 for two time steps.
Trong cách tính điểm của ta, cái này sẽ là — để xem nào. 8 cộng 10 cho một chấm, trừ 2 cho hai bước thời gian.
This would be a — negative 2. And this would be also a 8.
Cái này sẽ là — âm 2. Và cái này cũng là 8.
So what happens here is that there are two options that are equally good. Going to the left or to the right is equally good.
Vậy ở đây có hai lựa chọn tốt như nhau. Đi sang trái hay sang phải đều tốt như nhau.
It doesn't really distinguish, breaks ties, and happens to go to the right. Then once it's here, it's effectively in a symmetric situation.
Nó không thực sự phân biệt được, nên chọn ngẫu nhiên, và tình cờ đi sang phải. Rồi khi đã ở đây, về cơ bản nó lại ở trong tình huống đối xứng.
Happens to break ties the other way, go to the left, keeps going back and forth. Because what is it doing? It's solving a new type of game. It's not solving the original game.
Lần này tình cờ chọn ngược lại, đi sang trái, và cứ thế đi qua đi lại. Vì nó đang làm gì? Nó đang giải một loại trò chơi mới. Nó không giải trò chơi gốc.
It's solving the game, if I look 2 ahead, what is the best thing to do as my first move?
Nó giải trò chơi: nếu nhìn trước 2 bước, nước đi đầu tiên tốt nhất là gì?
And if you only get to look 2 ahead, the best you can do is collect the food pellet. And it doesn't matter which direction you start.
Và nếu chỉ nhìn trước được 2 bước, điều tốt nhất có thể làm là ăn viên thức ăn. Và bắt đầu theo hướng nào cũng không quan trọng.
You can collect the food pellet in the next time step as needed. So that's the problem here.
Bạn có thể ăn viên thức ăn ở bước thời gian kế tiếp. Đó là vấn đề ở đây.
Our evaluation function by just looking at the score after two steps is not very indicative of how good that situation is. So maybe we need to use something better.
Hàm đánh giá của ta, chỉ nhìn vào điểm số sau hai bước, không phản ánh tốt việc tình huống đó tốt đến đâu. Nên có lẽ ta cần dùng thứ gì đó tốt hơn.
So if we look at it, this situation versus this situation, well, the one on the left is clearly better, because you already made progress getting to the next one.
Nếu so sánh tình huống này với tình huống kia, thì bên trái rõ ràng tốt hơn, vì bạn đã tiến được một đoạn tới chấm kế tiếp.
So maybe we should get a bonus here, a plus 1 or something, for getting already closer to the next one. Now we have a 8 plus 1 here.
Nên có thể ta cho thêm điểm thưởng, cộng 1 chẳng hạn, vì đã gần chấm kế tiếp hơn. Giờ ta có 8 cộng 1 ở đây.
This branch gives us 9. The other one gives us 8. And we will go that way. So this is one of the things you might see in your own agents too.
Nhánh này cho ta 9. Nhánh kia cho 8. Và ta sẽ đi hướng đó. Đây là một điều bạn có thể gặp ở các tác tử của chính mình nữa.
If your evaluation function is not good enough, doesn't give enough signal, and you only look that deep, you might get weird behaviors that are not what you're hoping for.
Nếu hàm đánh giá không đủ tốt, không cho đủ tín hiệu, và bạn chỉ nhìn sâu đến thế, bạn có thể thấy hành vi kỳ lạ, không phải điều bạn mong muốn.
But you can solve it by having a better evaluation function that better evaluates how good a situation is. Don't just use the score in the game. Use something smarter.
Nhưng bạn có thể giải quyết bằng một hàm đánh giá tốt hơn, đánh giá tình huống chính xác hơn. Đừng chỉ dùng điểm số của trò chơi. Hãy dùng thứ thông minh hơn.
So here's what it looks like when fixed.
Đây là kết quả sau khi sửa.
And it clears the board effectively. So what are these evaluation functions in practice? Imagine you're building one for the game of chess. We just heard that you can only go 8 deep.
Và nó ăn sạch bàn chơi. Vậy trong thực tế các hàm đánh giá này là gì? Hãy tưởng tượng bạn xây một hàm cho cờ vua. Ta vừa nghe là chỉ đi sâu được 8 tầng.
After 8 deep, usually the game's not over yet. How are you going to evaluate the board situation? Well, you might have heard things like the queen is worth a lot.
Sau 8 tầng thì thường ván cờ chưa kết thúc. Bạn sẽ đánh giá thế cờ thế nào? Có thể bạn đã nghe là quân hậu có giá trị rất lớn.
Maybe a rook is worth something. A bishop is worth something.
Quân xe có giá trị nào đó. Quân tượng cũng có giá trị nào đó.
And maybe you take a weighted sum of the quality scores of each of the pieces that you have left minus some weighted sum of the quality score of the pieces the opponent has left.
Và có thể bạn lấy tổng có trọng số điểm chất lượng của từng quân bạn còn lại trừ đi tổng có trọng số điểm chất lượng của các quân đối thủ còn lại.
But maybe you also have something about quality of the mobility on the board and so forth. So you come up with some way of evaluating the quality of the situation.
Nhưng có thể bạn còn thêm yếu tố về độ linh hoạt di chuyển trên bàn cờ, v.v. Vậy bạn nghĩ ra một cách nào đó để đánh giá chất lượng của tình huống.
And however good you make this will drastically affect how well your agent plays the game, because that is what it's going to use to evaluate what to do until you're very close to the end of the game, where you can search all the way till the end and use the actual outcome of the game.
Và hàm này tốt đến đâu sẽ ảnh hưởng mạnh đến việc tác tử chơi giỏi thế nào, vì đó là thứ nó dùng để quyết định nước đi cho đến khi gần cuối ván, lúc đó có thể tìm kiếm đến tận cuối và dùng kết quả thực của ván cờ.
So a lot of thinking can go into this. Also, often machine learning can go into this to learn what are good or bad positions to be in.
Nên có thể cần suy nghĩ rất nhiều ở đây. Cũng thường có thể dùng machine learning ở đây để học xem vị trí nào tốt hay xấu.
For example, for Pac-Man, let's say you design an evaluation function. You're in this situation here. You might say, oh, I have an evaluation function. You run it on the situation.
Ví dụ với Pac-Man, giả sử bạn thiết kế một hàm đánh giá. Bạn đang ở tình huống này. Bạn có thể nói, ồ, mình có hàm đánh giá. Bạn chạy nó trên tình huống đó.
You get a number back. Then you can sanity check. Now here is another situation — better or worse? Well, this might look worse.
Bạn nhận lại một con số. Rồi bạn có thể kiểm tra hợp lý. Đây là tình huống khác, tốt hơn hay tệ hơn? Cái này trông có vẻ tệ hơn.
If you think this is worse, you can check your evaluation function to see if indeed it gives this a worse score.
Nếu bạn nghĩ nó tệ hơn, hãy kiểm tra xem hàm đánh giá có thực sự cho nó điểm thấp hơn không.
If it doesn't, then maybe you should change your evaluation function or change your intuition and conclude that maybe this is better. How about this?
Nếu không, có thể bạn nên sửa hàm đánh giá hoặc sửa trực giác của mình và kết luận có lẽ cái này tốt hơn. Còn cái này thì sao?
Maybe even worse, because you're getting cornered more by the ghosts, getting closer to dead-ends than you were before. How about this? Even worse. Even worse.
Có thể còn tệ hơn, vì bạn bị lũ ma dồn vào góc nhiều hơn, gần đường cụt hơn so với trước. Còn cái này? Còn tệ hơn nữa. Tệ hơn nữa.
And so you want to have a few sample situations for which you evaluate your evaluation function and inspect that indeed it gives you good numbers back.
Vậy bạn nên có vài tình huống mẫu để chạy hàm đánh giá của mình và kiểm tra xem nó có thực sự cho ra các con số hợp lý.
So now we're going to look at it from the perspective of the ghosts. So the ghosts also run minimax. They're just the opposite player.
Bây giờ ta sẽ nhìn từ góc độ của lũ ma. Lũ ma cũng chạy minimax. Chúng chỉ là người chơi đối lập.
Here's what you get with ghosts running minimax.
Đây là kết quả khi lũ ma chạy minimax.
They can't think all the way till the end of the game. So they use an evaluation function. The evaluation function says getting closer to Pac-Man is good.
Chúng không thể nghĩ đến tận cuối ván. Nên chúng dùng hàm đánh giá. Hàm đánh giá nói rằng đến gần Pac-Man là tốt.
But then at the end, something else happens. Why does the behavior change at the end? Let's look at this again.
Nhưng rồi ở cuối, có điều khác xảy ra. Tại sao hành vi thay đổi ở cuối? Hãy xem lại.
What's happening here? You evaluate based on evaluation function. You can't get to the end of the game in your search. Evaluation function says close to Pac-Man is good.
Chuyện gì đang xảy ra ở đây? Bạn đánh giá dựa trên hàm đánh giá. Tìm kiếm của bạn chưa tới được cuối ván. Hàm đánh giá nói gần Pac-Man là tốt.
But then you're at a point where you can get to the end of the game, which once you realize that this is how you can finish up the game and that's what you're going to do.
Nhưng rồi đến lúc bạn có thể tới cuối ván, và khi nhận ra rằng đây là cách để kết thúc ván chơi và đó chính là điều bạn sẽ làm.
Here's a zoomed-in version.
Đây là phiên bản phóng to.
Even more difficult situation. So the ghosts initially will just try to follow Pac-Man. But when they can look till the end of the game, they'll change their strategy, and flank, and win.
Một tình huống còn khó hơn nữa. Lúc đầu các con ma chỉ cố bám theo Pac-Man. Nhưng khi chúng nhìn được đến tận cuối trò chơi, chúng sẽ đổi chiến thuật, đánh chặn hai bên, và thắng.
Depth matters. The deeper you can look by being fast at computing things, the better your evaluations will be. Your evaluation function will typically be better closer to the end of the game.
Độ sâu rất quan trọng. Bạn tính toán càng nhanh thì càng nhìn được sâu, và đánh giá của bạn càng tốt. Hàm đánh giá thường tốt hơn khi gần cuối trò chơi.
There's a trade-off here. If you spend a lot of time on your evaluation function computationally, you'll have less time to run search, just like in A*.
Ở đây có một sự đánh đổi. Nếu bạn tốn nhiều thời gian tính toán cho hàm đánh giá, bạn sẽ có ít thời gian hơn để chạy tìm kiếm, giống như trong A*.
If your heuristic function is very expensive, then you don't have as much time to run the search.
Nếu hàm heuristic của bạn rất tốn kém, thì bạn không còn nhiều thời gian để chạy tìm kiếm.
What does limited depth do to you? Here is a limited-depth execution. Pac-Man — well, execution's also probably the right way to phrase the outcome.
Giới hạn độ sâu gây ra hậu quả gì? Đây là một lần chạy với độ sâu giới hạn. Pac-Man... à, nói là bị "hành quyết" có lẽ đúng hơn để mô tả kết quả.
Pac-Man's looking only 2 ahead. What happens?
Pac-Man chỉ nhìn trước 2 bước. Chuyện gì xảy ra?
Doesn't know what to do. Gets eaten. But what if Pac-Man can look much — oh, wrong one. This one is unsolvable.
Không biết phải làm gì. Bị ăn mất. Nhưng nếu Pac-Man nhìn xa hơn nhiều... à, nhầm cái rồi. Cái này không giải được.
What if you look much further ahead? What if you can look 10 steps ahead? What can you do?
Nếu nhìn xa hơn nhiều thì sao? Nếu bạn nhìn trước được 10 bước thì sao? Bạn làm được gì?
You can actually anticipate that once blue chooses which way to go, they'll keep going that way.
Bạn có thể dự đoán rằng một khi con xanh chọn hướng đi, nó sẽ cứ đi hướng đó.
So if you can just hold off — rather than running away from the red ghost, run towards it to hold off and gain time to see where blue is headed, and then choose where you go — you can actually win this game.
Vậy nếu bạn cứ cầm chân được... thay vì chạy trốn con ma đỏ, hãy chạy về phía nó để câu giờ xem con xanh đi đâu, rồi mới chọn hướng đi của mình... thì bạn thực sự có thể thắng ván này.
And so this is an example of looking further ahead, giving you the edge compared to an agent that doesn't look nearly as far ahead.
Đây là ví dụ cho thấy nhìn xa hơn giúp bạn có lợi thế so với một tác tử không nhìn xa được như vậy.
One thing you might wonder — are there any synergies between what we've seen in terms of evaluation functions in alpha-beta pruning? We've looked at them as two orthogonal things.
Bạn có thể thắc mắc: liệu có sự phối hợp nào giữa những gì ta đã thấy về hàm đánh giá và cắt tỉa alpha-beta không? Ta đã xem chúng như hai thứ độc lập.
Evaluation function is a way to call a node a terminal node effectively rather than keep searching. Alpha-beta is a way to skip parts of the tree.
Hàm đánh giá là cách để coi một nút như nút kết thúc thay vì tiếp tục tìm kiếm. Alpha-beta là cách bỏ qua các phần của cây.
Well, the amount of pruning you get in alpha-beta depends on the expansion ordering. The evaluation function can give you guidance about what to expand first.
Mức độ cắt tỉa bạn đạt được trong alpha-beta phụ thuộc vào thứ tự mở rộng. Hàm đánh giá có thể gợi ý nên mở rộng nút nào trước.
We said that if you find good options first, then you get to prune more.
Ta đã nói nếu tìm được lựa chọn tốt trước, thì sẽ cắt tỉa được nhiều hơn.
Well, the evaluation function for your successor nodes can tell you which successor nodes are more promising for you and which ones are less promising.
Hàm đánh giá cho các nút kế tiếp có thể cho biết nút kế tiếp nào triển vọng hơn và nút nào kém triển vọng hơn.
You can go to the more promising ones first and that way increase the amount of pruning you get in alpha-beta pruning.
Bạn đi vào các nút triển vọng hơn trước và nhờ vậy tăng mức độ cắt tỉa trong cắt tỉa alpha-beta.
Another thing that's happening is the value of a min node will keep going down.
Một điều nữa là giá trị của nút min sẽ cứ giảm dần.
Once a value of a min node is lower than a better option available to max on the path to the root, you can stop. Here's an alternative how to decide to stop.
Khi giá trị của một nút min thấp hơn một lựa chọn tốt hơn mà max có trên đường về gốc, bạn có thể dừng. Đây là một cách khác để quyết định dừng.
If you have an evaluation function that is a bound — you say, I evaluate this node. And I know that the value of this node is this much or less.
Nếu hàm đánh giá của bạn là một cận... bạn nói: tôi đánh giá nút này. Và tôi biết giá trị của nút này nhiều nhất là bấy nhiêu.
And if the evaluation function is quick, you can quickly evaluate whether you get a certain value or less at a specific node. That is enough information to potentially already prune.
Nếu hàm đánh giá nhanh, bạn có thể nhanh chóng xác định liệu tại một nút cụ thể ta đạt một giá trị nhất định hoặc thấp hơn hay không. Thông tin đó đã đủ để có thể cắt tỉa ngay.
So rather than going down your first child and hope you find something that is promising that allows you to prune, your evaluation function, if it's a bound in the right direction, will also allow you to already prune.
Vậy thay vì đi xuống nút con đầu tiên và hy vọng tìm được thứ triển vọng giúp bạn cắt tỉa, hàm đánh giá của bạn, nếu là một cận đúng hướng, cũng cho phép bạn cắt tỉa ngay.
I strongly encourage you to think about these two ideas a little bit on your own time, because I think if you fully understand what's going on here, that means you have a lot of the intuition in place of everything we covered in this lecture.
Tôi rất khuyến khích các bạn tự suy nghĩ thêm về hai ý tưởng này, vì tôi nghĩ nếu bạn hiểu trọn vẹn chuyện gì đang diễn ra ở đây, nghĩa là bạn đã nắm phần lớn trực giác về mọi thứ ta đã học trong bài này.
See you next time, and we'll cover uncertainty.
Hẹn gặp lại lần sau, và ta sẽ học về sự bất định.
[SIDE CONVERSATION] [NO AUDIO]
[CUỘC TRÒ CHUYỆN RIÊNG] [KHÔNG CÓ ÂM THANH]
Đă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.