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

jjuiddong
이동: 둘러보기, 찾기
5번째 줄: 5번째 줄:
  
  
 +
=== 돌 나누기 ===
 
* 오목 인공지능의 핵심은 돌들을 어떻게 나눗느냐다.
 
* 오목 인공지능의 핵심은 돌들을 어떻게 나눗느냐다.
 
** 6목, 여러개의 돌들로 얽혀졌을 때에 이 문제를 해결하려면 돌을 잘 나누어야 한다.
 
** 6목, 여러개의 돌들로 얽혀졌을 때에 이 문제를 해결하려면 돌을 잘 나누어야 한다.
33번째 줄: 34번째 줄:
 
  }
 
  }
  
* Filter
+
=== Filter ===
 
** 특정 조건이 성립되면 스트링을 바꾼다. (최적화를 위해)
 
** 특정 조건이 성립되면 스트링을 바꾼다. (최적화를 위해)
 
* 001101100 -> 11011
 
* 001101100 -> 11011
39번째 줄: 40번째 줄:
 
* 010110 -> S1011S
 
* 010110 -> S1011S
 
* 0101010 -> S10101S
 
* 0101010 -> S10101S
 +
 +
 +
=== MiniMax Tree ===
 +
* 알고리즘
 +
minimax()
 +
{
 +
  1. 흑돌에서 가장 좋은 수 순서대로 후보지를 뽑는다.
 +
  2. 백돌에서 가장 좋은 수 순서대로 후보지를 뽑는다.
 +
  3. 오목이 완성되면 종료
 +
  4. 두 후보지를 섞어 정렬한다.
 +
  5. 가장 높은 우선순위대로 minimax() 함수를 호출한다.
 +
  6. 리턴된 값중에 가장 높은 점수를 내놓은 후보지 위치를 리턴한다.
 +
}

2014년 3월 23일 (일) 21:07 판

Omok2.png


돌 나누기

  • 오목 인공지능의 핵심은 돌들을 어떻게 나눗느냐다.
    • 6목, 여러개의 돌들로 얽혀졌을 때에 이 문제를 해결하려면 돌을 잘 나누어야 한다.
    • 이부분은 separator namespace 로 따로 빼두었다.
      • 10 으로 이루어진 스트링을 입력받아, 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. 리턴된 값중에 가장 높은 점수를 내놓은 후보지 위치를 리턴한다.
}
개인 도구
이름공간

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