C++ - 이길수 없는 틱택토 인공지능 만들기

1.서론

틱택토란?

판 크기는 3×3의 정사각형인 2인 전용 게임이다. 가로 세로 대각선으로 3개가 이어지면 이긴다.

즉 3 x 3 보드판에서 삼목을 만들면 이기는 아주 간단한 보드게임입니다.

 

이 보드게임은 선수, 후수 상관없이 무조건 비기는 방법이 존재합니다.

 

규칙이 아주 단순하여 가장 기초적인 게임 인공지능을 만들고자 할 때 예제로 활용된다고 합니다.

 

그럼 절대 이길 수 없는 틱택토 인공지능의 조건을 알아보자.

 

 

2.우선순위

1. 우선 컴퓨터의 차례일 때 가장 먼저 고려해야할 수는 두었을때 삼목이 완성되는 자리 입니다.

두는 순간 컴퓨터가 승리할 수 있기 때문에 이보다 우선적으로 두어야 하는 자리는 없습니다.

 

2. 그 다음은 플레이어가 두었을 때 삼목이 되는 자리입니다. 이번 컴퓨터의 차례에서 플레이어의 삼목을

막지 않으면 컴퓨터가 패배하기 때문에 지금 바로 승리할 수 있는 자리가 없다면 플레이어의 삼목을 막는

자리를 둬야합니다.

 

3. 컴퓨터 차례일 때 2목을 2개 만들 수 있는 자리. 2목을 2개 만들면 삼목을 만들 수 있는 자리가 2개 존재하기 때문에다음턴 플레이어가 한쪽을 막는다고 해도 다음 컴퓨터 차례 때 우선순위 1번에 의해 나머지 한 곳에 수를 두면 승리할 수 있습니다.

 

4.플레이어의 2목 2개를 막을 수 있는 자리. 3번 우선순위와 마찬가지로 컴퓨터 입장에서 플레이어가 2목을 2개 만들도록 방치하면 다음 컴퓨터의 차례는 올 수 없습니다. 

 

5. 4번 우선순위 까지는 직관적으로 생각해낼 수 있지만 이제부터 디테일한 인공지능이 필요합니다. 이를 위해선 틱택토의 룰을 세밀하게 이해할 필요가 있습니다. 먼저 플레이어가 선수라고 했을 때 가장 좋은 자리는 어디인지 생각해봅시다.

얼핏보면 모든 줄에 한개의 자리를 차지 할 수 있으니 정 가운데가 좋아보이지만 틱택토에서 가장 높은 승률을 가져갈 수 있는 첫 수는 구석에 두는것입니다.

첫 수를 구석에 둘 경우 상대방이 그 다음에 반대편 구석에 두지 않는다면 이길 확률이 급격하게 증가합니다.

예들 들어 상대방이 두는 자리와 상관없이 그 다음 수에 반대편 구석에 둡니다.

ex)

X : 선 플레이어 O : 후 플레이어

X - -

- O -

- - X

이렇게 되면 그 다음에 상대가 변에 두어 자신의 2목을 완성과 동시에 한곳을 막지 않으면 패배하게 됩니다.

하지만 이런 수를 인공지능에게 적용시키기 위해선 위에서 언급했던 4개의 우선순위로 해결할 수 없으므로

일반화 시키기 위해 첫수를 구석에 두었을 때 반대편 구석에 두도록 하면 선 플레이어의 승리를 막을 수 있습니다.

 

6. 그냥 가운데에 놓는 수. 위의 모든 우선순위에 해당하지 않는다면 가운데에 놓는것이 좋습니다. 첫 수는 구석에 놓는것이 좋다고 했지만 일반적으로 최소 무승부만 내기위한 인공지능을 목적으로 하고 있기 때문에 가운데에 두는것으로 하는것이 좋습니다.

 

7.구석에 놓기. 가운데에 이미 돌이 있다면 구석에 둡니다.

 

8. 둘곳이 없다면 변에 있는 자리중 아무곳에 둡니다.

 

3.상세 설계

1. 해당 자리가 삼목을 완성시키는 자리인지 확인하기 위해 해당 자리를 교차점으로 각 가로, 세로, 대각선 줄에 컴퓨터의 돌이 2개인지 확인합니다. 만약 2개인 자리가 한줄이라도 있다면 해당 자리는 삼목을 완성할 수 있는 자리입니다.

 

2.1번의 과정을 컴퓨터의 돌이 아니라 플레이어의 돌로 놓고 검사하여 상대방이 두었을때 삼목이 완성되는 자리인지 판별할 수 있습니다.

 

3. 해당 자리가 2목을 2줄 만들 수 있는 자리인지 확인 하기 위해서는 1, 2번 우선순위 조건을 만족시키기 위해 적용시켰던 로직에서 돌이2개인지가 아닌 1개인지로 바꿔줍니다. 그리고 해당되는 줄이 1개이상이 아닌 2개이상으로 하면 2목을 2줄 완성 시킬 수 있는 자리인지 아닌지 판별할 수 있습니다. 단, 주의할 점으로 돌이 1개가 있지만 다른 칸에 플레이어의 돌이 있는지 없는지 검사하는 것 또한 포함해야 합니다. 상대방의 하나라도 껴있다면 그 줄은 2목을 완성시킨 줄이 아닙니다.

 

4.3번의 로직을 돌만 바꿔서 적용합니다.

 

5. 5번 우선순위가 적용되는 자리는 전제조건이 구석자리인 경우입니다. 구석자리가 아니라면 5번 우선순위를 적용할 필요없이 넘어갑니다. 그렇다면 구석자리인지 판단하기 위해 좌표를 일반화 해보겠습니다.

구석자리는 각 0,0 0,2 2,0 2,2에 해당됩니다.

여기서 보드판의 크기인 2(인덱스가 0부터 시작하기 때문)에 각 좌표의 수직좌표, 수평좌표를 빼보면 그 어떤 경우라도 그 결과 값은 0 또는 2가 나온다는걸 알 수 있습니다. 위에서 언급한 4개 좌표에 적용시켜봅시다.

0,0 -> (2-0),(2-0) = 2,2

0,2 -> (2-0),(2-2) = 2,0

2,0 -> (2-2),(2-0) = 0,2

2,2 -> (2-2),(2-2) = 0,0

 

구석 좌표가 아닌 좌표에 해당 로직을 적용해보면 결과값이 0 또는 2가 아닌 값이 최소 한개이상 존재 한다는걸 알 수 있습니다. 이 로직을 통해 보드판에서 특정 좌표가 구석에 있는 좌표인지 아닌지 알 수 있습니다.

 

그래서 구석 좌표일 경우, 반대편 구석 좌표에 플레이어의 수가 놓여있으면 해당 자리는 5번 우선순위에 해당하는 자리로 정할 수 있습니다.

반대 구석 좌표를 구하는 방법으로는 삼항연산자를 사용하였습니다.

oppositeVer = ver==2 ? 0 : 2

oppositeHor = hor==2 ? 0 : 2

 

6.보드판의 가운데에 있는 자리인지는 수직좌표와 수평좌표가 모두 1인경우인지를 검사합니다.

 

7.보드판의 구석에 있는 자리인지는 5번 우선순위에서 적용시켰던 구석자리를 판별하는 방법을 적용합니다.

 

8. 위 우선순위에서 모두 해당되지 않는 경우를 변에 두는 경우로 생각합니다.

 

이제 각 9개의 좌표에 몇번 우선순위에 해당되는지를 검사하고 가중치를 부여합니다. 그 다음 컴퓨터는 가장 가중치가 높은 자리에 돌을 두면 가장 우선순위가 높은 자리에 돌을 두게 됩니다.

 

4.마무리

위 8가지 우선순위를 고려하여 수를 두면 사람이 어느곳을 두어도 절대 이길 수 없는 틱택토 인공지능이 완성됩니다.

보드판 구현은 각 자리에 숫자를 부여하고 플레이어는 턴마다 보드판의 숫자를 입력하여 돌을 둘 수 있도록 하였습니다.소스코드는 첨부파일에 첨부합니다. 참고해주시고 오류나 로직상의 문제가 있다면 지적해주시면 감사드리겠습니다.

main.cpp

0.01MB

도움이 됐다면 좋아요 눌러 주시면 감사드리겠습니다.