게임에 대한 좋은 평가 기능을 만드는 방법은 무엇입니까?

https://stackoverflow.com/questions/1291377

18-09-2019
|

문제

나는 때때로 보드 게임 변형을 플레이하기 위해 프로그램을 작성합니다. 기본 전략은 표준 알파 베타 가지 치기 또는 유사한 검색으로, 때로는 엔드 게임이나 오프닝에 대한 일반적인 접근 방식으로 보강됩니다. 나는 주로 체스 변형을 가지고 놀았으므로 평가 기능을 선택할 때 기본 체스 평가 기능을 사용합니다.

그러나 이제는 완전히 새로운 보드 게임을하기위한 프로그램을 작성하고 있습니다. 양호하거나 괜찮은 평가 기능을 어떻게 선택합니까?

주요 과제는 동일한 작품이 항상 보드 위에 있다는 것입니다. 따라서 일반적인 재료 기능이 위치에 따라 변경되지 않으며 게임이 천 번 미만 이하로 재생되었으므로 인간이 반드시 충분히 연주 할 필요는 없습니다. 아직 통찰력을 제공하지 않았습니다. (PS. 나는 MOGO 접근법을 고려했지만 임의의 게임은 종료되지 않을 것입니다.)

게임 세부 사항:이 게임은 10 x-10 보드에서 측면 당 6 개가 고정 된 6 개 보드에서 재생됩니다. 조각은 특정 움직임 규칙을 가지고 있으며 특정 방식으로 상호 작용하지만 조각은 아무것도 캡처하지 않습니다. 게임의 목표는 보드에 특정 특별 광장에 충분한 작품을 갖는 것입니다. 컴퓨터 프로그램의 목표는 현재 인간 플레이어보다 경쟁력있는 플레이어를 제공하는 것입니다.

해결책

