더 지니어스에서 나오는 십이장기를 AI와 두는 프로그램
[더 지니어스 프로그램에서 십이장기를 두고 있는 영상]
-
십이장기는 가로 4칸, 세로 3칸 총 12칸으로 이루어진 게임 판에서 진행되며 플레이어들의 바로 앞쪽 3칸이 각자의 진영이 된다.
-
결승 진출자 2명에게는 4가지 종류의 말이 1개씩 주어지며 각 말은 지정된 위치에 놓인 상태로 게임을 시작한다.
-
각 말들은 말에 표시된 방향으로만 이동할 수 있으며 각각의 역할은 다음과 같다.
-
장(將). 자신의 진영 오른쪽에 놓이는 말로 앞, 뒤와 좌, 우로 이동이 가능하다.
-
상(相). 자신의 진영 왼쪽에 놓이며 대각선 4방향으로 이동할 수 있다.
-
왕(王). 자신의 진영 중앙에 위치하며 앞, 뒤, 좌, 우, 대각선 방향까지 모든 방향으로 이동이 가능하다.
-
자(子). 왕의 앞에 놓이며 오로지 앞으로만 이동할 수 있다.
-
하지만, 자(子)는 상대 진영에 들어가면 뒤집어서 후(侯)로 사용된다.
-
후(侯)는 대각선 뒤쪽 방향을 제외한 전 방향으로 이동할 수 있다.
-
-
게임이 시작되면 선 플레이어부터 말 1개를 1칸 이동시킬 수 있다. 말을 이동시켜 상대방의 말을 잡은 경우, 해당 말을 포로로 잡게 되며 포로로 잡은 말은 다음 턴부터 자신의 말로 사용할 수 있다.
-
게임 판에 포로로 잡은 말을 내려놓는 행동도 턴을 소모하는 것이며 이미 말이 놓여진 곳이나 상대의 진영에는 말을 내려놓을 수 없다.
-
상대방의 후(侯)를 잡아 자신의 말로 사용할 경우에는 자(子)로 뒤집어서 사용해야 한다.
-
게임은 한 플레이어가 상대방의 왕(王)을 잡으면 해당 플레이어의 승리로 종료된다.
-
만약 자신의 왕(王)이 상대방의 진영에 들어가 자신의 턴이 다시 돌아올 때까지 한 턴을 버틸 경우 해당 플레이어의 승리로 게임이 종료된다.
-
잡은 말을 사용할 땐 자신이 원하는 턴에 자유롭게 사용가능 하며 원하지 않으면 사용하지 않아도 무관하다.
출처 : https://namu.wiki/w%EC%8B%AD%EC%9D%B4%EC%9E%A5%EA%B8%B0
-
파일들을 다운 받은 뒤, 십이장기.py를 실행한다.
-
난이도를 조정한다.
| 난이도 | 상 | 중 | 하 |
|---|---|---|---|
| 수 깊이 | 7 | 5 | 3 |
- 움직일 말의 영문과 함께 y좌표, x좌표 순서대로 입력한다.
(예: 王을 B2로 움직인다 했을때 -> Kb2 )
(예: 잡은 자를 B2에 놓는다 했을 때 -> Zb2!)
| 말 | 왕 | 상 | 장 | 자 | 후 |
|---|---|---|---|---|---|
| 영문 | K | S | J | Z | H |
| 번호 | 0 | 1 | 2 | 3 | 4 |
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | a1 | a2 | a3 | a4 |
| b | b1 | b2 | b3 | b4 |
| c | c1 | c2 | c3 | c4 |
십이장기를 구현하는 Board 모듈과 Board와 호환되어 Ai를 구현하는 Ai 모듈이 존재한다.
그 외에도 점수, 좌표등을 기록하거나 파일을 읽어 사용하는 모듈인 dicBoard가 있으며,
파일로는 긴 배열들을 파일로 정리했는데, 각각의 말들이 움직일 수 있는 범위를 알려주는 piece_go, 각각의 말들이 좌표당 가지는 가중치 score csv파일이 있다.
Board 속 함수의 설명은 다음과 같다.
-
print_(board, catch) : 3x4 판 board와 각각 잡은 말 목록
catch를 인수로 받아 터미널에 출력한다. -
getlocalxy(x, y) : 상대적 x, y 좌표를 받으면 밑의 표에 따라 적합한 정수를 반환한다.
| Y\X | 1 | 0 | -1 |
|---|---|---|---|
| 1 | 1 | 2 | 3 |
| 0 | 4 | 5 | 6 |
| -1 | 7 | 8 | 9 |
-
getBoardNow(board, new_xy) : 인수로 받은 board의 xy = (x, y)좌표 속 정보를 반환한다.
-
isIn(x, y) 인수로 받은 x, y좌표가 3x4배열 인덱스를 넘어가면 거짓, 아닐시 참을 반환한다.
-
isEmpty(board, xy) : 인수로 받은 board의 xy = (x, y)가 비어있으면 참, 아닐시 거짓을 반환한다.
-
isCatch(catch, type_, turn) : 해당 타입의 말을 해당 turn(0 = player, 1 = ai)의 플레이어가 포로로 가지고 있으면 참, 아닐시 거짓을 반환한다.
-
isCanGo(board, new_xy, old_xy, type_, turn) : board에서 old_xy에 있는 말이 new_xy로 이동할 수 있다면 참, 아닐시 거짓을 반환한다.
-
findXY(board, new_xy, type_, turn) : board에서 new_xy 주변에 type_과 turn이 같은 말의 좌표를 반환한다.
-
setPiece(board, new_xy, type_, turn) : board의 new_xy에 type_ + turn 를 저장한다.
-
isWin(board, catch, turn) : board, catch를 통해 턴마다 승리조건을 확인하고 승리시 참을 반환한다.
-
move(board, catch, new_xy, type_, turn) : type_, turn인 말을 new_xy로 움직인 후 그 때의 board, catch를 반환한다.
-
place(board, catch, new_xy, type_, turn) : board의 new_xy 위치에 type_, turn 속성을 가진 말을 두고, 해당 turn의 catch에서 type_을 하나 뺀다. board, catch를 반환한다.
-
Player(board, catch, old_xy, com_xy, type_, isMove) : 받은 명령을 바탕으로 player의 턴을 진행한다. isMove가 참일 경우, move 함수를, 거짓일 경우 place 함수를 실행한다.
-
Ai_(board, catch): Ai의 턴을 실행한다.
-
input_command(board, catch) : 올바른 입력이면 입력을 바탕으로 old_xy, com_xy, type_, isMove를 반환한다. 입력이 잘못될 경우, 올바른 입력이 나올 때까지 반복한다.
Ai 속 함수의 설명은 다음과 같다.
-
calc_expt(board, catch) : board, catch를 설정한 가중치로 계산하여 상황 점수를 반환한다.
-
Aing(board, catch, depth) : board, catch에서 depth만큼 수를 탐색하고, 가장 최선의 수를 board, catch로 반환한다.
-
minimax(node, depth, alp, bet, maximizingPlayer) : minimax 알고리즘으로 수를 탐색하고 가장 최선의 수를 반환한다.
-
minimax_value(node, depth, maximaizingPlayer) : minimax 알고리즘 속 경우의 수 탐색 함수, node의 자식 노드로 경우의 수를 받는다.
AI 알고리즘은 많이 알려진 체스 AI에서 사용되는 minimax 알고리즘을 채용하였다.
체스나 바둑과 같이 1대1 턴제 보드게임의 경우, 상대방의 수를 파악하고 대응하는 것이 승리로 이끈다. 상대방의 수를 대응한다는 뜻은, 상대방의 최선의 수가 최소의 영향을 미치는 수를 찾는 다는 뜻이고, 이를 알고리즘으로 만든게 minimax 알고리즘이다.
다음과 같이 4번째 수 까지 모든 경우의 수가 존재한다 한다면, 3번째 수를 두는 상대방은 나에게 가장 불리한 경우를 선택한다.(숫자가 클수록 유리하고, 숫자가 작을수록 불리하다)
10과 무한대 중에서는 10을, 7과 5중에서는 5를, -7과 -5중에서는 -7을 선택한다.
나는 나에게 가장 유리한 경우를 선택하니, 10과 5중에서 10을, 5와 -무한대 중에서는 -5를 고른다.
또 다시 상대방은 10과 -10중에서 -10을, 5와 -7에서 -7을 선택한다.
따라서 -7과 -10중 가장 최선의 결과는 -7이므로 -7을 선택한다.
minimax 알고리즘을 보다 효율적으로 활용하기 위해서 알파베타 가지치기를 사용하였다.
알파베타 가지치기란 일어날 가능성이 없는 경우의 수를 미리 제거하는 알고리즘이다.
minimax 알고리즘 중 한 노드에서 자식 노드를 탐색할 때, 이전에 평가한 수보다 현재 평가한 수가 더 좋지 않으면 그 노드의 남은 형제 노드와 후손 노드를 가지치기한다.
Alpha는 최대한 유리한 정도, Beta는 최소로 불리한 정도라고 하면,
Max 에서는 값이 Beta보다 크면 가지치기하고, Min 에서는 값이 Alpha보다 작으면 가지치기한다.
위 사진을 보면 1단계에서 alpha가 3, 2단계에서 각각 Beta가 3, 0, 2가 되었다.
3단계에서는 각각 베타보다 작은 값들이 가지치기 되어 (3, A), 0, 2 로 가지치기 되었다.
4단계에서도 가지치기가 진행되어 alpha보다 작은 값이 가지치기 된 것을 볼 수 있다.
이 알고리즘들을 십이장기에 적용하였다.
먼저 각각의 말마다, 위치별 점수를 부여하였다.
플레이어 기준 ( x == 1 이 자신의 진영인 경우)으로 말 점수는 다음과 같다.
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | 0 | 0 | 0 | 100 |
| b | 0 | 0 | 0 | 100 |
| c | 0 | 0 | 0 | 100 |
왕의 경우는 상대 진영에 두턴 이상 있을 경우 승리하기 때문에, 매우 큰 가중치인 100을 줘 Ai가 최대한 상대 진영에 유지하도록 하였다. 다른 경우 왕은 위치에 상관없이 살아있는게 중요하기 때문에 0점을 주었다.
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | 3 | 4 | 4 | 3 |
| b | 4 | 5 | 5 | 4 |
| c | 3 | 4 | 4 | 3 |
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | 3 | 4 | 4 | 3 |
| b | 4 | 5 | 5 | 4 |
| c | 3 | 4 | 4 | 3 |
상과 장은 같은 점수를 가진다. 공식은 (갈 수 있는 칸의 갯수) + 1 이다. 1을 더한 이유는 최소값이 3이되어 잡은 말을 위치에 두는게 이득이 되도록 도출되게 하기 때문이다.
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | 1 | 1 | 2 | 3 |
| b | 1 | 1 | 2 | 3 |
| c | 1 | 1 | 2 | 3 |
자의 경우 후가 되는게 이득이므로, 앞으로 갈 수록 좋은 점수를 가지도록 하였다. 상대진영에서 가중치가 3인이유는 뒤에 나오는 후가 상대진영에서 3을 가지기 때문이다. 3보다 작을 경우, AI가 후가 되는 것을 선택하지 않는다.
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | 2 | 2 | 3 | 3 |
| b | 2 | 2 | 4 | 3 |
| c | 2 | 2 | 3 | 3 |
후의 경우, 상대 진영에서는 y좌표를 선택할 수 없지만, x=3 부터 y좌표를 선택할 수 있어 y = b일때 가장 큰 4가 되도록 하고, 뒤로 갈 수록 용도가 없어지니 가중치가 떨어지도록 설정하였다.
잡은 말에도 각각의 점수를 부여 하였다.
| 말 | 왕 | 상 | 장 | 자 | 후 |
|---|---|---|---|---|---|
| 점수 | inf | 3 | 3 | 1 | 2 |
| Y\X | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a | S0 | -- | -- | J1 |
| b | K0 | J0 | K1 | -- |
| c | -- | Z0 | -- | S1 |
| Player | Ai |
|---|---|
| Z | -- |
Ai 기준(1) 위치별 점수 : (0 + 3 + 3) - (0 + 3 + 2 + 4) = -3
Ai 기준(1) 잡은 말 점수 : -1
현재 유리한 정도 : -4
참고자료: