16 진수 게임에 최소 최대 알고리즘을 적용하는 방법

Question

분기 인수가 너무 높기 때문에 최소 최대 알고리즘을 사용하여 16 진수 게임에 효율적인 알고리즘을 설계하는 방법. 일반적인 tic tac toe 게임은 간단한 min max 알고리즘을 사용하여 만들 수 있지만이 경우 11 * 11 보드 게임의 경우 121 조합이 있으므로 조합 수를 줄이는 방법이 많은 조합을 최소화하는 방법

Answer 1

게임을위한 움직임의 나무는 tic-tac-toe와 같은 단순한 물건에 대해서만 완전히 탐색 될 수 있습니다. 체스와 같은 다른 게임은 너무 깊어서 모든 동작에서 너무 많은 옵션을 갖습니다 (큰 분기 요인).

매우 제한적인 수준에서이 제한 사항을 해결할 수있는 방법이 있습니다.

가장 중요한 점은 중간 게임 위치에 값을 할당하는 경험적 방법이 필요하다는 것입니다. 이렇게하면 게임 종료까지의 모든 동작을 분석 할 수 없더라도 minimax를 적용 할 수 있습니다. 이러한 추론은 매우 간단 할 수 있습니다. 예를 들어, 체스에서 조각에게 가치 (폰 1, 기사 3 등)를 부여하고 간단히 합칠 수 있습니다. 게시판의 위치를 ​​고려하여 좀 더 복잡하게 만들 수도 있지만 여기에는 실적과 절충안이 있습니다. 이것은 많은 인공 지능 시스템의 기초입니다.

고전적인 향상을 alpha-beta pruning이라고합니다. 이는 이동 트리의 노드를 규칙적인 방식으로 평가하여 이미 다른 노드보다 나쁘다고 보증 된 분기를 생략하여 효율성을 향상시키는 데 기반을 둡니다. 예를 들어, 한 플레이어가 승리하는 운동을 할 수있는 지점을 고려해보십시오.이 지점에서이 운동에 대한 대안은 중요하지 않습니다. 왜냐하면이 게임은 이런 식으로 진행되는 경우 항상 승리하는 운동을 강요 할 것이기 때문입니다.

다른 알고리즘은 우리가 움직임의 나무를 탐색하는 방식을 변경합니다. Monte-Carlo tree search이 그 예입니다. 여기서 핵심 아이디어는 노드를 평가하고 조정 된 방식으로 트리를 탐색하는 것입니다 (이전과는 반대로 가능한 한 트리를 먼저 탐색 한 다음 리프를 평가합니다). 여기에는 탐사 착취 균형이 있습니다 (더 유망한 직책을 개발하고 싶은지 또는 새로운, 아마도 실망스러운 움직임을 탐구하는 것을 선호해야하는지 결정해야합니다).