CODEWITHSUNDEEP
algorithmartificial-intelligence
fotg
fotg

Reputation: 639

Algorithm to beat bots moving towards prizes predictably

For this game, there is a 10x10 board and a few different prizes with values from 1 to 9, there are a few simple bots playing where one always goes after the closest prize, and another always goes for the prize with the greatest number of points assigned to it. Bots and prizes are placed randomly on the board. The task is to create another simple AI which always collects the highest number of points total and wins the game.

How would I go about picking between prize points and prize distance which would allow this new AI to always win the game? I was thinking I would favor closer prizes, but go towards a larger prize if it is 2 larger than the closest one, however this doesn't always win.

The bots do not know where the bots are and if one bot moves 8 spaces for one prize another can move 8 spaces and collect multiple prizes during that time. All the bots move at once and can move diagonally. The game ends once there is no more prizes on the board.

Upvotes: 0

Views: 307

Answers (1)

AaronLS
AaronLS

Reputation: 38392

There is no way to guarantee a win. If bots/prizes are placed randomly, there are surely random placements that will put you too far away from prizes before the other bots get them.

Since you know the exact behavior of the other bots, you can model all future moves they will make for a given board. You can then enumerate all possible moves as a tree, and board states, then look at the leaves and find the one that gives you a winning score. In other words, each branch is a move you make, and the node represents the board state including the move that the other bots will make. Also, this won't be a binary tree, each node will branch based on the directions you could move that turn. You will completely build this tree before you make a single actual move, so that essentially you will have the outcome of the game predicted once you choose the optimum path. This is possible only because the other bots move in a predictable manner.

Also as you move, you can add checks to ensure the other bots are moving as you predicted, just as a debugging feature. Depending on how the system operates, they may see your move before they decide their move, depending on if everyone moves simultaneously, or one at a time. Either way it can be done, you just have to make sure your model of how they move is accurate.

Note that there might be other leaves where you have a larger score but lose because one of the other bots dominated the other. I.e. (you:12, a:1, b:17) vs. (you:11, a:10, b:9)

The paths that will probably succeed the most are the ones that exploit the behavior of the other bots, for example, grabbing the highest prize when it is closer to you, causing the greedy bot to loose moves going towards it. And also sidetracking for prizes on the way if you have enough moves to do so. You won't have to code for this behavior though, because when you create the tree and find the optimum series of moves, you it will occur implicitly.

Upvotes: 3

Related Questions