Tic-Tac-Toe 게임은 3*3 게임판에 두 명의 플레이어가
X와 O를 번갈아 두면서 3개의 동일한 무늬의 직선을 만들게 되는 쪽이
승자가 되는 게임이다.
이제 이 Tic-Tac-Toe 게임을 MinMax 알고리즘을 통해
구현하는 방법을 알아보도록 하자.
1. MinMax 알고리즘
MinMax 알고리즘이란 최대 최소 전략을 사용하여 틱택토,오목,체스,바둑 등과 같은
턴제 게임과 같은 프로그램에서 최선의 의사결정을 하는데 사용되는 알고리즘이다.
상대방과 차례를 주고받는 게임에서는 우리는 상대방의 수를 예측하고
그 수를 기반으로 다음 수를 생각하는 것이 승리할 수 있는 가장 좋은
방법일 것이다.
MinMax 알고리즘의 핵심이 바로 이것이다.
이런 턴제 게임에서 상대방이 최선의 수를 택한다는 가정하에 다음 수를
예측하는 것이다.
상대방의 최선의 수(상대방에게 유리해지는 수)는 나의 입장에서는 최악의
수이기 때문에
'상대방의 최선의 수를 두더라도 이에 대응하여 최소한의 손실을 보는 것'
이것이 MinMax 알고리즘의 궁극적인 목표라 할 수 있다.
그렇다면 MinMax 알고리즘은 어떤 방식으로 구현이 될까?
게임트리는 가능한 선택지들을 트리의 노드로 만들고 각각의 노드들로부터
또 가능한 자식 노드들이 이어지는 트리이다.
다음 그림과 같이 루트로부터 가능한 경우의 수들이 노드로 생성되고
거기서 또 파생되어서 트리가 만들어진다.
나의 차례에서는 가장 좋은 수(max)를 선택하고 상대방의 차례에서는
나에게 최악의 수(min,즉 상대방에게 최선의 수)를 선택하게 된다.
2. Tic-Tac-Toe 구현
Tic-Tac-Toe 게임의 규칙은 다음과 같다.
-
A와 B가 차례대로 번갈아가면서 수를 둔다.
-
Max가 선공을 가져간다. (선공은 항상 X로 시작한다.)
-
같은 무늬의 직선( 수직선 , 수평선 , 대각선 )을 먼저 완성하는 쪽이 승리.
-
제로썸 게임이다. (승자와 패자가 나뉜다.)
MinMax 알고리즘을 사용하기에 플레이어들은 최선의 수를 선택한다는 가정하에
게임을 진행한다.
Max가 항상 X로 시작하며 후공인 Min은 O이다.
그림과 같이 가능한 모든 경우의 수들을 그려보며
가장 아래 노드까지 탐색하며 모든 수들을 평가한다.
모든 경우의 수들을 평가하며 측정값을 계산한다.
Max가 이기는 경우 측정값은 +1 이다.
Min이 이기는 경우 측정값은 -1 이다.
비기는 경우는 0이 된다.
Max는 항상 큰 값을 택하고 Min은 작은 값을 택한다.
Min은 3과 5를 비교하여 3을 택하고 2와 9를 비교하여 2를 택한다.
Max는 3과 2를 비교하여 3을 택한다.
이런 식으로 모든 수들을 비교하여 항상 최선의 수를 두도록 한다.
3. Tic-Tac-Toe 구현 코드
Tic-Tac-Toe는 제로섬 게임이기때문에 비겼을 경우에는
선공을 하는 X가 이기는 것으로 구현하였다.
개발환경은 vsCode를 사용하였고 언어는 파이썬으로 구현했다.
참고
미니맥스 알고리즘 소개
https://aboutnlp.tistory.com/18
휴리스틱 알고리즘
https://going-to-end.tistory.com/entry/Minimax-algorithm-%EB%AF%B8%EB%8B%88%EB%A7%A5%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://lordofkangs.tistory.com/204
https://ssollacc.tistory.com/43
