인공지능 - mixMax 알고리즘을 이용한 Tic Tac Toe 구현

reference > 게임트리를 사용한 제로섬 게임의 인공지능 
위 내용을 바탕으로 minMax 알고리즘을 이용한 TicTacToe 게임을 구현해보았다.
레퍼런스에서의 소스코드에 있는 평가함수와는 다른 방식으로 해결해 보았다. 

 Tic Tac toe

   게임 방식

      • 게임에 참여하는 플레이어는 2명이다.

      • 양 플레이어는 서로 번갈아가면서 가로 * 세로 3칸씩으로 구성된 표에 서로 자리를 점한다.

      • 자리가 빈 곳에만 점할 수 있다.

   승리 조건

      • 플레이어가 점한 3자리가 1자로 되었을 경우 그 플레이어가 승리한다.

      • 테이블이 꽉 찰 때까지 결판이 나지 않으면 경기는 무승부로 한다.
 

 문제 풀이

   초기상태 및 목표상태, 연산자 정의

      • 초기상태 : 9칸의 빈 테이블

      • 목표상태 : 승리상태를 얻어낼 수 있는 테이블

      • 연산자

         - 플레이어가 자리를 정할 수 있는 setMark(position, p)를 정의한다. 
            테이블의 position에 p를 입력함으로서 자리를 정한다.

         - 테이블변수를 t, 플레이어를 p라 하고 스키마 win(t, p)를 정의한다.

           win(t, p)는 테이블을 평가하여 플레이어 p가 승리하였는지 판단한다.

         - 플레이어의 차례를 정하는 sequence(t) 스키마를 설정한다.

            sequence(t)는 현재 플레이어의 판단한다.

         - 테이블에서의 게임이 진행 중인지를 판단하는 finish(t) 스키마를 정의한다.
 

 구 현

구현은 Java를 기반으로 구현하였다. 게임트리를 구현하기위해 결정트리 자료구조를 만든다. 이 자료형은 기존의 트리와 흡사하지만 각 노드마다 노드의 성분을 평가한 평가값이 들어있다. 결정하기 위한 알고리즘으로 알파베타 가지치기를 이용하였다. 알파베타 가지치기는 minMax 알고리즘의 일종으로, minMax알고리즘보다 더욱 더 경제적으로 설계되어있다.
 • Table 클래스 : 3목게임을 관리하고 여러 가지 기능을 가진 클래스이다. 플레이어

가 가장 최근에 둔 자리를 저장해 놓는다거나, 기본적으로 진행되는 게임의 룰을

구현해놓았다.

public class Table{

private int [] t;

 

// 플레이어에 대한 값을 상수로서 정의한다.

public static final int player1 = 1;

public static final int player2 = -1;

 

// 최근에 놓은 값

private int latestPosition;

 

// 차례를 알 수 있는 논리값.

private boolean sequence;

 

// 생성자

public Table(){

t = new int[9];

latestPosition = -1;

sequence = true;

}

public Table(Table t){

this.t = t.t.clone();

latestPosition = t.getLatestPosition();

sequence = t.getSequence();

}

 

// 최근에 둔 수의 좌표를 가져온다

public int getLatestPosition() {

return latestPosition;

}

 

// 자리를 마크하는 setMark() 메소드

public Table setMark(int x, int y){

int coord = x + (3 * y);

if(x < 3 && y < 3)

if(t[coord] == 0){

latestPosition = coord;

t[coord] = sequence?player1:player2;

// 시퀀스값에 XOR 연산을 하여 수를 둘때마다 값이 변할수 있게 하였다.

sequence ^= true;

}

// 자리를 점한 테이블을 리턴한다.

return this;

}

// 오버로딩하여 2차원을 1차원으로 컨버팅 할 필요없게하였다.

public Table setMark(int coord){

if(coord < 9 && t[coord] == 0){

latestPosition = coord;

t[coord] = t[coord] = sequence?player1:player2;

sequence ^= true;

}

return this;

}

// 각종 멤버변수 접근 메소드, 테이블 상태를 확인하는 메소드

public boolean getSequence(){

return sequence;

}

 

public int whoseTurn(){

return sequence?player1:player2;

}

 

public boolean isFull(){

for(int i : t) if(i == 0) return false; return true;

}

 

// 승자를 확인하는 메소드

public boolean isWinner(int player){

if(t[0] == player && t[1] == player && t[2] == player ||

t[3] == player && t[4] == player && t[5] == player ||

t[6] == player && t[7] == player && t[8] == player ||

t[0] == player && t[3] == player && t[6] == player ||

t[1] == player && t[4] == player && t[7] == player ||

t[2] == player && t[5] == player && t[8] == player ||

t[0] == player && t[4] == player && t[8] == player ||

t[2] == player && t[4] == player && t[6] == player)

return true;

else

return false;

}

 

public int getTableCount(){

int counter = 0;

for(int i=0; i<9; i++)

if(t[i] != 0)

counter++;

return counter;

}

 

public boolean isFinished(){

return (isFull() || isWinner(player1) || isWinner(player2));

}

 

public int [] getTableArray(){

return t;

}

 

// 모니터링을 편리하게 하기 위해 toString()을 오버로딩하였다.

public String toString(){

String temp = super.toString();

temp += "[tableCount=" + getTableCount() + "]";

temp += "[sequence=" + (sequence?"O":"X") +"]";

temp += "[isFull=" + isFull() +"]";

temp += "[isFinished=" + isFinished() +"]";

 

for(int i = 0; i < 9; i++){

if(i%3 == 0)

temp += "\n";

temp += ((t[i]==player1)?"O":(t[i]==player2)?"X":"-") + " ";

}

return temp;

} 
}

 • TableState 클래스 : State를 상속하여 테이블의 상태를 평가하고 평가값을 저장해 놓는다. 이 TableState를 기반으로 인공지능이 다음수를 예상하고 결정할 수 있게 구현된다.

