Elements of AI - Search and games

Elements of AI

III.Search and games

In this section, we will study a classic AI problem: games. The simplest scenario, which we will focus on for the sake of clarity, are two-player, perfect-information games such as tic-tac-toe and chess.

이 섹션에서는 고전적인 AI 문제인 게임을 연구합니다. 우리가 해야할 일을 분명히 드러내 주는 가장 간단한 시나리오는 tic-tac-toe와 chess와 같은 2 인용 perfect-information 게임입니다.

Example: playing tic tac toe

Maxine and Minnie are true game enthusiasts. They just love games. Especially two-person, perfect information games such as tic-tac-toe or chess. One day they were playing tic-tac-toe. Maxine, or Max as her friends call her, was playing with X. Minnie, or Min as her friends call her, had the Os. Min had just played her turn and the board looked as follows:

Maxine과 Minnie는 진정한 게임 애호가입니다. 그들은 그냥 게임을 좋아합니다. 특히 2 인용 perfect-information 게임인 tic-tac-toe 또는 chess와 같은 게임을 좋아합니다. 어느 날 그들은 tic-tac-toe 게임을 하고 있었습니다. Maxine -그녀의 친구는 Max라고 부릅니다 - 은 X를 선택했고 Minnie, - 친구들은 Min 이라고 부릅니다 - 는 O를 선택했습니다. Min이 방금 자신의 차례를 마쳤습니다. 현재 말판은 아래와 같습니다.

Max was looking at the board and contemplating her next move, as it was her turn, when she suddenly buried her face in her hands in despair, looking quite like Garry Kasparov playing Deep Blue in 1997.

맥스는 그 말판을 보고 나서 다음 수를 깊이 고민했습니다. 그녀가 둘 차례거든요. 그러더니 손으로 얼굴을 감싸고 절망에 빠졌습니다. 흡사 1997년 딥불로와 경기하던 Garry Kasparov와 비슷한 모습이었습니다.

Yes, Min was close to getting three Os on the top row, but Max could easily put a stop to that plan. So why was Max so pessimistic?

그렇습니다. 민은 맨 윗줄에 세 개의 O를 만들기 직전이었습니다. 그런데 맥스는 그걸 막을 수 있는 상황이죠. 그런데 맥스는 왜 절망적일까요? 

Game trees

To solve games using AI, we will introduce the concept of a game tree. The different states of the game are represented by nodes in the game tree, very similar to the above planning problems. The idea is just slightly different. In the game tree, the nodes are arranged in levels that correspond to each player's turns in the game so that the “root” node of the tree (usually depicted at the top of the diagram) is the beginning position in the game. In tic-tac-toe, this would be the empty grid with no Xs or Os played yet. Under root, on the second level, there are the possible states that can result from the first player’s moves, be it X or O. We call these nodes the “children” of the root node.

AI를 사용하여 게임을 해결하기 위해 게임 트리 개념을 소개합니다. 게임의 여러 states는 게임 트리에서 노드라는 것으로 표현됩니다. 위의 planning problems와 매우 유사하죠. 아이디어는 약간 다릅니다. 게임 트리에서 노드는 레벨들로 정열되는데 게임에서 각 플레이어의 차례와 서로 관련이 되어 있습니다. 그러니까 트리의 “root” node는 (대개 다이어그램의 맨 위에 표시되죠) 게임의 시작지점 입니다.  tic-tac-toe에서는 아직 경기가 시작되지 않은 상태는 X 또는 O가없는 빈 그리드입니다. 루트 아래 두 번째 레벨에는 X 또는 O와 같은 첫 번째 플레이어의 이동으로 인해 발생할 수있는 states가 있습니다. 이러한 노드를 루트 노드의 "하위 children"라고합니다.

Each node on the second level, would further have as its children nodes the states that can be reached from it by the opposing player's moves. This is continued, level by level, until reaching states where the game is over. In tic-tac-toe, this means that either one of the players get a line of three and wins, or the board is full and the game ends in a tie.

두 번째 레벨의 각 노드는 상대방 플레이어의 이동에 의해 이루어 질 수있는 states를 children 노드로 추가로가집니다. 이것은 게임이 끝난 상태에 도달 할 때까지 수준별로 계속됩니다. tic-tac-toe의 경우, 이것은 플레이어 중 한 명이 3 개의 라인을 얻었거나 보드가 꽉 차서 게임이 무승부인 상황을 의미합니다.

Minimizing and maximizing value

In order to be able to create game AI that attempts to win the game, we attach a numerical value to each possible end result. To the board positions where X has a line of three so that Max wins, we attach the value +1, and likewise, to the positions where Min wins with three Os in a row we attach the value -1. For the positions where the board is full and neither player wins, we use the neutral value 0. (It doesn’t really matter what the values are as long as they in this order so that Max tries to maximize the value, and Min tries to minimize it.)

게임에서 이기려고 하는 게임 AI를 만들기 위해 우리는 각 가능한 최종 결과에 숫자 값을 부여 합니다. 말판에 X 세개가 나란히 있어서 Max가 이기는 경우 우리는 값 +1을 부여하고 마찬가지로 Min이 3 개의 O로 한 줄을 만들면 우리는 값 -1을 첨부합니다. 보드가 꽉 차서 무승부가 되는 경우, 중립적 인 값 0을 사용합니다. (값이 무엇인지는 그렇게 중요하지 않습니다. 단지 맥스는 그 숫자를 최대한도로 크게하려고 할 겁니다. 그리고 민은 그 값을 최소한도로 하려고 할 것이구요. )

A sample game tree

Consider, for example, the following game tree which begins not at the root but in the middle of the game (because otherwise, the tree would be way too big to display). Note that this is different from the game shown in the illustration in the beginning of this section. We have numbered the nodes with numbers 1, 2, ..., 14.

예를 들어 루트에서 시작하지 않고 게임 중간에 시작하는 다음 게임 트리를 보겠습니다. (그렇지 않으면 트리가 너무 커서 표시 할 수 없기 때문입니다). 이것은 이 섹션 시작 부분의 그림에 표시된 게임과 다릅니다. 우리는 노드에 번호 1, 2, ..., 14로 번호를 매겼습니다.

The tree is composed of alternating layers where it is either Min's turn to place an O or Max's turn to place an X at any of the vacant slots on the board. The player whose turn it is to play next is shown at the left.

트리는 말판은 민의 차례에 O를 빈 슬롯에 놓거나 맥스의 차례에 X 를 빈 슬롯에 놓는 경우들을 사용해 구성됩니다. 다음에 둘 사람 이름이 왼쪽에 있습니다.

The game continues at the board position shown in the root node, numbered as (1) at the top, with Min’s turn to place O at any of the three vacant cells. Nodes (2)–(4) show the board positions resulting from each of the three choices respectively. In the next step, each node has two possible choices for Max to play X each, and so the tree branches again.

게임은 맨 위의 (1) 번으로 번호가 매겨진 루트 노드에 표시된 말판 위치에서 계속 이어집니다. 민의 차례인데요 비어있는 칸에 O를 놓을 수 있습니다. 노드 2~4는 민이 둘 수 있는 3가지 가능성을 보여 줍니다. 그 다음 단계는 맥스가 둘 수 있는 칸이 두개가 되겠죠. 민이 선택할 수 있는 3개의 경우 각각 마다 맥스는 두 개의 가능성이 있습니다.

When starting from the above starting position, the game always ends in a row of three: in nodes (7) and (9), the winner is Max who plays with X, and in nodes (11)–(14) the winner is Min who plays with O.

3번째 줄 다음 민이 둘 수 있는 경우를 보면 7번과 9번의 경우 X 세개가 나란히 이어져서 맥스가 이겨 버리죠. 게임 끝입니다. 민이 더 이상 둘 수 없는 경우이죠. 그리고 4번째 줄을 보면 4개의 경우 전부 다 O을 잡고 있는 민이 이기는 경우입니다.

Note that since the players’ turns alternate, the levels can be labelled as Min levels and Max levels, which indicates whose turn it is.

두 경기자가 번갈이 두는 게임이기 때문에 각 레벨마다 민과 맥스가 번갈아 가며 표시됩니다. 그건 그 사람이 둘 차례라는 겁니다.

Being strategic

Consider nodes (5)–(10) on the second level from the bottom. In nodes (7) and (9), the game is over, and Max wins with three X’s in a row. The value of these positions is +1. In the remaining nodes, (5), (6), (8), and (10), the game is also practically over, since Min only needs to place her O in the only remaining cell to win. In other words, we know how the game will end at each node on the second level from the bottom. We can therefore decide that the value of nodes (5), (6), (8), and (10) is also –1.

아래에서 두번째 레벨에서 5~10의 경우들을 보세요. 7번과 9번은 게임 끝입니다. 맥스가 이기죠. 이 포지션들의 값은 +1 입니다. 다른 녿들은 5,6,8 그리고 10번 노드들도 사실상 경기 끝이죠. 다음번에 민이 O을 둘 차례인데 어디에 둬도 민이 이기죠. 우리는 밑에서 두번째 단계에서 이미 누가 이길 것인지 알 수 있습니다. 그러므로 우리는 5,6,8 그리고 10번 노드의 경우 -1을 주게 됩니다.

Here comes the interesting part. Let’s consider the values of the nodes one level higher towards the root: nodes (2)--(4). Since we observed that both of the children of (2), i.e., nodes (5) and (6), lead to Min’s victory, we can without hesitation attach the value -1 to node (2) as well. However, for node (3), the left child (7) leads to Max’s victory, +1, but the right child (8) leads to Min winning, -1. What is the value of node (3)? Think about this for a while, keeping in mind who makes the choice at node (3).

여기서 이제 흥미로운 부분이 나타납니다. 그 윗단계 레벨을 보죠. 노드 2~4번이요. 2번 노드의 children 노드인 5번과 6번은 민의 승리로 이끕니다. 즉 노드 2번에 우리는 당연히 -1 값을 부여할 수 있겠죠.  그런데 노드 3의 자식 노드 중 7 번 노드는 맥스의 승리로 돌아갑니다. 값은 +1이죠. 하지만 그 오른쪽에 있는 8번 노드는 민의 승리로 이어집니다. 8번 노드는 -1이죠. 그럼 노드 3의 값은 무엇일까요? 잠깐 생각해 보세요. 누가 노드 3번을 선택하는 경우인지 생각해 보세요.

Since it is Max’s turn to play, she will of course choose the left child, node (7). Thus, every time we reach the board position in node (3), Max can ensure victory, and we can attach the value +1 to node (3).

위에서 두번 째 레벨은 맥스가 둘 차례입니다. 당연히 맥스는 노드 7번을 선택하겠죠. 그렇게 되면 노드 3에서 우리는 맥스가 이길거라는 것을 미루어 짐작할 수 있습니다. 그러므로 우리는 노드 3에 +1을 부여할 수 있습니다.

The same holds for node (4): again, since Max can choose where to put her X, she can always ensure victory, and we attach the value +1 to node (4).

이건 노드 4번도 마찬가지입니다. 맥스는 노드 9번을 선택할 것이고 그러면 그녀는 이기게 됩니다. 그러므로 노드 4번에도 우리는 +1을 부여할 겁니다.

Determining who wins

The most important lesson in this section is to apply the above kind of reasoning repeatedly to determine the result of the game in advance from any board position.