이동성 (가능한 이동의#)과 같은 평가 기능에 대한 후보자를 찾은 다음 각 메트릭에 대한 최적의 가중치를 찾으십시오. 유전자 알고리즘은 평가 기능에서 가중치를 최적화하는 데 꽤 잘 작동하는 것 같습니다.

무작위 무게로 모집단을 만들고 깊이와 회전으로 서로 싸우고 패자를 승자의 임의의 조합으로 교체하고 셔플을 반복하고 모든 세대 후에 인구 평균을 인쇄합니다. 결과에 만족할 때까지 또는 일부 메트릭의 범위를 조정하고 다시 시도 할 필요가있을 때까지 실행하십시오. 하나의 메트릭의 최적 값이 초기 범위를 벗어날 수 있습니다.

늦은 편집 : 당시에 알지 못하는 더 받아 들여지고 연구하고 이해 된 접근 방식은 "차별적 진화"라고 불리는 것입니다. 자손은 평균에 대한 조기 수렴 문제를 피하는 방식으로 2 대신 3 명의 부모로부터 창출됩니다.

다른 팁

나는 몇 가지 기본부터 시작하여 나중에 더 어려운 물건으로 이동할 것입니다.

기본 에이전트 및 테스트 프레임 워크

어떤 접근 방식에 관계없이, 당신은 정말로 단순하고 바보로 시작해야합니다. 멍청한 에이전트의 가장 좋은 방법은 임의의 에이전트입니다 (가능한 모든 움직임을 생성하고 무작위로 선택). 이것은 다른 모든 에이전트를 비교하는 출발점 역할을합니다. 비교를 위해서는 강력한 프레임 워크가 필요합니다. 다양한 에이전트를 취하고, 그들 사이에서 몇 가지 게임을 플레이하고 성능의 매트릭스를 반환 할 수 있습니다. 결과에 따라 각 에이전트의 체력을 계산합니다. 예를 들어 귀하의 기능 tournament(agent1, agent2, agent3, 500) 각 에이전트 쌍 (첫 번째/초 재생) 사이에서 500 게임을 플레이하고 다음과 같은 것을 반환합니다.

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

예를 들어, 나는 승리를 위해 2 점을 사용하고, 드로우 스코어링 기능을 위해 1 점을 사용하고, 결국 체력을 찾기 위해 모든 것을 요약합니다. 이 테이블은 즉시 그 말을합니다 agent3 최고입니다 agent1 실제로 다르지 않습니다 agent2.

따라서이 두 가지 중요한 사항이 설정되면 평가 기능을 실험 할 준비가되었습니다.

기능 선택부터 시작하겠습니다

우선 당신은 만들어야합니다 not a terrible 평가 기능. 이것은이 기능이 세 가지 중요한 측면 (Win/Draw/Loss)을 올바르게 식별해야한다는 것을 의미합니다. 이것은 분명하게 들리지만, 제작자 가이 세 가지 측면을 올바르게 설정할 수 없었던 상당한 양의 봇을 보았습니다.
그런 다음 인간의 독창성을 사용하여 게임 상태의 일부 기능을 찾습니다. 가장 먼저해야 할 일은 게임 전문가와 대화하고 그가 어떻게 그 직책에 접근하는지 묻는 것입니다.
전문가가 없거나 5 분 전에 게임의 규칙을 만든 경우 인간의 패턴 검색 능력을 과소 평가하지 마십시오. 두 번의 게임을 한 후에도 똑똑한 사람은 자신이 어떻게 연주해야했는지 아이디어를 줄 수 있습니다 (아이디어를 구현할 수 있다는 의미는 아닙니다). 이 아이디어를 기능으로 사용하십시오.
이 시점에서 이러한 기능이 게임에 어떤 영향을 미치는지 알 필요는 없습니다. 특징의 예 : 조각의 가치, 조각 이동성, 중요한 위치 제어, 안전, 가능한 움직임 수, 마감과의 친밀감.
이러한 기능을 코딩하고 별도로 사용하여 가장 잘 작동하는 것을 확인한 후 (자체적으로 합리적으로 수행하지 않는 기능을 버리지 말고 다른 사람과 함께 도움이 될 수 있음) 조합을 실험 할 준비가되었습니다.

간단한 기능을 결합하고 가중치로하여 더 나은 평가를 구축합니다. 몇 가지 표준 접근 방식이 있습니다.

기능의 다양한 조합을 기반으로 Uber 기능을 만듭니다. 선형 일 수 있습니다 eval = f_1 * a_1 + ... f_n * a_n (f_i 특징, a_i 계수), 그러나 그것은 무엇이든 될 수 있습니다. 그런 다음이 평가 기능에 대해 절대적으로 임의의 가중치를 가진 많은 에이전트를 인스턴스화하고 유전자 알고리즘을 사용하여 서로를 다시 재생합니다. 테스트 프레임 워크를 사용하여 결과를 비교하고, 몇 명의 명확한 패자를 버리고, 몇 명의 우승자를 돌연변이합니다. 동일한 프로세스를 계속하십시오. (이것은 대략적인 개요입니다. GA에 대해 자세히 알아보십시오)
신경망에서 후퇴 아이디어를 사용하여 게임 끝에서 오류를 전파하여 네트워크의 가중치를 업데이트하십시오. 당신은 그것이 어떻게 끝났는지 더 읽을 수 있습니다 Backgammon (나는 비슷한 것을 쓰지 않았으므로 부족한 것에 대해 죄송합니다).

평가 기능없이 작업 할 수 있습니다! 이것은 Minimax/Alpha-Beta에 대해서만 들었던 사람에게는 미쳤지 만 평가를 전혀 필요없는 방법이 있습니다. 그들 중 하나가 호출됩니다 몬테 카를로 트리 검색 그리고 이름의 Monte Carlo가 많은 임의를 사용한다고 제안했듯이 (무작위가 아니어야합니다. 이전에 좋은 에이전트를 사용할 수 있습니다) 게임은 트리를 생성합니다. 이것은 그 자체로 큰 주제이므로, 나는 당신에게 정말로 높은 수준의 설명을 줄 것입니다. 당신은 뿌리로 시작하고, 당신의 프론티어를 만들고, 당신은 확장하려고합니다. 무언가를 확장하면 무작위로 잎으로갑니다. 잎에서 결과를 얻으면 결과를 역전시킵니다. 이 작업을 여러 번 수행하고 현재 국경의 각 자녀에 대한 통계를 수집하십시오. 최고의 것을 선택하십시오. 탐사와 착취 사이의 균형을 잡는 방법과 관련된 중요한 이론이 있으며, 읽을 수있는 좋은 것은 UCT입니다 (상단 신뢰 바운드 알고리즘).

강화 학습과 같은 감독 된 기계 학습 알고리즘을 살펴 보겠습니다. 체크 아웃 보드 게임의 강화 학습. 나는 그것이 당신에게 약간의 좋은 지시를 줄 것이라고 생각합니다.

또한 확인하십시오 강화 학습을 기반으로 한 게임 Othello의 전략 획득 (PDF 링크) 게임의 규칙이 주어지면 좋은 "지불 기능"을 배울 수 있습니다. 이것은 밀접하게 관련되어 있습니다 TD-Gammon ...

훈련 중에 신경망 자체는 양측의 움직임을 선택하는 데 사용됩니다. 다소 놀라운 발견은 원시 보드 인코딩을 사용하는 제로 초기 지식 실험에서도 상당한 양의 학습이 실제로 이루어 졌다는 것입니다.

아직 게임을 이해하지 못한다면 괜찮은 평가 기능을 얻을 수있는 방법이 없습니다. 재료 수를 가진 표준 알파 베타는 체스 또는 그 변형에 대해 양호하거나 괜찮다는 것을 말하지 마십시오 (패자의 체스는 예외 일 수 있음).

피드백 또는 유사한 기계 학습 알고리즘으로 신경망을 시험해 볼 수 있지만 일반적으로 수많은 훈련이있을 때까지 빨라집니다.이 경우에는 사용할 수 없습니다. 그리고 심지어 그들이 빨지 않으면, 당신은 그들로부터 지식을 얻을 수 없습니다.

나는 게임을 최선을 다해 게임을 이해할 수있는 방법이 없다고 생각합니다. 우선, 미지의 것을 평가 함수에서 무작위로 남겨 두십시오 (또는 미지의가 더 잘 알려질 때까지 그림에서 벗어나십시오).

물론 게임에 대한 더 많은 정보를 공유하려면 커뮤니티로부터 더 나은 아이디어를 얻을 수 있습니다.

내가 이해할 때, 당신은 최소 맥스 트리의 잎에서 사용하기에 좋은 정적 평가 기능을 원합니다. 그렇다면이 정적 평가 기능의 목적은 컴퓨터 플레이어에게 보드가 얼마나 좋은지에 대한 등급을 제공하는 것임을 기억하는 것이 가장 좋습니다. 그렇습니다

f (보드 1)> f (보드 2)

그런 다음 Board1이 Board2보다 컴퓨터에 대해 더 낫다는 것이 사실이어야합니다. 물론 모든 보드에 정적 기능이 완전히 정확하지 않습니다.

그래서 당신은 "게임의 목표는 보드의 특정 특별 광장에 당신의 조각을 충분히 갖는 것입니다"라고 말합니다. 특별한 사각형. 그런 다음 더 세밀하게 될 수 있습니다.

게임의 세부 사항을 알지 못하고 더 나은 추측을 할 수 없습니다. 게임 규칙을 준다면 StackoverFlow 사용자가 그러한 기능에 대한 독창적 인 아이디어를 제공 할 수 있다고 확신합니다.

다양한 기계 학습 방법을 사용하여 평가 함수 (GnubackGammon과 같은 프로젝트에 사용 된 TD- 학습, 그러한 예입니다)를 제시 할 수 있지만 결과는 게임 자체에 확실히 의존합니다. Backgammon의 경우 게임의 확률 론적 특성 (롤링 주사위)은 학습자가 원하지 않을 수도있는 영역을 탐험하도록 강요하기 때문에 정말 잘 작동합니다. 그러한 중요한 구성 요소가 없으면 아마도 다른 사람들에게는 좋은 평가 기능이 될 것입니다.

물질적 차이가 적용되지 않을 수 있으므로 이동성의 개념이 중요합니까? 즉, 가능한 몇 개의 가능한 움직임이 있습니까? 보드의 특정 영역을 통제하는 것이 일반적으로 그렇지 않은 것보다 낫습니까? 게임을하는 사람들과 대화하여 단서를 찾으십시오.

최대한 평가 기능을 제공하는 것이 바람직하지만 검색 알고리즘을 조정하여 검색 할 수 있습니다. 깊이 가능한 한. 의료용 평가 기능이있는 깊은 검색자가 좋은 평가 기능을 통해 얕은 검색을 능가 할 수 있기 때문에 때때로 이것은 실제로 더 관심이 있습니다. 그것은 모두 도메인에 달려 있습니다. (Gnubackgammon은 1 폴리 검색으로 전문가 게임을합니다.

검색의 품질을 향상시키는 데 사용할 수있는 다른 기술이 있습니다. 가장 중요한 것은 전송 테이블을 캐시 검색 결과에 사운드 전향 적 이지는 가지를 갖도록하는 것입니다.

나는 바라 보는 것이 좋습니다 이 슬라이드.

당신은 또한 당신의 선택에주의를 기울여야합니다. 알고리즘이 실제 값과 알려진 관계가없는 경우 표준 AI 기능이 제대로 작동하지 않습니다. 유효하려면 평가 함수 또는 휴리스틱은 실제 가치와 일관되거나 일관되게 동일해야합니다. 그렇지 않으면 결정을 이상한 방식으로 안내 할 것입니다 (표준 포인트가 괜찮다고 생각하더라도 체스에 대해 논쟁 할 수 있습니다. ).

내가 일반적으로하는 일은 무엇이 가능하고 필요한 것이 무엇인지 알아내는 것입니다. Sokoban과 같은 일부 게임의 경우 현재 위치에서 목표 위치로 하나의 상자 (분리)를 얻는 데 필요한 최소 상자 동작을 사용했습니다. 이것은 필요한 움직임의 수에 대한 정확한 답이 아니지만, 절대로 과대 평가할 수 없으며 전체 보드에 미리 계산 될 수 있기 때문에 꽤 좋은 휴리스틱이라고 생각합니다. 보드의 점수를 합산하면 각 현재 상자 위치에 대한 값의 합입니다.

Evolve Pack Hunting and Pack Defense에 쓴 인공 생활 시뮬레이션에서, 내가 사용한 스코어링 시스템은 진화를 안내하고 가지 치기를 수행하지 않는 것이 었습니다. 나는 각 생물에게 태어나기위한 한 지점을 주었다. 그들이 그들의 삶에서 소비 한 각 에너지 지점에 대해, 나는 그들에게 하나의 추가 요점을 주었다. 그런 다음 세대의 포인트의 합을 사용하여 각각의 재생산 가능성을 결정했습니다. 제 경우에는 단순히 그들이 얻은 세대의 총점의 비율을 사용했습니다. 회피에 큰 생물을 진화시키고 싶었다면, 나는 그들을 먹는 포인트를 얻는 데 득점했을 것입니다.

또한 기능이 목표를 달성하기가 어렵지 않다는 점도주의해야합니다. 무언가를 발전 시키려고한다면 솔루션 공간에 괜찮은 경사가 있는지 확인하려고합니다. 진화를 방향으로 안내하고 싶다.

당신의 게임에 대해 더 많이 알지 못하면 나는 당신에게 함수를 구축하는 방법을 말하기가 어려울 것입니다. 승리 또는 손실을 나타내는 분명한 가치가 있습니까? 격차를 해소하는 데 최소 비용을 추정하는 방법이 있습니까?

더 많은 정보를 제공한다면 더 많은 통찰력을 제공하고 기꺼이 노력할 것입니다. 이 주제에 관한 훌륭한 책들도 많이 있습니다.

야곱

괜찮은 평가 기능이 존재한다는 것은 사실이 아니라는 점을 명심하십시오. 이 진술에 대해서는 평가 함수가 복잡성이 낮아야한다고 가정합니다 (P).

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow