Algorithm/MinMax & Recursive
Java Self-Invocation & MinMax example
Soul-Learner
2016. 10. 12. 21:15
재귀호출(Self-Invocation)을 이용한 MinMax 알고리듬 구현
이 예제를 보기 전에 MinMax알고리듬에 대한 이해가 반드시 필요합니다 MinMax 알고리듬을 자세히 이해하려면 여기 링크를 눌러 참조하세요
재귀호출은 성능이나 메모리 사용면에서 보면 일반 반복문에 비하여 상대적으로 불리한 점이 있지만 일반 반복문을 사용할 수 없는 상황에서 재귀호출만이 가능한 수단이라면 어쩔 수 없이 사용해야 한다. 게임이나 인공지능 분야에서 더 자주 사용되기도 하는 재귀호출을 잘 이해하고 설계하기 위해서는 재귀호출의 시작부분과 끝 부분을 명확히 정의할 수 있어야 하고 다중호출된 메소드의 실행순서에 대해서 잘 이해하고 그 순서를 활용할 수 있어야 한다. 재귀호출에서는 가장 먼저 호출된 메소드가 가장 나중에 완료되고, 가장 마지막에 호출된 메소드가 가장 먼저 완료되므로 이 순서를 잘 이용하여 작업을 수행해야 한다.
재귀호출을 이용하여 트리노드 중에서 최대값을 구하는 예
package recursive;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Node res = getMaxNode();
System.out.printf("최종최대 --> %d ", res.value);
}
static int value;
static int cnt;
static int delta = 1;
static List<Node> maxList = new ArrayList<>();
static Node getMaxNode()
{
List<Node> list = new ArrayList<>();
for(int i=0;i<3;i++) {
Node n = new Node();
value += delta;;
n.value = value;;
if(value==6) delta = -1;
list.add( n);
System.out.printf("%d ", n.value);
}
System.out.println();
if(cnt++ < 3){
getMaxNode();
}
Node nodeMax = list.get(0);
for(int i=0;i<list.size();i++){
Node _node = list.get(i);
if(_node.value > nodeMax.value) nodeMax = _node;
}
maxList.add(nodeMax);
System.out.printf("부분최대: %d %n", nodeMax.value);
nodeMax = maxList.get(0);
for(int i=0;i<maxList.size();i++){
Node _node = maxList.get(i);
if(_node.value > nodeMax.value) nodeMax = _node;
}
return nodeMax;
}
}
class Node
{
String[] matrix = new String[9];
String layer;
int depth;
int value;
int num;
Node(){
for(int i=0;i<matrix.length;i++){
matrix[i] = " ";
}
}
Node(String layer) {
this();
this.layer = layer;
}
Node(int depth){
this();
this.depth = depth;
}
Node(String layer, int depth){
this();
this.layer = layer;
this.depth = depth;
}
Node(String layer, int depth, int value){
this();
this.layer = layer;
this.depth = depth;
this.value = value;
}
boolean isGameOver(){
for(int i=0;i<matrix.length;i++){
if(matrix[i].equals(" ")) return false;
}
return true;
}
void updateMatrix(String[] matrix){
for(int i=0;i<matrix.length;i++){
this.matrix[i] = matrix[i];
}
}
String inverseLayer(){
return this.layer.equals("MAX") ? "MIN" : "MAX";
}
}최대값을 가진 노드로 이동하기 위한 첫번째 노드 구하기
package recursive;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Node res = getMaxNode(null);
System.out.printf("최종최대 --> 노드번호:%d 노드값:%d", res.num, res.value);
}
static int num;
static int value=50;
static int cnt;
static int delta = 1;
static List<Node> maxList = new ArrayList<>();
static Node getMaxNode(Node p)
{
List<Node> list = new ArrayList<>();
for(int i=0;i<3;i++) {
Node n = new Node();
n.num = ++num;
value += delta;;
n.value = value;;
if(value==50) delta = -1;
list.add( n);
System.out.printf("%d ", n.value);
}
System.out.println();
if(cnt++ < 3){
for(int i=0;i<list.size();i++) {
getMaxNode( list.get(i) );
}
}
Node nodeMax = list.get(0);
for(int i=0;i<list.size();i++){
Node _node = list.get(i);
if(_node.value > nodeMax.value) nodeMax = _node;
}
if (p==null) return nodeMax;
else {
if(p.value < nodeMax.value)
p.value = nodeMax.value;
return p;
}
}
}
class Node
{
String[] matrix = new String[9];
String layer;
int depth;
int value;
int num;
Node(){
for(int i=0;i<matrix.length;i++){
matrix[i] = " ";
}
}
Node(String layer) {
this();
this.layer = layer;
}
Node(int depth){
this();
this.depth = depth;
}
Node(String layer, int depth){
this();
this.layer = layer;
this.depth = depth;
}
Node(String layer, int depth, int value){
this();
this.layer = layer;
this.depth = depth;
this.value = value;
}
boolean isGameOver(){
for(int i=0;i<matrix.length;i++){
if(matrix[i].equals(" ")) return false;
}
return true;
}
void updateMatrix(String[] matrix){
for(int i=0;i<matrix.length;i++){
this.matrix[i] = matrix[i];
}
}
String inverseLayer(){
return this.layer.equals("MAX") ? "MIN" : "MAX";
}
}MinMax 알고리듬을 구현한 예
package recursive;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
System.out.println("번호, 레이어, 깊이, 값, 부모");
System.out.println("----------------------------------------------");
Node res = minmax(null);
System.out.println("----------------------------------------------");
System.out.printf("MinMax 최종선택노드--> 번호:%d 레이어:%s depth:%d value:%d", res.num, res.layer, res.depth, res.value);
}
static int num;
static Node minmax(Node p)
{
List<Node> list = new ArrayList<>();
String layer = (p==null || p.layer.equals("MIN")) ? "MAX" : "MIN";
int depth = p==null ? 1 : p.depth+1;
for(int i=0;i<2;i++) {
Node n = new Node(++num, layer, depth);
list.add( n);
System.out.printf("(%d, %s, %d, %d, %d) ",n.num, n.layer, n.depth, n.value, p==null ? 0 : p.num);
}
System.out.println();
if(list.size()==0) return p;
else{
if(p==null || (list.get(0).depth < 3)){
for(int i=0;i<list.size();i++) {
minmax( list.get(i) );
}
}
}
Node retNode = null;
if(p==null || p.layer.equals("MAX")) {
retNode = list.get(0);
for(int i=0;i<list.size();i++){
Node _node = list.get(i);
if(_node.value > retNode.value) retNode = _node;
}
if(p!=null && retNode.value > p.value) p.value = retNode.value;
}else{
retNode = list.get(0);
for(int i=0;i<list.size();i++){
Node _node = list.get(i);
if(_node.value < retNode.value) retNode = _node;
}
if(retNode.value < p.value) p.value = retNode.value;
}
if (p==null) return retNode;
else return p;
}
}
class Node
{
String[] matrix = new String[9];
{
for(int i=0;i<matrix.length;i++){
matrix[i] = " ";
}
}
String layer;
int depth;
int value;
int num;
Node(){}
Node(int num, String layer, int depth){
this.num = num;
this.layer = layer;
this.depth = depth;
this.value = evaluate();
}
int evaluate(){
Random rd = new Random();
return rd.nextInt(11);
}
boolean isGameOver(){
for(int i=0;i<matrix.length;i++){
if(matrix[i].equals(" ")) return false;
}
return true;
}
void updateMatrix(String[] matrix){
for(int i=0;i<matrix.length;i++){
this.matrix[i] = matrix[i];
}
}
String inverseLayer(){
return this.layer.equals("MAX") ? "MIN" : "MAX";
}
}재귀호출이 이용되는 인공지능 오목게임의 예 ( MinMax 알고리듬의 구현)
package minmax;
import java.util.*;
public class Main
{
static int num; // 디버깅 목적으로 사용되는 노드번호
static Node game = new Node(); //게임의 현황에 대한 정보
/**
* 상대방이 선택한 위치에 'x' 를 기록하고 그 수에 대응하는 수를 minmax알고리듬을
* 이용하여 평가한 후에 해당 위치를 숫자(ox를 기록한 문자열 배열의 index)로 리턴한다
* @param idx 상대방의 수의 위치(ox를 기록한 문자열 배열의 index)
* @return minmax알고리듬을 이용하여 평가된 대응 수의 위치(ox를 기록한 문자열 배열의 index)
*/
static int userMove(int idx)
{
//상대방의 한 수
if(game.matrix[idx].equals(" ")) game.move(idx,"x");
System.out.println("상대방의 수");
game.printDebug();
if(game.value==-1){
System.out.println("Game Over! Winner->[x]");
}
//컴퓨터의 대응 수
Node n = minmax(null);
int evalPos = game.getEvaluatedIndex(n);
game.move(evalPos, "o");
System.out.printf("minmax로 평가된 위치:%d %n", evalPos);
game.printDebug();
if(game.value==1){
System.out.println("Game Over! Winner->[o]");
}
return evalPos;
}
public static void main(String[] args)
{
int res = userMove(0);
res = userMove(3);
res = userMove(7);
}
/**
* 파라미터 p의 하위 노드를 생성하고 하위노드 중에서 minmax 알고리듬으로 선택된 노드를 리턴한다
* p가 null이면 하위 노드 중에서 가장 큰 값을 가진 노드를 리턴하고, p가 null이 아니고 특정 노드
* 라면 해당 노드의 값에 하위노드의 최대 혹은 최소 값을 복사하여 리턴한다
* @param p 상위 노드, 최상위 노드라면 null이 전달된다
* @return p가 null이면 하위노드 중에서 가장 큰 값을 가진 노드가 리턴되고 p가 null이 아니면
* p가 리턴되는데, 이 때 p의 하위 노드 중에서 가장 큰 값 혹은 가장 작은 값이 p의 value속성에 복사되어
* p가 리턴된다. p가 MAX 노드이면 하위노드의 값 중에서 가장 큰 값이 p에 복사되고, MIN 노드이면
* 하위 노드 중에서 가장 작은 값이 p에 복사되어 p가 리턴된다
*/
static Node minmax(Node p)
{
List<Node> list = new ArrayList<>();
String layer = (p==null || p.layer.equals("MIN")) ? "MAX" : "MIN";
int depth = p==null ? 1 : p.depth+1;
Node n = null;
String[] bd = (p==null) ? game.matrix : p.matrix;
for(int i=0;i<bd.length;i++) {
if(bd[i].equals(" ")){ //빈 곳을 찾아 하위노드로 표현한다
n = new Node(++num, layer,depth, bd);//보드의 현황 복사
n.move(i,layer.equals("MAX") ? "o" : "x"); //빈 곳마다 한 수를 표시
list.add(n);
}
}
// 노드 p의 하위노드가 없다는 것은 빈 곳이 없다는 의미이므로 p는 말단 노드가 된다
if(list.size()==0) return p;
else{ // 노드 p의 하위노드가 있는 경우에는 그 하위노드의 하위노드를 생성하기 위해 재귀호출
for(int i=0;i<list.size();i++) {
Node node = list.get(i); //게임이 종료되지 않은 노드에는 하위노드를 생성한다
if(node.value!=1 && node.value!=-1){// 게임이 승부가 난 상태인지 검사
minmax( list.get(i) );
}
}
}
//추가된 하위노드들의 점수를 평가하여 부모노드의 점수에 반영한다
Node retNode = null;
if(p==null || p.layer.equals("MAX")) { //MAX 노드인 경우
retNode = list.get(0);
for(int i=0;i<list.size();i++){
Node _node = list.get(i);
if(_node.value > retNode.value) retNode = _node;
}
if(p!=null) p.value = retNode.value;
}else{ //MIN 노드인 경우
retNode = list.get(0);
for(int i=0;i<list.size();i++){
Node _node = list.get(i);
if(_node.value < retNode.value) retNode = _node;
}
if(p!=null) p.value = retNode.value;
}
if (p==null) return retNode;
else return p;
}
}
class Node
{
/**
* 현재노드의 게임 현황을 1차원 문자열 배열로 표현함
*/
String[] matrix = new String[9];
{
for(int i=0;i<matrix.length;i++){
matrix[i] = " ";
}
}
String layer; // 상대방(MIN), 컴퓨터(MAX)
int depth; //루트노드가 1이고 그 하위는 2,3....
int value; //MAX가 이기면 1, 지면 -1, 비기면 0 으로 평가된 점수를 저장
int num; //디버깅 목적으로 사용
Node(){}
Node(String layer, int depth, String[] mat){
this.layer = layer;
this.depth = depth;
updateMatrix(mat);
}
/**
* 디버깅 목적으로 사용되는 생성자
* @param num 노드번호
* @param layer "MAX", "MIN"
* @param depth 루트는 1, 그 하위는 2,3,....
* @param mat 게임현황 1차원 문자열 배열
*/
Node(int num, String layer, int depth, String[] mat){
this(layer,depth, mat);
this.num = num;
}
/**
* 현재 노드의 값을 평가한다. 컴퓨터(MAX)가 이기면 1, 상대방(MIN)이 이기면 -1, 비기면 0으로
* 점수를 평가하여 그 값을 멤버변수 value에 할당하고 value값을 리턴한다
* @return 현재 노드의 점수
*/
int evaluate(){
String ox = matrix[0];
if(ox.equals(matrix[1]) && ox.equals(matrix[2])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[3];
if(ox.equals(matrix[4]) && ox.equals(matrix[5])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[6];
if(ox.equals(matrix[7]) && ox.equals(matrix[8])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[0];
if(ox.equals(matrix[3]) && ox.equals(matrix[6])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[1];
if(ox.equals(matrix[4]) && ox.equals(matrix[7])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[2];
if(ox.equals(matrix[5]) && ox.equals(matrix[8])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[0];
if(ox.equals(matrix[4]) && ox.equals(matrix[8])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
ox = matrix[2];
if(ox.equals(matrix[4]) && ox.equals(matrix[6])) {
if(ox.equals("o")) value = 1;
else if(ox.equals("x")) value = -1;
}
if(value==1 || value==-1) return value;
return 0;
}
/**
* 게임이 현재 종료된 상태인지 확인하여 true, false로 리턴한다
* @return 게임이 종료된 상태이면 true, 아니면 true
*/
boolean isGameOver(){
if(this.value==1 || this.value==-1) return true;
for(int i=0;i<matrix.length;i++){
if(matrix[i].equals(" ")) return false;
}
return true;
}
/**
* minmax 알고리듬을 이용하여 평가된 대응 수를 게임의 현황에 반영한다
* @param mat String[]
*/
void updateMatrix(String[] mat){
for(int i=0;i<matrix.length;i++){
this.matrix[i] = mat[i];
}
}
/**
* 새로운 자식 노드를 생성할 때 부모의 노드가 MAX이면 그 하위노드는 MIN이어야 하고
* MIN인 경우에는 그 하위 노드는 MAX이어야 하므로 이 메소드를 호출하여 사용한다
* @return 현재의 노드가 MAX이면 MIN, MIN이면 MAX를 리턴함
*/
String inverseLayer(){
return this.layer.equals("MAX") ? "MIN" : "MAX";
}
/**
* 상대방이나 컴퓨터가 수를 둘 때 선택한 위치에 'o' 혹은 'x'를 입력하고
* 그 점수를 평가하여 멤버변수 value에 할당한다
* @param idx 문자열 배열의 인덱스
* @param mark 'o'혹은 'x'
*/
void move(int idx, String mark){
matrix[idx] = mark;
evaluate();
}
/**
* minmax 알고리듬에 의해 평가된 결과를 숫자형태로 리턴한다 (문자열 배열의 인덱스)
* @param evalNode minmax 알고리듬에 의해 평가되어 다음 수로 선택된 노드
* @return minmax 알고리듬에 의해 평가된 수를 둘 위치(문자열 배열의 인덱스)
*/
int getEvaluatedIndex(Node evalNode){
for(int i=0;i<matrix.length;i++){
if(!matrix[i].equals(evalNode.matrix[i])){
return i;
}
}
return -1;
}
void printDebug() {
System.out.printf(" %s | %s | %s\t%s, value : %d%n", matrix[0],matrix[1],matrix[2],layer==null?"MIN":layer, evaluate());
System.out.println("-----------");
System.out.printf(" %s | %s | %s%n", matrix[3],matrix[4],matrix[5]);
System.out.println("-----------");
System.out.printf(" %s | %s | %s%n", matrix[6],matrix[7],matrix[8]);
System.out.println("\n");
}
}위의 코드를 실행하면 다음과 같은 결과를 볼 수 있다.
이 테스트에서는 알고리듬이 정상적으로 실행되고 있다는 것을 확인할 수 있다
x : 상대방
o : minmax
