Hi guys. I am solving a very interesting problem from this year’s IeeeXtreme contest.
Short problem description: You have a unweighted bidirectional graph of at most 100 nodes. You place your king on a node, and the computer places their king on a node. You move to one adjacent node, then the computer moves to one adjacent node in an alternating fashion.
Your goal is to minimize the number of moves to capture him and his goal is to maximize the number of moves you need to capture him. It is guaranteed that you always have a winning strategy.
The computer plays ‘smart’ i.e. thinks ahead. I managed to get a score of 80/100. I believe my code always finds a solution but i fail 4 tests because of “exceeded number of moves” meaning that i was not fast enough to catch him.
I am doing a min-max (with alpha-beta pruning) approach. My heuristic is a formula like this:
1000*(100 - distance(black,white) + 100*(100-stepsTaken).
By testing manually i noticed that i can get 2 more tests to pass (90/100 score) if i get a better starting position. My current starting position is the one that has the least total sum of distances to all other nodes.
Please help guys, this problem really frustrates me, i tried everything i could think of :).
Here is a link to the problem and the environment: https://csacademy.com/ieeextreme-practice/task/cd05154d910e28e73ca3930e9a5103f5/statement/
Thanks in advance!!