오목 AI 알고리즘 6 편 - 반복 심화

앞에서 말 한 것 은 살 해 를 계산 하 는 것 이 고, 사실은 살 해 를 계산 하기 전에 교체 의 깊이 를 말 해 야 한다.이 문장 들 은 내 가 하면 서 쓴 필기 이기 때문에 순서 가 그리 엄밀 하지 않 을 것 이다.
AI 가 최 적 화 를 찾 지 못 했 습 니 다.
앞의 모든 알고리즘 에 따라 이 루어 진 후에 (물론 계산 살 포함 되 지 않 음) 비교적 심각 한 문 제 를 발견 할 수 있다. 바로 컴퓨터 가 자신 이 이미 승산 이 있 는 상황 에서 (쌍 삼 같은 바둑 은 갈 수 있다) 4 와 같은 바둑 을 가지 고 놀 수 있다 는 것 이다 .이런 주 법 이 나타 난 본질은 지금의 AI 가 최종 결과 만 비교 하고 경로 의 장단 점 을 고려 하지 않 았 기 때문이다.그래서 6 층 에서 하나, 둘, 셋 을 검색 하기 쉬 우 며, 사실 4 층 에 도 하나, 둘, 셋 이 있 는데, 점수 가 같 기 때문에 AI 가 무 작위 로 하 나 를 선택 하기 때문이다.2 보 로 이 길 수 있 는데 도 AI 가 굳이 3 보 를 걷 게 되면 서 게이머 들 에 게 는 사람 을 희롱 하 는 느낌 이 들 었 다.
그래서 여기 서 우 리 는 의 개념 을 정의 한다. 점수 가 가장 높 은 방법 중 경로 가 가장 짧 은 방법 이다.그렇다면 지금 문 제 는 우리 가 어떻게 최 적 화 를 찾 느 냐 하 는 것 이다.
반복 심화
우 리 는 AB 검색 을 통 해 모든 최고 분 주 법 을 찾 을 수 있다. 직관 적 인 생각 은 우리 가 모든 방법 을 찾 은 다음 에 그들의 길 이 를 비교 하고 길이 가 가장 짧 은 방법 을 선택 하 는 것 이다.
이것 은 확실히 방법 이지 만 우 리 는 효율 적 이 고 높 은 방법 을 찾 을 수 있다. 바로 을 통 해 최 단 경 로 를 우선적으로 찾 는 것 이다.
교체 심화 란 2 층 부터 승리 의 방법 을 찾 거나 깊이 제한 에 도달 할 때 까지 검색 깊이 를 점차 늘 리 는 것 이다.예 를 들 어 우리 가 6 층 깊이 를 검색 하면 우 리 는 먼저 2 층 을 시도 하고 이 길 수 있 는 방법 을 찾 지 못 하면 4 층 을 시도 하고 마지막 으로 6 층 을 시도 한다.우 리 는 짝수 층 만 시도 한다.홀수 층 은 사실 컴퓨터 가 게이머 보다 한 걸음 더 걸 었 기 때문에 게이머 들 의 수 비 를 무시 하고 더 좋 은 해법 을 찾 지 못 할 것 이다.
그래서 이 알고리즘 을 실현 하 는 것 은 매우 간단 하 다.

var deeping = function(board, deep) {
  deep = deep === undefined ? config.searchDeep : deep;
  //    
  //             ，                ，        ，             
  var result;
  for(var i=2;i<=deep; i+=2) {
    result = maxmin(board, i);
    if(math.greatOrEqualThan(result.score, SCORE.FOUR)) return result;
  }
  return result;
}