※ 테이블의 상태 평가 함수의 구현

테이블의 각 말들이 가진 위치와 잠재적인 다음 수에 대한 이득을 카운트하여

양 플레이어가 가진 가중치의 비를 만들어 -1 ~ 1 사이의 평가값을 가지게 설정

하였다. 각 평가마다 설정된 가중치는 휴리스틱하게 설정되었다.

수식 > p1 = 플레이어1의 가중치, p2 = 플레이어2의 가중치

eval(t) = (p2 + p1) == 0 ? 1 : ((p1 / p2 + p1) * 2) - 1

위 함수를 보면 분자에 p1만이 올라와있는데 이는 minMax알고리즘을 이용할 때, p1측이 Max값이 되도록 유도를 하기 위함.

 분모가 0인지를 판단하여 0일 경우 무한대가되므로 1로 설정한다.

• 평가 0

자신의 차례일 때 가중치를 주어 서로 똑같은 상황일 때 자신에게 더

이득이 되는 평가값을 갖게 한다.

• 평가 1

테이블에 있는 플레이어의 마크가 속한 줄(가로, 세로, 대각선)에 다른

플레이어가 있는지, 자리가 비어있는지를 판단하여 가중치를 설정한다.

- 테이블에 플레이어가 속한 줄들에 다른 플레이어와 같이 있는 경우

가중치를 주지 않는다.

• 평가 2

테이블에 플레이어가 속한 줄에 자신만이 속해있고 자리가 2개 이상이면서,

현재 차례가 해당 플레이어일 경우 결정타를 줄 수 있도록 높은 가중치를

설정한다.

• 평가 3

승자는 플레이어에 따라 Max값 또는 min값을 가지게 한다.

• 초기에 가중치는 0으로 설정되어선 안 된다. 초기 가중치를 0으로 설정하게되면,

승리하거나 패배 하였을 때의 평가값이 산출되므로 초기화는 선수를 두는

플레이어는 1로 후수를 두는 플레이어는 2로 설정하도록 하였다.

- 평가에 대한 공정성을 유지하기 위함.

 • 평가함수 구현에 사용된 메소드

// 가중치를 초기화하는 메소드

public void initEval(){

p1Bonus = 1;

p2Bonus = 2;

}

 

