Minimax 알고리즘 내 스레딩

Question

3D Tic-Tac-Toe 게임을 디자인하고 Minimax 알고리즘의 한계점을 찾아야합니다. 깊이가 6까지는 크게 중요하지 않지만 (< 1s) 깊이가 높을수록 시간이 오래 걸립니다.

>Depth 7 = 6 seconds 
>Depth 8 = 49 seconds 
>Depth 9 = 314 seconds 

나는 더 높은 수심을 검사 할 시간이 없다 (하!). 최대 깊이는 22로, AI가 Move 1에서 가능한 모든 게임 상태를 분석하고 결코 사용자가 승리하지 못하게합니다.

Minimax 함수에서 스레딩을 구현하고 싶지만 스레딩에 비교적 새로운 기능입니다.

//player is -1 for human, +1 for AI 
function minimax(board_state, depth, player) 
    if depth <= 0 or board == full //full board means no further states 
     return score * player 
    bestScore = -1000; 
    foreach possible move 
     if valid move 
      /* */ 
      make_move() 
      bestScore = max(bestScore, minimax(board_state, depth-1, -player) 
      undo_move() 
      /* */ 
    return bestScore 

내가 /* */ 사이의 비트가 새로운 스레드입니다 뭔가를하려고하지만 문제가 발생 : 내 최소 최대 기능은 다음과 같은 경우에도 depth = 1로, 즉 8 개 스레드입니다. depth = 8은 16534863 스레드입니다. 스레드의 한계는 무엇입니까? 내 CPU에 몇 개의 물리적 코어가 연결되어 있습니까?

Answer 1

먼저 8 코어 시스템에서 속도를 얼마나 높일 수 있는지 생각해보십시오. 문제는 메모리 바운드가 아니라면 조금 더 좋아질 수 있습니다. Amdahl's law 및 Gustafson's law

문제는 a! N 문제처럼 보입니다. 시간이 지나면 폭발합니다. 코드 양을 크게 변경하여 옵션의 양을 줄이는 것을 고려해야합니다.

당신은 이미 당신의 minmax 알고리즘으로 게임 이론 방식으로 가고있는 것처럼 보입니다.

트리의 한 깊이에서 상대 플레이어의 승리를 결정하자마자 나머지 가능한 이동을 테스트 할 필요가 없으며 해당 부분 트리의 승자를 반환 할 수 있습니다.

Answer 2

솔루션이 멀티 스레딩이 아닙니다. 대신 Alpha–beta pruning을 조사해보세요. Naive minimax는 많은 중복 노드를 탐색합니다. 당신이 그래서,이 위치는 승리

oxo 
oxx 
xox 

반면 :

또한, 난 당신의 코드는 아무도 승리하지 의미하는

return score * player 

전체 보드 가능성이 무승부를 의미에서 잘못 대신 furhter 탐구의 점수를 반환 :

xxx 
0 
0 

Answer 3

은 박하 사탕 발가락을위한 완벽한 전략이, clearly described in Wikipedia. 나는 자바 스크립트 게임에서 그것을 구현했고 그것은 쉽다. 스레딩 없음, 알파 베타 잘라 내기 없음, 미니 맥스 없음, 아무 것도 없음 ...

완벽한 시작은 두 번 이동 (상대 포크 차단)을하지 않으므로 라이브로 사용할 수 있습니다.

참고 : tic tac 발가락을위한 보드는 매우 대칭 적이므로 어떤 방법을 사용하더라도 유효한 이동 수를 크게 줄일 수 있습니다. 완벽한 전략을 살펴 본다면, 이동 횟수는 클래스 ("센터", "반대편 코너", "빈 코너", "빈 사이드" 등)에서 집계됩니다.