검색 및 게임

이 섹션에서는 고전적인 AI 문제인 게임을 연구합니다. 명확성을 위해 집중할 가장 간단한 시나리오는 tic-tac-toe 및 체스와 같은 2인용 완벽한 정보 게임입니다.

예: 틱택토 게임하기

Maxine과 Minnie는 진정한 게임 매니아입니다. 그들은 단지 게임을 좋아합니다. 특히 tic-tac-toe나 체스와 같은 2인용 완벽한 정보 게임에서는 더욱 그렇습니다. 어느 날 그들은 틱택토 게임을 하고 있었습니다. 친구들이 그녀를 Maxine이라고 부르는 Maxine은 X를 가지고 놀고 있었습니다. 친구들이 그녀를 Minnie라고 부르는 Minnie는 Os를 가지고 있었습니다. 민은 자신의 차례를 방금 진행했고 보드는 다음과 같이 보였습니다.

Max는 보드를 바라보며 자신의 차례가 되자 다음 행동을 고민하고 있었는데, 갑자기 절망에 빠져 두 손에 얼굴을 묻었습니다. 그 모습은 1997년 Deep Blue를 연기한 Garry Kasparov와 매우 흡사했습니다.

예, Min은 맨 윗줄에 Os 3개를 올릴 뻔했지만 Max는 그 계획을 쉽게 중단할 수 있었습니다. 그렇다면 맥스는 왜 그토록 비관적이었을까요?

게임 트리

AI를 활용하여 게임을 해결하기 위해 게임 트리의 개념을 소개하겠습니다. 게임의 다양한 상태는 게임 트리의 노드로 표시되며, 이는 위의 계획 문제와 매우 유사합니다. 생각이 조금 다를 뿐입니다. 게임 트리에서 노드는 게임에서 각 플레이어의 차례에 해당하는 레벨로 배열되어 트리의 "루트" 노드(일반적으로 다이어그램 상단에 표시됨)가 게임의 시작 위치가 됩니다. tic-tac-toe에서는 아직 X나 Os가 재생되지 않은 빈 그리드가 됩니다. 루트 아래의 두 번째 수준에는 첫 번째 플레이어의 움직임으로 인해 발생할 수 있는 X 또는 O의 상태가 있습니다. 우리는 이러한 노드를 루트 노드의 "자식"이라고 부릅니다.

두 번째 수준의 각 노드는 상대 플레이어의 움직임으로 도달할 수 있는 상태를 하위 노드로 갖습니다. 이는 게임이 끝나는 상태에 도달할 때까지 레벨별로 계속됩니다. tic-tac-toe에서는 플레이어 중 한 명이 3라인을 얻어 승리하거나, 보드가 가득 차서 게임이 무승부로 끝나는 것을 의미합니다.

가치의 최소화와 극대화

게임에서 승리를 시도하는 게임 AI를 만들 수 있도록 가능한 각 최종 결과에 수치를 부여합니다. X가 3개의 라인을 가지고 있어 Max가 승리하는 보드 포지션에는 +1 값을 부여하고, 마찬가지로 Min이 연속으로 3개의 Os를 가지고 승리하는 포지션에는 -1 값을 부여합니다. 보드가 가득 차고 두 플레이어 모두 승리하지 못하는 위치의 경우 중립 값 0을 사용합니다(Max는 값을 최대화하려고 시도하고 Min은 값을 최소화하려고 시도하는 순서대로 값이 무엇인지는 중요하지 않습니다).

샘플 게임 트리

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

트리는 Min의 차례가 O를 배치하거나 Max의 차례가 보드의 빈 슬롯에 X를 배치하는 교대 레이어로 구성됩니다. 다음 차례에 플레이할 플레이어가 왼쪽에 표시됩니다.

게임은 루트 노드에 표시된 보드 위치(상단에 (1))에서 계속되며 민은 세 개의 빈 셀 중 하나에 O를 배치합니다. 노드 (2)~(4)는 각각 세 가지 선택으로 인한 보드 위치를 보여줍니다. 다음 단계에서 각 노드에는 Max가 각각 X를 플레이할 수 있는 두 가지 가능한 선택이 있으므로 트리가 다시 분기됩니다.

위의 시작 위치에서 시작할 때 게임은 항상 3개의 행으로 종료됩니다. 노드 (7)과 (9)에서는 X를 사용하는 Max가 승자가 되고, 노드 (11)~(14)에서는 O를 사용하는 Min이 승자가 됩니다.

