risk game ai agent
1.0.0
위험은 2-6 명의 선수를위한 외교, 갈등 및 정복의 전략 보드 게임입니다. 회전은 다른 플레이어로부터 영토를 포착하려고 시도하는 작품의 군대를 제어하는 플레이어들 사이에서 회전하며, 결과는 주사위 롤에 의해 결정됩니다. 게임의 목표는 보드의 모든 영토를 점유하고 그렇게함으로써 다른 플레이어를 제거하는 것입니다. 각 턴은 두 가지 작업으로 구성됩니다.
이 프로젝트의 목적은 규칙을 변경하여 위험 게임을 구현하고 실제 인간을 포함하여 다른 상대를 대면 할 때 게임을 제대로 플레이 할 수 있고 승리 할 가능성이 높은 인공 지능 에이전트를 설계하는 것이 었습니다. 플레이어 또는 기타 에이전트 플레이어.
이 게임은 Java 프로그래밍 언어를 사용하여 구현됩니다. 턴 제어, 플레이어 요청 조치 수행, 게임 맵 업데이트, 규칙에 따라 모든 일이 발생하는지 확인하는 것이 코드 의이 부분이하는 일입니다. 게임 UI는 또한 .fxml 파일을 통해 설계된 맵을 그리며 플레이어를 게임의 논리에 연결하는 플랫폼입니다.
이 섹션은 게임 위험에 대한 강력한 AI로 이어지는 휴리스틱의 구현 및 평가에 중점을 둡니다.
구현은 Minimax Alpha-Beta 가지 치기 알고리즘을 기반으로합니다. 플레이어는 DFS 알고리즘을 기반으로 예측 트리를 구성합니다.
에이전트가 플레이 할 차례가 될 때마다 나무가 만들어집니다. 트리 노드는 게임의 상태 (해당 상태의 게임지도)이며 각 모서리는 현재 상태에서 공격의 결과 상태에서 맵의 결과 상태에 대한 공격입니다. 공격 행동은 시작 및 대상 영토의 좌표와 공격 군대에서 선택된 부대 수로 구성됩니다. 루트 노드는 플레이어가 이동하는 것을 선택 해야하는지도의 현재 상태입니다. 그러나, 트리는 게임의 끝 상태가 많은 수의 움직임으로 인해 플레이어가 각 상태에서 메모리와 시간 제한이 허용하지 않는 상태에서 가질 수있는 상태까지 예측할 수 없습니다. 따라서 플레이어는 코드에서 정의한 특정 깊이로만 트리를 구성 할 수 있습니다. 또한 에이전트 게임 전략의 특정 부분에 적용되는 몇 가지 단순화가 있으며 다음 섹션에서 모두 설명됩니다. 최상의 결정을 내리기 위해 휴리스틱은 플레이어에게 얼마나 많은 도움이 될 수 있는지를 평가하는 가장 깊은 노드 (트리 잎)에 대해 정의됩니다. Heuristics는이 보고서에 자세히 설명 될 것이라고 말했다. 잎의 값이 결정되면 트리가 Minimax Alpha-Beta 가지 치기로 전달 되며이 잘 알려진 알고리즘은 플레이어가 가질 수있는 최고의 조치를 찾을 수 있습니다.
영토에 단위를 공급하는 것은 까다로운 작업이 될 수 있습니다. 우리는 공격력을 향상시키고 싶을뿐만 아니라 공격을받을 위험이있는 영토에서 충분한 방어력을 갖추고 싶다는 점에서. 적 영토에 인접한 국가에 유닛을 배치하는 것은이 두 목표 사이의 균형을 유지하는 현명한 방법 일 수 있습니다.
드래프트 단순화 :
예측 트리에 가능한 모든 초안 시나리오를 예측하고 포함 시키면 이전에 언급 된 문제에 직면 할 수있는 복잡한 트리가 발생합니다. 따라서 단순화 중 하나는 우리가 항상 최상의 결과를 가져 오는 것으로 입증 된 드래프팅 휴리스틱을 사용하고 상대방이 드래프팅에도 이러한 접근 방식을 만들 것으로 예측한다는 것입니다. 다시 말해, 우리는 가능성이 예측 트리를 형성하고 결정적인 초안 시나리오로 변경함에 따라 제도 결과를 제거합니다.
그렇게하려면 다음 단계를 수행합니다.
드래프트 휴리스틱 :
Step 1:
국가 X에 인접한 적 국가의 모든 단위의 요약을 통해 X에서 BST (Border Security Threat)라고 부르는 조치를 제공합니다.
Step 2:
이 BST를 X에 위치한 단위로 나누면 모든 국경 국가간에 비교할 수있는 BSR (Border Security Vratio)을 제공합니다.
BSR이 높은 국가는 적의 선수가 정복 할 가능성이 더 높습니다. 인접한 적 국가의 적 유닛 수는 국가 자체의 유닛 수보다 상대적으로 높기 때문입니다. 공급 할 BSR이 높은 국가를 선택하면 BSR을 낮추어 방어력이 높아집니다. BSR이 낮은 국가에 유닛을 공급하는 것은 이미 더 나은 방어 입장을 가지고 있음을 의미합니다. 이는 공격적인 힘을 높이고 이들 국가의 성공적인 공격의 가능성을 높일 것입니다.
3 단계 : 3 단계 :
플레이어가 소유 한 국가의 모든 BSR의 합으로 BSR을 나누어 BSR을 정규화하면 누군가가 단위를 정리할 수있는 직접적인 측정을 제공합니다. 정규화 된 경계 보안 비율 (NBSR)은 다음과 같이 계산됩니다.
그것은 국가들 사이에 유닛을 분배 할 수있는 방법의 직접적인 비율을 제공합니다. 이 시점에서 일부 데이터는 관련이 없기 때문에이 비율에 문제가있을 수 있으며 모든 영토에 단위를 추가하고 싶지 않으므로 BSRX 데이터를 정렬하여 2 단계에서 3 단계 사이의 임계 값을 설정합니다. 내림차순 순서 (우리는 방어력을 강력하게 만드는 데 더 집중하고 있음), 데이터를 중간에서 나누고 숫자를 하반기에서 0으로 설정합니다.
Step 4:
4 단계는 더 이상 사용 가능한 장치를 추가 할 수 없을 때까지 계속됩니다.
트리를 덜 복잡하게 만들기 위해 공격 단계에 몇 가지 단순화가 적용되어 더 깊은 수준을 예측할 수 있습니다. 이것은 어떤 공격 시나리오가 전투에서 이길 수있는 기회가 더 높은지 확인하여 트리에만 포함시킬 수 있습니다.
특정 플레이어에게 나무 잎이 얼마나 유익한 지 평가하기 위해; 우리는 나중에 설명 될 휴리스틱을 배우는 동안 가장 좋은 가중치가 발견되는 4 가지 휴리스틱 특징을 정의했습니다. 기능이 서로 가까운 비율로 평가되면 학습 및 할당량이 더 정확하기 때문에 모든 기능은 0에서 1 사이의 결과를 반환합니다.
기능은 다음과 같습니다.
이전 부분의 각 휴리스틱에 무게를 주면 에이전트가 게임에서이기는 데 각각의 중요하고 영향력이 있는지 평가하는 데 도움이됩니다. 이러한 체중을 찾는 과정은 유전 적이며 학습됩니다. 각 유전자는이 네 가지 특징에 대한 4 가지 가중치 세트입니다. 우리는 범위 [0,10]에서 100 세트의 랜덤 가중치를 생성하는 것으로 시작합니다. 그 후 10 번의 토너먼트가 이루어집니다. 각 토너먼트마다 1 차 인구의 10 개의 유전자가 무작위로 선택됩니다. 가능한 모든 유전자 쌍이 서로에 대항하여 재생되며 각 토너먼트에서 각 게임의 결과가 문서화됩니다. 피트니스 기능은 각 유전자에 대한 (승리 / 게임 수)로 정의됩니다. 각 토너먼트의 3 개의 최고 유전자 (피트니스 기능 기반)가 선택되므로 이제 30 개의 상위 선택된 유전자가 있습니다. 이 중 우리는 12 개의 무작위 쌍을 선택하고 각 쌍에 대해 유전자 쌍의 평균 중량을 계산하여 새로운 유전자를 생성하는 크로스 오버를 수행합니다. 따라서 우리는 이제이 크로스 오버에서 12 개의 새로운 유전자가 있습니다. 다른 한편으로, 우리가 가진 30 개의 유전자 내에서 3 개의 유전자가 무작위로 선택되고 각각의 임의 중량을 다른 임의의 무작위로 변경하여 [0,10] [0,10]. 이 모든 후에 우리는 이제 1 차 인구에 넣는 15 개의 새로운 유전자를 가지고 있으며, 우리가 이미 가지고있는 가장 좋은 15 가지 유전자를 대체합니다. 이 시점에서 2 세대 유전자가 생성됩니다. 이 과정은 4 세대 유전자가 생성 될 때까지 계속 반복 될 것입니다. 그 인구의 최고 유전자는 에이전트가 사용할 수있는 휴리스틱의 특징에 대한 최고의 가중치로 선정 될 것입니다.
