"오목 인공지능"의 두 판 사이의 차이

jjuiddong
이동: 둘러보기, 찾기
(Customize)
(Customize)
 
(한 사용자의 중간의 편집 11개 숨겨짐)
8번째 줄: 8번째 줄:
 
* 오목 인공지능의 핵심은 돌들을 어떻게 잘 나누는가 이다.
 
* 오목 인공지능의 핵심은 돌들을 어떻게 잘 나누는가 이다.
 
** 6목, 여러개의 돌들로 얽혀졌을 때에 이 문제를 해결하려면 돌을 잘 나누어야 한다.
 
** 6목, 여러개의 돌들로 얽혀졌을 때에 이 문제를 해결하려면 돌을 잘 나누어야 한다.
 +
** 돌이 나열된 형태는 선이므로, 오목은 선 단위로 돌을 분석하면 된다.
 
** 이 부분은 separator namespace 로 따로 빼두었다.
 
** 이 부분은 separator namespace 로 따로 빼두었다.
 
*** 1,0 으로 이루어진 스트링을 입력받아, n개의 스트링으로 나눠 리턴한다.
 
*** 1,0 으로 이루어진 스트링을 입력받아, n개의 스트링으로 나눠 리턴한다.
56번째 줄: 57번째 줄:
 
* minimax 알고리즘이 돌아가기 위해서는 오목의 수치화가 필요하다.
 
* minimax 알고리즘이 돌아가기 위해서는 오목의 수치화가 필요하다.
 
** 현재 흑돌, 백돌의 상황에서 누가 더 유리한 상황인지 비교 가능해야 한다.
 
** 현재 흑돌, 백돌의 상황에서 누가 더 유리한 상황인지 비교 가능해야 한다.
 +
*** 흑돌과 백돌사이에서 가장 좋은 수를 비교 한다.
 +
*** 3 이 하나 있을 때와 3,3이 두개 있을 때 무엇이 더 높을까?
 
** 1101 vs 111  혹은 1111 vs 1101 등 각 조합을 수치화 시켜 비교 가능해야 한다.
 
** 1101 vs 111  혹은 1111 vs 1101 등 각 조합을 수치화 시켜 비교 가능해야 한다.
 
** 지금 돌을 놓을 사람에게 좀더 높은 점수가 부여되야 한다. 똑같은 수더라도 먼저 둘 사람이 유리하다.
 
** 지금 돌을 놓을 사람에게 좀더 높은 점수가 부여되야 한다. 똑같은 수더라도 먼저 둘 사람이 유리하다.
** 01110 > X1110  
+
** 돌비교 함수
** 011010 = 01110
+
*** 01110 > X1110  
** 01110 > 0110
+
*** 011010 = 01110
** 011110 > X11110
+
*** 01110 > 0110
** X11110 > 01110
+
*** 011110 > X11110
** X1111X < X1110
+
*** X11110 > 01110
** X1111X = X111X
+
*** X1111X < X1110
 +
*** X1111X = X111X
  
 
=== 3-3 찾기 ===
 
=== 3-3 찾기 ===
  
  1. 가장 좋은 수 순서대로 후보지를 얻는다.
+
  1. 가장 좋은 수 순서대로 후보지를 얻는다.  
 
  2. 후보지를 중심으로 map<Pos,Data> 맵에 저장한다.
 
  2. 후보지를 중심으로 map<Pos,Data> 맵에 저장한다.
 
  3. 후보지 별로 정렬한다.
 
  3. 후보지 별로 정렬한다.
 
  4. 같은 후보지에 두개 이상의 수가 존재하고 3-3 일 때 해당 후보지는 제거 한다.
 
  4. 같은 후보지에 두개 이상의 수가 존재하고 3-3 일 때 해당 후보지는 제거 한다.
 +
 +
(후보지(Pos)는 오목판의 x,y 위치를 뜻하며, 프로그램에서는 구조체 혹은 pair<int,int>로 구현한다.)
  
* map 을 이용해 위치를 중심으로 정렬한후, 타입별로 정렬하면 끝난다.
+
* map 을 이용해 위치를 중심으로 정렬한후, 타입별로 정렬하면 끝난다. (돌타입별로 정렬해야 가장 높은 돌로 3-3인지 판단할 수 있다.)
  
 
=== Customize ===
 
=== Customize ===
  
 
* 011010  일경우 한개 돌만 검사하면 다른 돌은 검사하지 않아도 된다.
 
* 011010  일경우 한개 돌만 검사하면 다른 돌은 검사하지 않아도 된다.
 +
** 라인 단위로 돌을 검사하기 때문에 가능하다.
 
* 재귀적으로 minimax 트리가 만들어지는 상황에서 달라지는 돌은 하나밖에 없으므로 lookup 테이블을 이용할 수 있다.
 
* 재귀적으로 minimax 트리가 만들어지는 상황에서 달라지는 돌은 하나밖에 없으므로 lookup 테이블을 이용할 수 있다.
 
** lookup table< Pos, type > 타입의 map 으로 구현한다.
 
** lookup table< Pos, type > 타입의 map 으로 구현한다.
 
** 이 때의 pos 는 후보지 위치를 나타내는 x,y좌표 구조체다.
 
** 이 때의 pos 는 후보지 위치를 나타내는 x,y좌표 구조체다.
 
* minimax 트리를 만들어갈 때 탐색하지 않아도 되는 노드를 미리 검사할 수 있다.
 
* minimax 트리를 만들어갈 때 탐색하지 않아도 되는 노드를 미리 검사할 수 있다.
** 01110 이 있는 상태에서 상대의 0110 노드는 탐색할 필요가 없다.
+
** 01110 돌에 놓을 때, 상대의 0110 노드는 탐색할 필요가 없다. (상대적으로 낮은 돌은 검사하지 않아도 된다.)

2015년 5월 3일 (일) 23:41 기준 최신판

Omok2.png


목차

[편집] 돌 나누기

  • 오목 인공지능의 핵심은 돌들을 어떻게 잘 나누는가 이다.
    • 6목, 여러개의 돌들로 얽혀졌을 때에 이 문제를 해결하려면 돌을 잘 나누어야 한다.
    • 돌이 나열된 형태는 선이므로, 오목은 선 단위로 돌을 분석하면 된다.
    • 이 부분은 separator namespace 로 따로 빼두었다.
      • 1,0 으로 이루어진 스트링을 입력받아, n개의 스트링으로 나눠 리턴한다.
  • 1 : 돌
  • 0 : 빈자리
  • X : 놓아서는 안될 곳
  • S : 놓을 수는 있지만 우선순위에 의해서 놓지 않을곳
  • 0011010011110001010 -> 0011010 + 0111110 + 001010
  • 011101011110 -> 011101X + 11110
  • 011010 -> S1101S
    • 가운데 빈곳에 돌을 놓을 때 가장 좋은 결과를 얻게된다. 011110
  • 돌을 나누는 알고리즘
while( separate(source, dest, remainder))
{
  source = remainder;
  dest 저장
}

separate(src, dst, remainder)
{
  dst = src를 5개 단위로 나눠 저장.
  separateTwo(dst, tmp1, tmp2)
  dst = tmp1
  remainder = tmp2 + src의 나머지;
}

[편집] Filter

  • 특정 조건이 성립되면 스트링을 바꾼다. (최적화를 위해)
    • 001101100 -> 11011
    • 0101110 -> 10111
    • 010110 -> S1011S
    • 0101010 -> S10101S

[편집] MiniMax Tree

minimax()
{
 1. 흑돌에서 가장 좋은 수 순서대로 후보지를 뽑는다.
 2. 백돌에서 가장 좋은 수 순서대로 후보지를 뽑는다.
 3. 오목이 완성되면 종료
 4. 두 후보지를 섞어 정렬한다.
 5. 가장 높은 우선순위대로 minimax() 함수를 다시 호출한다.
 6. 리턴된 값중에 가장 높은 점수를 내놓은 후보지 위치를 리턴한다.
}
  • minimax 알고리즘이 돌아가기 위해서는 오목의 수치화가 필요하다.
    • 현재 흑돌, 백돌의 상황에서 누가 더 유리한 상황인지 비교 가능해야 한다.
      • 흑돌과 백돌사이에서 가장 좋은 수를 비교 한다.
      • 3 이 하나 있을 때와 3,3이 두개 있을 때 무엇이 더 높을까?
    • 1101 vs 111 혹은 1111 vs 1101 등 각 조합을 수치화 시켜 비교 가능해야 한다.
    • 지금 돌을 놓을 사람에게 좀더 높은 점수가 부여되야 한다. 똑같은 수더라도 먼저 둘 사람이 유리하다.
    • 돌비교 함수
      • 01110 > X1110
      • 011010 = 01110
      • 01110 > 0110
      • 011110 > X11110
      • X11110 > 01110
      • X1111X < X1110
      • X1111X = X111X

[편집] 3-3 찾기

1. 가장 좋은 수 순서대로 후보지를 얻는다. 
2. 후보지를 중심으로 map<Pos,Data> 맵에 저장한다.
3. 후보지 별로 정렬한다.
4. 같은 후보지에 두개 이상의 수가 존재하고 3-3 일 때 해당 후보지는 제거 한다.

(후보지(Pos)는 오목판의 x,y 위치를 뜻하며, 프로그램에서는 구조체 혹은 pair<int,int>로 구현한다.)
  • map 을 이용해 위치를 중심으로 정렬한후, 돌 타입별로 정렬하면 끝난다. (돌타입별로 정렬해야 가장 높은 돌로 3-3인지 판단할 수 있다.)

[편집] Customize

  • 011010 일경우 한개 돌만 검사하면 다른 돌은 검사하지 않아도 된다.
    • 라인 단위로 돌을 검사하기 때문에 가능하다.
  • 재귀적으로 minimax 트리가 만들어지는 상황에서 달라지는 돌은 하나밖에 없으므로 lookup 테이블을 이용할 수 있다.
    • lookup table< Pos, type > 타입의 map 으로 구현한다.
    • 이 때의 pos 는 후보지 위치를 나타내는 x,y좌표 구조체다.
  • minimax 트리를 만들어갈 때 탐색하지 않아도 되는 노드를 미리 검사할 수 있다.
    • 01110 돌에 놓을 때, 상대의 0110 노드는 탐색할 필요가 없다. (상대적으로 낮은 돌은 검사하지 않아도 된다.)
개인 도구
이름공간

변수
행위
둘러보기
도구모음