플레이어의 차례가 번갈아 진행되기 때문에 레벨은 누구의 차례인지 나타내는 최소 레벨과 최대 레벨로 표시될 수 있습니다.

전략적이다

맨 아래에서 두 번째 수준에 있는 노드 (5)–(10)을 고려하십시오. 노드 (7)과 (9)에서는 게임이 종료되고 Max가 연속으로 세 개의 X를 사용하여 승리합니다. 이 위치의 값은 +1입니다. 나머지 노드 (5), (6), (8), (10)에서도 민은 남은 셀에 O만 배치하면 이기므로 게임이 실질적으로 종료됩니다. 즉, 우리는 맨 아래에서 두 번째 수준의 각 노드에서 게임이 어떻게 끝날지 알 수 있습니다. 따라서 노드 (5), (6), (8) 및 (10)의 값도 -1이라고 결정할 수 있습니다.

여기에 흥미로운 부분이 있습니다. 루트 쪽으로 한 단계 높은 노드(노드 (2)~(4))의 값을 고려해 보겠습니다. (2)의 하위 노드, 즉 노드 (5)와 (6)이 모두 Min의 승리로 이어지는 것을 관찰했으므로 주저 없이 노드 (2)에도 -1 값을 붙일 수 있습니다. 그러나 노드(3)의 경우 왼쪽 하위(7)는 Max의 승리(+1)로 이어지며 오른쪽 하위(8)는 Min의 승리(-1)로 이어집니다. 노드 (3)의 값은 무엇입니까? 노드 (3)에서 누가 선택하는지 염두에 두고 이에 대해 잠시 생각해 보십시오.

Max가 플레이할 차례이므로 당연히 왼쪽 자식 노드(7)를 선택합니다. 따라서 노드 (3)의 보드 위치에 도달할 때마다 Max는 승리를 보장할 수 있으며 노드 (3)에 +1 값을 추가할 수 있습니다.

노드 (4)에도 동일하게 적용됩니다. Max는 X를 어디에 놓을지 선택할 수 있으므로 항상 승리를 보장할 수 있으며 노드 (4)에 +1 값을 추가합니다.

누가 승리할지 결정

이 섹션에서 가장 중요한 교훈은 위의 추론을 반복적으로 적용하여 어떤 보드 위치에서든 게임의 결과를 미리 결정하는 것입니다.

지금까지 우리는 노드 (2)의 값이 –1이라고 결정했습니다. 이는 우리가 그러한 보드 위치에 있게 되면 Min이 승리를 보장할 수 있다는 것을 의미하고 노드 (3)과 (4)의 경우 그 반대가 성립한다는 것을 의미합니다. 해당 값은 +1입니다. 이는 Max가 자신의 턴을 현명하게 플레이하면 확실히 승리할 수 있음을 의미합니다.

마지막으로 Min은 경험이 풍부한 플레이어이기 때문에 동일한 결론에 도달할 수 있으며 따라서 그녀에게 가능한 유일한 옵션은 보드 중앙에 O를 플레이하는 것입니다.

아래 다이어그램에는 각 노드의 값과 Min의 차례부터 시작하는 최적의 게임 플레이를 루트 노드에 포함시켰습니다.

루트 노드의 값 = 누가 승리하는지

게임의 가치라고 불리는 루트 노드의 값은 누가 이겼는지(그리고 결과가 단순히 승패가 아닌 경우에는 얼마나 되는지) 알려줍니다. 게임의 가치가 +1이면 Max가 승리하고, 값이 -1이면 Min, 값이 0이면 게임은 무승부로 종료됩니다. 다른 게임에서는 값이 다른 값을 가질 수도 있습니다(예: 포커에서 앞에 있는 칩의 금전적 가치 등).

이 모든 것은 두 플레이어가 자신에게 가장 좋은 것을 선택하고, 한 사람에게 가장 좋은 것이 다른 사람에게는 가장 나쁘다는 가정(소위 "제로섬 게임")에 기초합니다.

미니맥스 알고리즘

위의 게임 가치 개념을 활용하여 Minimax 알고리즘이라는 알고리즘을 얻을 수 있습니다. 이론적으로 말하면 모든 결정론적 2인 완전 정보 ​​제로섬 게임에서 최적의 게임 플레이를 보장합니다. 게임의 상태가 주어지면 알고리즘은 단순히 주어진 상태의 하위 항목의 값을 계산하고 Max의 차례인 경우 최대값을 갖는 것을 선택하고 Min의 차례인 경우 최소값을 갖는 것을 선택합니다.

알고리즘은 몇 줄의 코드를 사용하여 구현할 수 있습니다. 그러나 우리는 주요 아이디어를 파악한 것으로 만족할 것입니다. 실제 알고리즘을 살펴보는 데 관심이 있다면(경고: 프로그래밍 필요) Wikipedia: Minimax 등을 자유롭게 확인해 보세요.

좋아요, 이제 집에 가도 될까요?

위에서 언급한 바와 같이 Minimax 알고리즘은 모든 결정론적, 2인 플레이, 완벽한 정보 제로섬 게임에서 최적의 게임 플레이를 구현하는 데 사용될 수 있습니다. 이러한 게임에는 tic-tac-toe, connect 4, 체스, 바둑 등이 포함됩니다. 가위바위보는 다른 플레이어에게 숨겨진 정보를 포함하므로 이 유형의 게임에 속하지 않습니다. 결정론적이지 않은 독점이나 주사위 놀이도 마찬가지입니다. 그럼 이 주제에 관해서는 여러분, 이제 집에 가도 될까요? 대답은 이론적으로는 그렇습니다. 그러나 실제로는 그렇지 않습니다.

추가 트릭: 대규모 게임 트리 관리

대규모 게임 트리를 관리하려면 몇 가지 트릭이 더 필요합니다. 이들 중 다수는 1997년 체스 세계 챔피언 가리 카스파로프(Garry Kasparov)를 물리친 IBM의 Deep Blue 컴퓨터에서 중요한 요소였습니다.

게임 트리의 작은 부분만 탐색할 여유가 있다면 최종 노드, 즉 게임이 끝나고 승자가 알려진 노드에 도달하기 전에 Minimax 알고리즘을 중지할 수 있는 방법이 필요합니다. 이는 다음 플레이어의 차례에 대한 정보를 포함하여 보드 위치를 입력으로 취하고 주어진 보드 위치에서 계속되는 게임의 예상 결과에 대한 추정치인 점수를 반환하는 소위 휴리스틱 평가 기능을 사용하여 달성됩니다.

위에 제시된 미니맥스 알고리즘은 주어진 깊이 제한의 모든 노드에서 휴리스틱이 반환되는 깊이 제한 버전을 얻기 위해 최소한의 변경이 필요합니다. 깊이는 단순히 휴리스틱 평가 함수를 적용하기 전에 게임 트리가 확장되는 단계 수를 나타냅니다.

연습문제

연습 7: 왜 그렇게 비관적인가요, Max?

이 섹션의 시작 부분에서 설명한 틱택토 게임으로 돌아가 보겠습니다. 고려해야 할 가능한 최종 게임의 공간을 좁히기 위해 Max는 임박한 패배를 피하기 위해 맨 윗줄에 X를 분명히 표시해야 한다는 것을 알 수 있습니다.

이제 민이 O를 플레이할 차례입니다. Minimax 알고리즘을 사용하여 게임의 이 상태와 위 위치가 루트인 게임 트리의 다른 상태의 값을 평가합니다.

학습 과제:
보드 아래 위치부터 게임 트리를 살펴보세요. 연필과 종이를 사용하여 게임이 끝나는 최하위 노드의 값을 채워주세요. 이번에는 일부 게임이 무승부로 끝나는데, 이는 노드의 값이 (-1이나 1이 아닌) 0이라는 것을 의미합니다.

다음으로 다음 레벨의 노드 값을 계속해서 채웁니다. 해당 수준에서는 분기가 없으므로 두 번째로 낮은 수준의 값은 최하위 수준의 값과 동일합니다.

두 번째로 높은 수준에서 각 노드에 대해 하위 노드 값의 최대값을 선택하여 값을 입력합니다. 보시다시피 이는 MAX 수준입니다. 마지막으로 루트 노드의 하위 노드 값 중 최소값을 선택하여 루트 노드의 값을 채웁니다. 이것이 게임의 가치입니다.

답변으로 게임의 가치를 입력하세요.

01가장 적절한 답을 선택하세요.

1-10

답안 확인하기