이곳 은 한 층 의 검색 을 줄 이기 위해 살 아 있 는 4 만 검색 하면 최고 점 수 를 받 았 다 고 생각한다.
반복 심화 의 우세
교체 심 화 는 가장 좋 은 해 를 찾 는 동시에 아주 작은 추가 시간 비용 만 증가 하고 심지어 비용 을 줄 일 수 있다.만약 에 우리 가 평균 50 가지 선택 을 한다 면 4 층 검색 은 6 층 검색 1 / 2500 분 의 1 의 시간 만 필요 하 다 는 것 을 증명 할 수 있 습 니 다. 그래서 우리 가 추가 로 진행 하 는 얕 은 층 검색 은 모두 결 과 를 찾 지 못 하 더 라 도 무시 할 수 있 는 시간 을 추가 로 증가 시 켰 습 니 다.또 얕 은 층 의 검색 으로 최 적 화 를 찾 을 수 있 으 며 효율 을 극 대화 할 수 있다.
이에 비해 전체 최고 분 해 를 검색 하고 경로 의 길 이 를 비교 하면 시간 복잡 도가 배로 증가한다.
집산 살
교체 가 깊 어 진 후에 우 리 는 통합 적 으로 계산 하여 죽 일 수 있다. 첫 번 째 단 계 는 계산 알고리즘 도 교체 심화 로 개조 하여 매번 계산 하여 찾 는 것 이 가장 좋 은 해 임 을 확보 해 야 한다.

var c = function(board, role, deep) {
  deep = deep || config.checkmateDeep;
  if(deep <= 0) return false;
  var start = new Date();
  debugNodeCount = 0;
  //    
  for(var i=1;i<=deep;i++) {
    var result = max(board, role, i);
    if(result) break; //      
  }
  var time = Math.round(new Date() - start);
  if(result) console.log("    ("+time+"  , "+ debugNodeCount + "   ):" + JSON.stringify(result));
  else {
    //console.log("    ("+time+"  )");
  }
  return result;
}

그리고 우 리 는 검색 한 잎 노드 에서 계산 살 해 를 할 수 있다.잎 노드 가 많 기 때문에 잎 노드 가 계산 살 을 넣 으 면 검색 시간 이 길 어 집 니 다.

var negamax = function(board, deep, alpha, beta, role) {
  var v = evaluate(board);
  count ++;
  if(deep <= 0 || win(board)) {
    return v;
  }

  var best = MIN;
  var points = gen(board, deep);

  for(var i=0;i<points.length;i++) {
    var p = points[i];
    board[p[0]][p[1]] = role;

    //pvs

    /*var pv = - negamax(board, deep-1, -alpha-1, -alpha, R.reverse(role));
    if(math.littleThan(pv, alpha) {
      PVcut ++;
      board[p[0]][p[1]] = R.empty;
      //console.log(pv, alpha);
      return pv;
    }*/

    alpha = Math.max(best, alpha);
    var v = - negamax(board, deep-1, -beta, -alpha, R.reverse(role));
    board[p[0]][p[1]] = R.empty;
    if(math.greatThan(v, best)) {
      best = v;
    }
    if(math.greatOrEqualThan(v, beta)) { //AB   
      ABcut ++;
      return v;
    }

     //  
    if( (deep <= 2 ) && role == R.com && math.littleThan(best, SCORE.FOUR) && math.greatThan(best, SCORE.FOUR * -1)) {
      var mate = checkmate(board, R.com);
      if(mate) {
        return SCORE.FIVE * Math.pow(.8, mate.length);
      }
    }
  }

  return best;
}

상기 코드 에서 우 리 는 AI 자신 에 게 만 계산 살 해 를 했 고 게이머 에 게 계산 살 해 를 하지 않 았 다. 주로 현재 의 계산 살 해 는 효율 이 비교적 낮 기 때문에 게이머 에 게 도 계산 살 해 를 하면 시간 이 배로 증가 할 수 있다.
또한 상기 극 대 극소 치 검색 은 마이너스 극 대 치 검색 으로 바 뀌 었 으 나 원리 적 으로 다 르 지 않 고 코드 만 더욱 간결 하고 통일 되 었 다.
현재 의 계산 살 과 검색 효율 로 4 + 7, 즉 4 층 마이너스 극 대치 검색 에 7 층 계산 살 을 더 하면 기력 이 이전 보다 뚜렷하게 향상 된다.
내부 반복 심화
위 에서 말 한 교체 심 화 는 마이너스 최대 치 검색 에 대해 한 층 의 포장 만 했 을 뿐 사실은 좀 더 깊이 있 을 수 있 습 니 다. 매번 negamax 검색 에 대해 교체 심 화 를 했 습 니 다. 구체 적 인 효 과 는 아직 검증 되 지 않 았 습 니 다. 관심 이 있 으 면 시도 해 보 겠 습 니 다. 나중에 저도 이 방법 을 시도 해 보 겠 습 니 다.