예상대로 봇을 이길 수있는 알고리즘

Question

이 게임에는 10x10 보드와 1에서 9까지의 값을 가진 여러 가지 상품이 있습니다. 가장 간단한 상금을 쫓는 간단한 봇과 몇 가지 간단한 봇이 있습니다. 항상 가장 많은 점수를 지닌 상금을 얻습니다. 봇과 상품은 보드에 무작위로 배치됩니다. 작업은 항상 가장 많은 수의 포인트를 모으고 게임에서이기는 또 다른 간단한 AI를 만드는 것입니다.

이 새로운 인공 지능이 항상 게임에서이기도록 할 수있는 상금 포인트와 경품 거리를 선택하는 방법은 무엇입니까? 나는 가까운 상금을 선호한다고 생각했지만 가장 가까운 상금보다 2 크다면 큰 상금으로 가고, 그러나 항상 그렇지는 않습니다.

봇은 봇이 어디에 있는지 알지 못합니다. 한 봇이 한 상금을 위해 8 칸을 움직이면 다른상은 8 칸을 이동하고 그 시간 동안 여러 상을 수거 할 수 있습니다. 모든 봇은 즉시 움직이며 대각선으로 이동할 수 있습니다. 보드에 더 이상 상품이 없으면 게임이 종료됩니다.

Answer 1

승리를 보장 할 방법이 없습니다. 봇/상품이 무작위로 배치되는 경우 다른 봇보다 먼저 상품을 얻으려는 무작위 배치가 반드시 있어야합니다.

다른 로봇의 정확한 동작을 알고 있기 때문에 주어진 보드에서 앞으로 발생할 모든 움직임을 모델링 할 수 있습니다. 가능한 모든 움직임을 나무와 보드 상태로 나열한 다음 잎을보고 승리 점수를주는 것을 찾으십시오. 즉, 각 분기는 사용자가 이동 한 것이고, 노드는 다른 로봇이 이동하는 것을 포함하여 보드 상태를 나타냅니다. 또한 이것은 2 진 트리가 아니며, 각 노드는 그 방향으로 이동할 수있는 방향에 따라 분기합니다. 실제로 하나의 실제 이동을하기 전에이 트리를 완전히 빌드하므로, 본질적으로 최적 경로를 선택하면 예측 된 결과를 얻게됩니다. 이것은 다른 봇들이 예측 가능한 방식으로 움직이기 때문에 가능합니다.

또한 이동하면서 다른 봇이 예상대로 움직이는지를 디버깅 기능처럼 추가 할 수 있습니다. 시스템 작동 방식에 따라 모든 사람이 동시에 이동하는지 또는 한 번에 하나씩 이동할지에 따라 이동을 결정하기 전에 이동을 볼 수 있습니다. 어느 쪽이든 그것을 할 수 있습니다, 당신은 단지 그들이 어떻게 움직이는 당신의 모델이 정확한지 확인해야합니다.

점수가 더 높지만 다른 봇 중 하나가 다른 봇을 지배하기 때문에 다른 퍽이 남을 수 있습니다. 나는. (you : 11, a : 10, b : 9) 대

아마도 가장 성공할 가능성이 높은 경로는 다른 예를 들어 봇 (bot)은 가장 가까운 상을 당신에게 더 가까이 붙잡을 때 탐욕스러운 봇을 향해 느슨한 움직임을 유발합니다. 그리고 그렇게하기에 충분한 움직임이 있다면 길을 잃을 때도 상을 줄 것입니다. 트리를 생성하고 최적의 일련의 동작을 찾을 때 암시 적으로 발생하기 때문에이 동작을 코딩 할 필요가 없습니다.