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 문제인 ‘게임’에 대해 공부합니다. 명확성을 위해 가장 간단한 시나리오에 중점을 두는데, 이는 틱택토 및 체스와 같은 2인용의 완전정보게임(perfect information games)입니다.

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인용의 완전정보 게임을 즐깁니다. 하루는 틱택토 게임을 하고 있었습니다. 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.

Max의 차례가 되었고, 그녀는 게임판을 쳐다보며 고심하다 낭패라는 듯 돌연 손에 얼굴을 파묻었습니다. 마치 1997년에 Deep Blue(IBM이 만든 체스 컴퓨터) 가리 카스파로프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?

Min이 맨 윗 줄에 3개의 O를 만들기 일보직전이긴 했지만, Max가 쉽게 막아낼 수도 있었습니다. 그렇다면 Max는 왜 그렇게 비관적이었을까요?

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를 사용하여 게임을 해결하기 위해, 우선 게임 트리라는 개념을 소개하려 합니다. 게임의 여러가지 상태state는 게임 트리의 노드로 표시되며 앞서 언급한 계획planning 문제와 매우 유사하되, 아주 조금 다릅니다. 게임 트리에서 노드는 게임에서 각 플레이어의 차례를 의미하는 각 레벨에 맞춰 배열되므로, 트리의 (주로 트리 그림의 맨 위에 표시되는) "루트" 노드는 게임의 시작 위치를 의미합니다. 틱택토에서는 X나 O 표시가 없는 빈 격자판에 해당합니다. 루트 노드 아래의 두 번째 레벨에는 첫 번째 플레이어의 움직임(X 또는 O)으로부터 발생할 수 있는 상태들 있습니다. 이러한 노드들을 루트 노드의 "자식"이라고 부릅니다.

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 gets a line of three and wins, or the board is full and the game ends in a tie.

두 번째 레벨의 각 노드는 상대 플레이어의 움직임으로 도달 할 수 있는 상태를 그 자식 노드로 가질 수 있습니다. 이 과정을 게임이 끝날 때까지 레벨별로 계속 진행합니다. 틱택토에서 게임이 끝난다는 것은 플레이어 중 한 명이 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 are in this order so that Max tries to maximize the value, and Min tries to minimize it).

가치 최소화 및 최대화

게임에서 이기기 위한 게임 AI를 만들기 위해, 가능한 모든 최종 결과 각각에 숫자 값을 붙여줍니다. 게임판에 3개의 X가 연속하는 라인이 생겨 Max가 이기는 경우에 대해 +1의 값을 붙이고, 마찬가지로 3개의 O가 연속하는 라인이 생겨 Min이 이기는 경우에 대해 -1의 값을 붙입니다. 보드가 꽉 차서 비기는 경우는 중립 값 0을 붙입니다 (Max는 값을 최대화하려고 하고, Min은 최소화하려고 하기 때문에 이 순서에 있는 한 어떤 값을 붙이는지는 중요하지 않습니다).

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.

트리는 게임판의 빈 칸에 Min이 O를 놓을 차례와 Max가 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)로 번호를 매긴, 루트 노드에 표시된 게임판부터 게임을 계속합니다. Min은 3 개의 빈칸 중 하나에 O를 놓을 차례입니다. 노드 (2) ~ (4)는 세 가지 선택 각각에서의 게임판 상황을 보여줍니다.

다음 단계의 각 노드에서 Max가 X를 놓을 수 있는 선택지가 두 가지이므로, 트리의 갈래가 나뉩니다.