MinMax 알고리즘

개념

최대 최소 전략을 사용하여서 턴제 게임과 같은 프로그램에서 의사결정에 주로 사용하는 알고리즘 게임 전략 알고리즘으로써 내 턴에서는 가장 좋은 경우를 상대턴에서는 가장 안좋은 경우를 선택하는 것을 의미한다.

틱택토 알고리즘 출저 위의 이미지에서 확인해 보면 현재 갈 수 있는 모든 경우의 수를 확인해 보았을 때 Return Value를 통해서 자신이 갈 수 있는 최선의 위치를 확인해 볼 수 있다. 위의 3개를 비교해 보면 왼쪽과 중간에는 자신이 질 수 있는 경우의 수가 존재하나 오른쪽의 경우의 수를 고르게 되는 것이 위의 시점에서 최선의 방식이다.

예시 문제

문제 링크 위의 문제에서는 두 캐릭터가 발판위에서 가장 오래 살아남는 방법에 대해 조사하는 알고리즘이다.

중요한 요점

• 플레이어 A 부터 시작한다.
• 플레이어는 이기기 위해서 최선의 플레이를 진행한다.
• 패배의 조건
  • 이동할 발판이 존재하지 않는 경우
  • 같은 위치에 있어서 다른 유저가 움직여서 현재 발판이 사라지는 경우

잘못된 접근

처음에 문제를 봤을 때에는 발판의 수가 최대 5개로 높지 않고 최선의 경우의 수를 찾는 것이라 판단을 해서 DFS로 접근을 하였었다. 이 때 항상 최선이 플레이를 하더라도 경우의 수를 찾았을 때 충분히 찾을 수 있을 것이라 판단하였었으나 이 경우 이긴 플레이의 경우 가장 많이 움직인 경우는 최선의 플레이를 하지 않은 경우로 확인이 되어서 다른 접근 방법이 있을 것이라 판단하였다.

Min Max 알고리즘을 사용한 접근 방법

먼저 자신이 최선의 수를 두었다는 가정하에 어떤 방식으로 접근이 되는지를 먼저 파악을 했어야 했다.

놓친 부분

• A가 둘 수 있는 최선의 수를 위주로 생각하고 B가 둘 수 있는 최선의 수만 생각해서 접근하다 보니 어떤 경우에 특정 플레이어가 이길 수 있는지 일반화를 하지 못하였다.

접근 방법

• 해당 문제에서는 그래프를 그려보면 자신이 이길 수 있는 것에 대한 판단은 턴수로 알 수 있었다.
• A가 지는 경우는 짝수 경우만 가능하다

주요 로직

두는 순서를 변경하는 로직

처음에는 한 사이클로 A가 두고 B가 두는 방식으로 접근을 하였었습니다. 하지만 그렇게 접근 할 시 step에 대해서 코드가 복잡해 지는 부분이 있었습니다. 이후 예제 코드를 살펴보다가 아래와 같이 현재 이동과 대기로 나누어서 다음과 같이 스위치 하면서 접근을 하는 로직을 보게 되었고 추후에도 번갈아가면서 게임을 진행하는 경우 아래와 같이 적용 하면 좋을 것 같아서 기록해 둔다.

// 현재 확인할 row/col    다음에 확인할 row/col
public int dfs(int[][] board, int row, int col, int tRow, int tCol, int depth) {
 
	...
 
	for(int i = 0 ; i < 4; i++) {
		// 다음에 확인할 row/col을 지금으로 넣어준다.
		int dfs = dfs(board, tRow, tCol, afterRow, afterCol, depth + 1) + 1;
	
	}
}

현재 승리 로직 중에서 최선의 로직을 고르는 방법

일반적인 DFS 탐색 로직을 제외 하고 가장 중요한 로직이다. 여기서 적혀있는 dfs value는 최적의 게임 수까지 걸린 이동 수이다.

result 변수는 현재 위치에서 최적의 결과를 저장하는 변수이다. 초기값이 0으로 설정된 이유는 이 자리에서 게임이 끝난 경우 아무것도 얻지 못함을 의미한다.

현 문제에서는 A부터 시작을 하게 되는데 짝수턴에 끝난 경우에는 무조건 A가 진 경우이고 홀수 턴에 끝난 경우에는 무조건 A가 이기는 경우이다. ex> (dfs 진입 전)A ⇒ B ⇒ A ⇒ B 와 같이 진행이 되므로 행동이 끝난 이후 자신이 졌는지 이겼는지가 판단이 가능하다. 따라서 아래와 같은 조건으로 확인이 가능하다. 승리와 패배 판정

• dfs % 2 == 1
  • 승리 하는 경우
• dfs % 2 == 0
  • 패배하는 경우

여기서 최선의 플레이의 조건을 나눠 본다면 이길 수 있으면 가장 빨리 끝내고 진 다면 최대한 오래 끄는 방향으로 접근을 하면 된다.

public int dfs(int[][] board, int row, int col, int tRow, int tCol, int depth) {
	//result는 현재 위치에서 최적의 결과를 저장하는 변수입니다.
	int result = 0;
	  
	// 현재 발판 확인  
	if (board[row][col] == 0) {  
	    return 0;  
	}
 
	for(int i = 0; i < 4; i++) {
 
		...
 
 
		// 한 번이라도 이긴 경우 && 지금 까지 다 진 경우
		if (dfs % 2 == 1 && result % 2 == 0) {  
		    result = dfs;  
		} //        다 지는 경우 && 다 진경우
		else if (dfs % 2 == 0 && result % 2 == 0) {  
		    result = Math.max(dfs, result);  
		} //  이긴 경우가 있는 경우 && 이긴 경우
		else if (dfs % 2 == 1 && result % 2 == 1) {  
		    result = Math.min(dfs, result);  
		}
	}
 
	
	}

참고 블로그

틱택토