이 섹션에서 가장 중요한 부분은 위와 같은 reasoning을 계속 적용해 나감으로서 말판의 어떤 포지션에 두든지 그에 이은 게임의 결과를 미리 알아가는 겁니다.

So far, we have decided that the value of node (2) is –1, which means that if we end up in such a board position, Min can ensure winning, and that the reverse holds for nodes (3) and (4): their value is +1, which means that Max can be sure to win if she only plays her own turn wisely.

우리는 노드 2번에 -1 값을 부여했죠. 그 의미는 민이 이길거라는 겁니다. 그리고 노드 3번과 4번에는 +1을 부여했습니다. 즉 맥스가 실수만 하지 않으면 이길거라는 의미죠.

Finally, we can deduce that since Min is an experienced player, she can reach the same conclusion, and thus she only has one real option: play the O in the middle of the board.

민은 이 게임에 대한 경험이 많기 때문에 그녀는 오직 한가지 선택만이 있다는 것을 알 것이고 그렇기 때문에 그녀는 O를 말판 한 가운데요 둘 것입니다.

In the diagram below, we have included the value of each node as well as the optimal game play starting at Min's turn in the root node.

아래 다이어그램을 보면 우리는 각 노드들에 값을 부여했고 또 민의 차례인 루트 노드로부터 이어지는 optimal 경로를 표시했습니다.

The value of the root node = who wins

The value of the root node, which is said to be the value of the game, tells us who wins (and how much, if the outcome is not just plain win or lose): Max wins if the value of the game is +1, Min if the value is –1, and if the value is 0, then the game will end in a draw. In other games, the value may also take other values (such as the monetary value of the chips in front of you in poker for example).

루트 노드의 값은 이 게임 전체의 값이라고 할 수 있는데 이 값이 누가 이길 것인지 우리에게 알려 줄 겁니다. 이 게임의 값이 +1이면 맥스가 이기고 -1이면 민이 이기겠죠. 이 값이 0이면 무승부가 됩니다. 다른 게임들에서는 다른 값들을 가지게 될 겁니다. (예를 들어 포커판에 있는 칩같은 것들이 될 수 있죠.)

This all is based on the assumption that both players choose what is best for them and that what is best for one is the worst for the other (so called "zero-sum game").

이건 각 경기자가 실수 없이 최선의 곳에 둘 거라는 가정에 근거합니다. 어느 한 사람한테 최선이면 상대방에게는 최악이겠죠. 즉 제로섬 게임이 되는 겁니다.

Note

Finding the optimal moves

Having determined the values of all the nodes in the game tree, the optimal moves can be deduced: at any Min node (where it is Min’s turn), the optimal choice is given by the child node whose value is minimal, and conversely, at any Max node (where it is Max’s turn), the optimal choice is given by the child node whose value is maximal. Sometimes there are many equally good choices that are, well, equally good, and the outcome will be the same no matter which one of them is picked.

게임 트리의 모든 노드들에 해당하는 값을 다 놓고 나면 가장 좋은 경로를 찾아낼 수 있습니다. 민에게 optimal choice 는 그 아래 레벨의 노드들 중에서 좀 더 작은 값을 가지고 있는 노드로 가는 겁니다. 반대로 맥스에게는 아래 레벨의 노드들 중에서 더 큰 값을 가지고 있는 노드로 가는 것이 optimal choice 이겠죠. 가끔 여러개의 good choice들이 있을 수 있습니다. 똑같은 값으로 좋은 것이요. 그런 경우 그 중 아무거나 선택해도 그 결과는 같게 됩니다.

The Minimax algorithm

We can exploit the above concept of the value of the game to obtain an algorithm called the Minimax algorithm. It guarantees optimal game play in, theoretically speaking, any deterministic, two-person, perfect-information zero-sum game. Given a state of the game, the algorithm simply computes the values of the children of the given state and chooses the one that has the maximum value if it is Max’s turn, and the one that has the minimum value if it is Min’s turn.

Minimax 알고리즘이라는 알고리즘을 얻기 위해 게임의 value에 대한 위의 개념을 활용할 수 있습니다. 이론적으로 2인용 perfect-information zero-sum game에서 이 알고리즘은 optimal game play를 보장합니다. 게임의 상태가 주어지면 알고리즘은 단순히 주어진 상태의 자식 값을 계산하고 Max의 차례라면 최대 값을 가지며 Min의 차례라면 최소값을 갖는 것을 선택합니다.

The algorithm can be implemented using a few lines of code. However, we will be satisfied with having grasped the main idea. If you are interested in taking a look at the actual algorithm (alert: programming required) feel check out, for example, Wikipedia: Minimax.

이 알고리즘은 단 몇줄의 코딩으로 구현될 수 있습니다. 아마 그 아이디어에 충분히 만족감을 느낄 수 있을 텐데요. 관심이 있다면 실제 알고리즘을 한번 살펴 보세요. (프로그래밍 지식이 있어야 합니다)  

Sounds good, can I go home now?

As stated above, the Minimax algorithm can be used to implement optimal game play in any deterministic, two-player, perfect-information zero-sum game. Such games include tic-tac-toe, connect four, chess, Go, etc. (Rock-paper-scissors is not in this class of games since it involves information hidden from the other player; nor are Monopoly or backgammon which are not deterministic.) So as far as this topic is concerned, is that all folks, can we go home now? The answer is that in theory, yes, but in practice, no.

위에서 언급했듯이, Minimax 알고리즘은 결정론적이며 2 인용의 perfect-information zero-sum game에서 최적의 게임 플레이를 구현하는 데 사용할 수 있습니다. 이러한 게임에는 tic-tac-toe, connect four, 체스, 바둑 등이 포함됩니다 (Rock-paper-scissors는 다른 플레이어로부터 information hidden 숨겨진 정보를 포함하기 때문에 이 클래스의 게임에 속하지 않습니다. 결정론적이지 않은 Monopoly 또는 backgammon -주사위놀이-도 아닙니다 ) 이제 이 주제에 대해서는 다 끝난 걸까요? 이제 집에 가도 될까요? 이론적으로는 에스인데 실제로는 노 입니다

Note

The problem of massive game trees

In many games, the game tree is simply way too big to traverse in full. For example, in chess the average branching factor, i.e., the average number of children (available moves) per node is about 35. That means that to explore all the possible scenarios up to only two moves ahead, we need to visit approximately 35 x 35 = 1225 nodes -- probably not your favorite pencil-and-paper homework exercise... A look-ahead of three moves requires visiting 42875 nodes; four moves 1500625; and ten moves 2758547353515625 (that’s about 2.7 quadrillion) nodes. In Go, the average branching factor is estimated to be about 250. Go means no-go for Minimax.

많은 게임에서 게임 트리가 너무 커서 전체를 traverse 할 수 없습니다. 예를 들어, 체스에서 평균 분기 요인, 즉 노드 당 평균 자식 수 (사용 가능한 이동 수)는 약 35입니다. 즉, 가능한 모든 시나리오를 탐색하기 위해 두번의 이동 만 해도 약 35 x 35 = 1225 노드를 가져야 합니다. - 단순히 종이에 연필로 그려가면서 할 일은 아니죠 -. 3번의 이동을 하면 42875 개의 노드를 만들어야 합니다. 네번이면 1500625; 10 번이면 2758547353515625 (약 2.7 조 천억)개의 노드가 있습니다. 바둑 에서 평균 분기 계수는 약 250개로 추정됩니다. Go (바둑)는 Minimax를 사용하기에는 no-go 이죠.

More tricks: Managing massive game trees

A few more tricks are needed to manage massive game trees. Many of them were crucial elements in IBM’s Deep Blue computer defeating the chess world champion, Garry Kasparov, in 1997.

거대한 게임 트리를 관리하려면 좀 더 많은 트릭들이 필요합니다. 그 트릭들 중 대부분은 1997년 세계 체스 챔피언 Garry Kasparov를 물리친 IBM의 딥블루 컴퓨터에서 사용됐었습니다.

If we can afford to explore only a small part of the game tree, we need a way to stop the minimax recursion before reaching an end-node, i.e., a node where the game is over and the winner is known. This is achieved by using a so called heuristic evaluation function that takes as input a board position, including the information about which player’s turn is next, and returns a score that should be an estimate of the likely outcome of the game continuing from the given board position.

우리가 게임 트리의 작은 부분만을 탐색 할 수 있다면, 게임의 끝까지 (엔드 노드) 가기 전에 이 미니맥스 recursion (재귀)를 멈출 필요가 있습니다. 왜냐하면 이미 게임의 결과를 알 수 있는 지점이 있을 것이 거든요. 이것은 heuristic evaluation function 이라고 불리는 방법을 사용해서 구현할 수 있습니다. 이 함수는 어느 플레이어가 둘 차례인지를 포함한 말판 (보드) 포지션을 인자로 받습니다. 그리고 주어진 말판 포지션에서 게임을 계속 하면 그 결과는 어떨 것인지를 추정할 수 있는 score를 return 합니다.

Note

Good heuristics

Good heuristics for chess, for example, typically count the amount of material (pieces) weighted by their type: the queen is usually considered worth about two times as much as a rook, three times a knight or a bishop, and nine times as much as a pawn. The king is of course worth more than all other things combined since losing it amounts to losing the game. Further, occupying the strategically important positions near the middle of the board is considered an advantage and the heuristic assign higher value to such positions.

예를 들어, 체스에 대한 Good heuristics는 일반적으로 type에 따라 weighted 된 체스 말의 수를 계산합니다. 여왕은 루크의 약 2 배, 기사나 비숍의 3배의 가치를 가지고 pawn (졸) 보다 9배 높은 가치를 가집니다. 킹은 물론 다른 모든 말들을 합친 것 보다 더 높은 가치를 가지죠. 왜냐 하면 왕을 잃으면 게임에 지게 되기 때문이죠. 또한, 보드의 중앙 부근에서 전략적으로 중요한 위치를 차지하는 것이 이점으로 간주되며, heuristic 은 그러한 위치에 더 높은 가치를 부여합니다.

위에서 제시 한 미니 맥스 알고리즘은 많지 않은 경우의 수가 있는 depth-limited version에서 사용 되기에 적합하고 이 heuristic는 주어진 depth limit에서의 모든 노드들을 return하게 됩니다. depth는 heuristic evaluation function을 적용하기 전에 게임트리가 확장되는 스텝들의 갯수를 의미합니다.

The minimax algorithm presented above requires minimal changes to obtain a depth-limited version where the heuristic is returned at all nodes at a given depth limit: the depth simply refers to the number of steps that the game tree is expanded before applying a heuristic evaluation function.

이 단원 초기에 얘기한 tic-tac-toe game으로 되돌아 가 보죠. 맥스는 지지 않으려면 맨 윗줄에  X를 놓아야 합니다.

Now it's Min's turn to play an O. Evaluate the value of this state of the game as well as the other states in the game tree where the above position is the root, using the Minimax algorithm.

이제 O를 두어야 할 민의 차례입니다. 미니맥스 알고맂ㅁ을 사용하여 위의 상태를 루트로 놓고 그 아래 놓일 수 있는 자식 상태들에 대해 값을 계산해 넣습니다.

Your task:

Look at the game tree starting from the below board position. Using a pencil and paper, fill in the values of the bottom-level nodes where the game is over. Note that this time some of the games end in a draw, which means that the values of the nodes is 0 (instead of –1 or 1).

과제

아래 게임 트리를 보세요. 연필과 종이를 이용해서 맨 마지막 레벨의 values를 정해서 넣어 보세요. 몇개의 노드들은 무승부를 나타냅니다. 이 경우 해당 노드의 값은 0 입니다.

Next continue filling the values of the nodes in the next level up. Since there is no branching at that level, the values on the second lowest level are the same as at the bottom level.

그 윗 단계의 노드들에도 값을 넣으세요. 그 레벨에서는 어떤 노드도 분기를 하지 않으므로 값은 맨 마지막 노드와 같게 됩니다.

On the second highest level, fill in the values by choosing for each node the maximum of the values of the child nodes – as you notice, this is a MAX level. Finally, fill in the root node's value by choosing the minimum of the root node's child nodes' values. This is the value of the game.

위에서 두번째 레벨에 있는 노드들에 값을 넣어 보세요. 값은 자식 노드들의 값 중 가장 큰 값을 넣습니다. 보시다 시피 이 레벨은 맥스가 둘 차례입니다. 마지막으로 루트 노드에 루트 노드의 자식 노드들의 값 들 중 가장 작은 값을 넣어 보세요. 이 값이 바로 이 게임의 값 입니다.

Enter the value of the game as your answer.

Note

The limitations of plain search

It may look like we have a method to solve any problem by specifying the states and transitions between them, and finding a path from the current state to our goal. Alas, things get more complicated when we want to apply AI in real world problems. Basically, the number of states in even a moderately complex real-world scenario grows out of hand, and we can’t find a solution by exhaustive search (“brute force”) or even by using clever heuristics.

우리는 상태와 전환을 지정하고 현재 상태에서 목표까지의 경로를 찾는 것으로 문제를 해결할 수있는 방법을 찾은 것 같습니다. 그런데, 현실 문제에 인공 지능을 적용하려면 상황이 훨씬 복잡해집니다. 기본적으로, #### 실제 세상에 있는 크게 복잡하지 않은 그냥 중간 정도의 시나리오의 states의 갯수도 그냥 손으로 해결하기에는 너무 많습니다. exhaustive search (“brute force”)로는 솔루션을 찾을 길이 없습니다. clever heuristics를 사용한다 해소 상황은 마찬가지 입니다.

Moreover, the transitions which take us from one state to the next when we choose an action are not deterministic. This means that whatever we choose to do will not always completely determine the outcome because there are factors that are beyond our control, and that are often unknown to us.

더군다나 우리가 행동을 선택할 때 한 상태에서 다음 상태로 우리를 이동시키는 전환은 deterministic 이지 않습니다. 즉, 어떤 것을 하기 위해 우리가 무엇을 선택하던지 간에 그 outcome은 완전한 determine 이지 않습니다. 왜냐하면 거기에는 우리의 통제를 벗어나는 요인이 있고 그것들은 종종 우리들이 알지 못하는 것들이기 때문입니다. 

The algorithms we have discussed above can be adapted to handle some randomness, for example randomness in choosing cards from a shuffled deck or throwing dice. This means that we will need to introduce the concept of uncertainty and probability. Only thus we can begin to approach real-world AI instead of simple puzzles and games. This is the topic of Chapter 3.

위에서 논의한 알고리즘은 randomness 무작위성을 다루기 위해 적용될 수 있습니다. 예를 들어, shuffled deck 또는 주사위 던지기에서 임의의 카드를 선택하는 것과 같습니다. 이것은 불확실성과 확률이라는 개념을 도입 할 필요가 있음을 의미합니다. 그럼으로서 우리는 단순한 퍼즐과 게임 대신 현실 세계의 AI에 접근 할 수 있게 됩니다. 이것이 제 3 장의 주제입니다.

After completing Chapter 2 you should be able to:

• Formulate a real-world problem as a search problem

• Formulate a simple game (such as tic-tac-toe) as a game tree

• Use the minimax principle to find optimal moves in a limited-size game tree