public int evaluate(Table t, int player){

// Table클래스로부터 int형의 테이블을 가져온다.

int [] table = t.getTableArray();

// 가중치값

int bonus = 0;

// 같은줄에 같은 마크가 2개 있는지 검사하기위한 카운터

int c;

// 가로 세로줄 대각선에서 자리가 비어있는지를 확인하기 위한 논리값.

boolean b;

// 속한 줄에서의 상대가 방해하고 있는지 확인하기 위한 논리값

boolean interrupt;

// x좌표 루프

for(int x = 0; x < 3; x++)

// y좌표 루프

for(int y = 0; y < 3; y++){

// 2차원배열을 1차원으로 변환하였을때의 좌표

int coord = x + 3 * y;

// 테이블값이 플레이어가 점하고 있을때

if(table[coord] == player){

// 확인하기 위한 변수값들을 초기화한다.

b = true; interrupt = false; c = 0;

// 3목이므로 해당하는 3칸에 대한 루프를 발생시킨다. 가로줄에 속한 값들을 확인하는 루프

for(int i = 0; i < 3; i++){

// 조건값이다. 논리값을 설정할 때 좌표에대한 계산을 최소화하기 위해 변수로 설정.

int cond = table[((x + i) % 3) + 3 * y];

// 방해받고 있는지 확인하는 논리연산이다.

interrupt |= (cond != 0) && (table[coord] != cond);

// 같은줄에서의 자리에 대한 가중치를 설정하기 위한 논리연산이다.

b &= (player == cond) || (cond == 0);

// 같은줄에 자신과 똑같은 마크가 있을 때 카운터를 1 증가시킨다.

c += table[coord] == cond ? 1 : 0;

}

// 만약 같은줄에대해 빈자리만이 있을 때 가중치를 1 증가시킨다.

if(b) bonus += 1;

// 방해받고있지 않고 카운터가 2 이상이며 자신의 차례일 때, 결정타를 주기위한 가중치를

// 4 증가시킨다.

if(!interrupt && c == 2 && t.whoseTurn() == player) bonus += 4;

// 검사를 끝내고 변수들을 초기화한다.

b = true; interrupt = false; c = 0;

// 세로줄에 대한 검사도 똑같이 실시한다.

for(int i = 0; i < 3; i++){

int cond = table[x + 3 * ((y + i) % 3)];

interrupt |= (cond != 0) && (table[coord] != cond);

b &= (player == cond) || (cond == 0);

c += table[coord] == cond ? 1 : 0;

}

if(b) bonus += 1;

if(!interrupt && c == 2 && t.whoseTurn() == player) bonus += 4;

 

// 왼쪽 위에서 오른쪽 아래로 향하는 대각선에 대한 검사를 실시한다.

if(coord == 0 || coord == 4 || coord == 8){

for(int i = 0; i < 3; i++){

int cond = table[i * 4];

interrupt |= (cond != 0) && (table[coord] != cond);

b &= (player == cond) || (cond == 0);

c += table[coord] == cond ? 1 : 0;

}

if(b) bonus += 1;

if(!interrupt && c == 2 && t.whoseTurn() == player) bonus += 4;

}

b = true; interrupt = false; c = 0;

 

// 오른쪽 위에서 왼쪽 아래로 향하는 대각선에 대한 검사를 실시한다.

if(coord == 2 || coord == 4 || coord == 6){

for(int i = 0; i < 3; i++){

int cond = table[(coord + 2 * i) % 6 == 0 ? 6 : (coord + 2 * i) % 6];

interrupt |= (cond != 0) && (table[coord] != cond);

b &= (player == cond) || (cond == 0);

c += table[coord] == cond ? 1 : 0;

}

if(b) bonus += 1;

if(!interrupt && c == 2 && t.whoseTurn() == player) bonus += 4;

}

b = true; interrupt = false; c = 0;

}

}

return bonus;

}

// 최종 평가모듈이다.

public void evaluate(){

// p1과 p2에 대한 가중치를 초기화한다.

initEval();

if(table != null){

// 승자에 대한 평가값을 설정한다.

if(table.isWinner(Table.player1)){

p1Bonus = 1;

p2Bonus = 0;

}else if(table.isWinner(Table.player2)){

p1Bonus = 0;

p2Bonus = 1;

// 만약 테이블이 꽉 찼을때는 무승부를 위한 평가값 0을 설정한다.

}else if(t.isFull())

eval = 0;

// 평가를 실시한다.

}else{

// 각 플레이어에 대한 가중치를 설정한다.

p1Bonus += evaluate(table, Table.player1);

p2Bonus += evaluate(table, Table.player2);

// 플레이어의 차례에 대한 가중치를 부여한다.

if(table.whoseTurn() == Table.player1)

p1Bonus++;

else

p2Bonus++;

}

// 최종 평가값을 계산한다.

eval = (p2Bonus + p1Bonus) == 0 ? 1 :

(((double)p1Bonus / ((double)p2Bonus+(double)p1Bonus)) * 2) - 1;

}

} 

• minMax 알고리즘의 구현

// 현재 가능한 수들의 좌표를 구하는 메소드이다

