실시간으로 확률 적으로 표현 된 2D 그리드에서 최적으로 득점하는 움직임을 결정하십시오.

Question

저는 이것이 어디에 가장 잘 맞는지 모르므로 StackOverflow, cstheory.stackexchange.com 및 math.stackexchange.com에 게시하고 있습니다. 나는 그것이 좋으면 좋겠다.

필자는 2D 셀을 가지고 있는데, 각 셀에는지도에 따라 각 단위 (10 ~ 50)의 확률 (0 ~ 1)이 각 셀에 포함되어있는 크기 (10X10 ~ 20X20, 반드시 정사각형이어야합니다.) 그 위치에 있습니다.

두 가지 주요 유형이 있습니다. 동작이 알고리즘에 의해 제어되는 큰 단위가 있습니다. 당신이 나를 돕기를 원할 것입니다. 이동하거나 부울 상태 만 가질 수있는 작은 단위가 있습니다 큰 단위의 도움으로 바뀌었다. 모든 유닛은 팀에 속하지만 모든 큰 유닛은 작은 유닛을 이동할 수 있습니다. 매치는 작은 단위의 위치와 상태에 따라 채점됩니다. 각 유닛은 자체 좌표를 알고 있습니다.

포인트는 인접한 셀의 수에 대해 보너스가 주어지는 지정된 셀 수에 대해 작은 단위를 갖는 것으로 주어집니다. 노트 인접성은 반드시 인접 셀 좌표를 의미하지 않으며지도 당 결정됩니다.

성능상의 이유로 최소로 호출해야하지만, 이미 경로 지정 시스템이있어 문제가되지 않으며 이동 시간을 계산하지도 않습니다.

내 의도는 계획 시스템이 원하는 상태/동작 시퀀스를 출력하도록하는 것입니다. 예를 들어, (9,4)에 43도 각도로 놓고 12도에서 (12,4)가되도록하고 작은 단위를 활성화하십시오.

~ 5 개의 경쟁 메인 유닛 각각에 대해 최적의 동작을 결정하여 시간이 다되었을 때 팀의 마무리 위치를 최적화하려고합니다. 유닛에는 확률 적 위치를 채우는 시뮬레이트 된 센서가 있으므로 정보를 수집하는 것이 유효한 방법입니다.

이상적으로 알고리즘은 앞으로 몇 가지 움직임을 보일 것이며 특정 이동이 다음 이동을 수행하기에 좋은 위치에 있는지 여부와 같은 것을 고려해야합니다.이 위치의 "장점"은 단지 경로 비용.

여기서 성능이 상당히 중요하며 성능 향상을 위해 솔루션 품질을 기꺼이 활용할 수 있습니다.

• 가장 완벽한 솔루션은 철저한 검색 겠지만, 성능이 배제 : 여기

  지금까지 내 생각이다.

• 각 합리적으로 가능한 현재 상태의 중요도를 계산해야하기 때문에 어떤 정보가 중요한지 확인할 수 있습니다.

• 평균 현대적인 PC의 단위당 실행 시간은 가능한 경우 < = 25ms가되어야합니다 - 돌로 설정되지 않은 경우 - 이것은 C++이므로 매우 빠릅니다.

• 체스 알고리즘을 적용하는 것이 좋은 방법 일 수 있습니다.

• 나는 이것에 대해 나쁘다. 나는 인터넷에 질문해야한다.

• 가장 좋은 방법은 거의 확실한 추정 일 수 있습니다.

• 움직임이 10 % 확률로 다른 것보다 20 배 많은 점수를 얻는다면, 위험이 따릅니다. 다른 이동이 좋은 마무리 위치를 보장하지 않고 시간이 거의 다 떨어지지 않는 한.

• 제 질문은 다소 장황합니다.

• 나는 지금까지 더 많은 생각을 했음에 틀림없지 만, 나는 내 삶에있어 그들이 무엇인지 생각할 수 없다.

• 마지막 점은 운입니다.

• 아직도이 글을 읽는다면 나는 당신과 결혼 할 의향이 있습니다.

사람이에 대한 완벽한 솔루션을 제공 할 수 있다면 그것이 환상적 일 것 동안

는, 그러나 나는 지금까지 내가 할 수있는 모든 도움/힌트를 받아 절대적으로 기꺼이 내게 가장 먼을 가져옵니다 대답을 받아 들일 것입니다 그렇지 않은가. 저는 알고리즘보다는 코드에 관심이 있습니다. 지금은 큰 여자이기 때문에 스스로 처리 할 수 ​​있습니다.

Answer 1

솔직히 말해서이 작업을 수행하는 가장 빠른 방법은 간단하게 시작하는 것입니다.

기본 게임 이론부터 시작하는 것이 좋습니다 (특히 game trees). 그러한 게임을 할 수있는 플레이어를 디자인하여 일정한 수의 움직임을 미리 살펴보십시오. 그런 다음 A * ("스타 알고리즘")을 구현하여 더 빨리 수행하십시오. 휴리스틱 스를 읽고 향후 트리 전체를 해결하지 않고 국가의 가치를 추측 해보십시오.

그런 다음 원하는 게임을 크게 단순화 한 버전을 시도해보십시오 (예 : 두 팀, 하나의 큰 유닛, 4 개의 작은 유닛, 완벽한 정보). 거기에서부터 한 번에 조금씩 복잡성을 추가 할 수 있습니다. 이 단계들 중 어느 한 단계에 빠지면 기꺼이 도와 드리겠습니다 (또는 적어도 시도하십시오).

Answer 2

큰 상태 공간에 문제가있는 것 같습니다. 최소한 처음에는 - 특히 그렇게 간단하지는 않습니다. 나는 몬테카를로 트리 검색 (http://en.wikipedia.org/wiki/Monte-Carlo_tree_search)과 근사 다이내믹 프로그래밍 (http://adp.princeton.edu/Papers/Powell-NRLWhat%20you%20should%20know%20about%20approximate%20dynamic%20programming.pdf)을 반복적으로 시뮬레이션하는 두 가지 접근 방법을 보았다.

몬테카를로 트리 검색에는 게임 프로그램을 만드는 데 사용 된 트랙 레코드가 있습니다.