public int [] getPossibleMove(Table t){

int [] move;

int [] table = t.getTableArray();

int counter = 0;

// 빈 공간을 확인하면서 카운터를 증가시킨다.

for(int i = 0; i < 9; i++)

if(table[i] == 0)

counter++;

// 빈 공간 만큼의 배열을 생성한다.

move = new int[counter];

// 카운터 초기화

counter = 0;

// 루프를 발생시켜 빈공간인 좌표를 등록한다.

for(int i = 0; i < 9; i++)

if(table[i] == 0){

move[counter] = i;

counter++;

}

return move;

}

 

// 차례에 놓을 수 있는 수들에 대한 상태들을 리스트로 리턴하는 메소드이다.

public ArrayList<TableState> getNextMove(){

ArrayList<TableState> list = new ArrayList<TableState>();

// 빈공간인 좌표들을 확인하고

int [] possibleMove = getPossibleMove(t);

for(int i = 0; i < possibleMove.length; i++){

Table temp = new Table(t);

// 빈 공간으로 수를 둔 후에

temp.setMark(possibleMove[i]);

// 예상한 수에 대한 상태를 리스트에 추가한다.

list.add(new TableState(temp));

}

return list;

}

 

// minMax알고리즘으로 구성된 메소드 최적의 수를 둔 상태를 리턴한다.

public TableState getBestPosition(ArrayList<TableState> list){

// 처음 테이블상태는 예상 수들 중 아무거나 선택하게된다.

TableState bestPos = list.get((int)(Math.random() * list.size()));

for(TableState b : list){

// 시퀀스 값에 따라 최대, 최소 평가값을가진 상태를 bestPos로 지정한다.

if(t.getSequence())

bestPos = b.getEval() > bestPos.getEval() ? b : bestPos;

else

bestPos = b.getEval() < bestPos.getEval() ? b : bestPos;

}

return bestPos;

}

// 테스트 모듈

public static void main(String [] args){

Table t = new Table();

TableState temp = new TableState(t);

// 게임 테이블이 끝났는지를 확인하면서 루프를 발생

while(!t.isFinished()){

temp.getEval();

// 게임의 상태를 출력한다

System.out.println(temp + "\n");

// 컴퓨터가 최적의 위치를 결정하고 수를 둔다.

t.setMark(temp.getBestPosition(temp.getNextMove()).getTable().

getLatestPosition()

);

}

}

 

 • 실행 결과(minMax 알고리즘으로 구성된 인공지능 플레이어 두 명이 게임을 진행)

TableState33263331 Table@61de33[tableCount=0][sequence=O][isFull=false][isFinished=false]

- - -

- - -

- - -

[eval=0.0] [p1=2] [p2=2]

 

TableState33263331 Table@61de33[tableCount=1][sequence=X][isFull=false][isFinished=false]

- - -

- O -

- - -

[eval=0.25] [p1=5] [p2=3]

 

TableState33263331 Table@61de33[tableCount=2][sequence=O][isFull=false][isFinished=false]

X - -

- O -

- - -

[eval=0.11111111111111116] [p1=5] [p2=4]

 

TableState33263331 Table@61de33[tableCount=3][sequence=X][isFull=false][isFinished=false]

X - -

- O -

O - -

[eval=0.19999999999999996] [p1=6] [p2=4]

 

TableState33263331 Table@61de33[tableCount=4][sequence=O][isFull=false][isFinished=false]

X - X

- O -

O - -

[eval=0.0] [p1=5] [p2=5]

 

TableState33263331 Table@61de33[tableCount=5][sequence=X][isFull=false][isFinished=false]

X O X

- O -

O - -

[eval=0.11111111111111116] [p1=5] [p2=4]

 

TableState33263331 Table@61de33[tableCount=6][sequence=O][isFull=false][isFinished=false]

X O X

- O -

O X -

[eval=0.0] [p1=3] [p2=3]

 

TableState33263331 Table@61de33[tableCount=7][sequence=X][isFull=false][isFinished=false]

X O X

- O O

O X -

[eval=0.0] [p1=3] [p2=3]

 

TableState33263331 Table@61de33[tableCount=8][sequence=O][isFull=false][isFinished=false]

X O X

X O O

O X -

[eval=0.0] [p1=2] [p2=2]

 

TableState33263331 Table@61de33[tableCount=9][sequence=X][isFull=true][isFinished=true]

X O X

X O O

O X O

[eval=0.0] [p1=2] [p2=2]