MiniHack January 2018
minihack.png
The Oxford Interscholastic Coding Competition


Getting Started

If you haven't already done so you will need to create an aigaming account, go to registration page and register.

Once you have signed up for an account the simplest way to start coding is to use our online code editor (OCE).

As soon as you visit the OCE the default game loaded will be today's hack challenge. This will mean there will be some default code loaded into the editor that will be ready to run however this code will play a very poor strategy. You can jump in an play straight away by pressing the 'RUN' button in the top right further help on using the OCE can be found here.

All code is written in Python. If your new to Python there are many help guides on the net including:

For those of you wanting to use your own development environment you can download our demo client:


Objectives

The challenge for this hack is to create bot to solve the well know Travelling Salesman problem. We've upgraded the salesman to a drone but the principle problem is the same where the drone has to visit a number of cities in the shortest possible route. You must play against our housebot-competition and use game style 407.

At the start of the game you are given a random set of points on our 100 by 100 grid map these represent the cities. Both players are given the same city locations.

tsd_example_game1.png

Your home can be any one of these cities but you must visit every city and return home. The drone always flies in a straight line between the cities but must remain in the confines of the map. The winner is the person who can find the shortest path between the cities. When the game is in play your route will be plotted onto the map. If your route is coloured yellow you are currently winning the game otherwise it will be shown in red. In the event both you and your opponent calculate the same distance, then the winner will be the person who gets to that solution first. You cannot submit a route which is the same as your opponents current best solution, however you could make modifications to it and submit the revised solution.

tsd_example_game2.png

The problem gets exponentially more difficult the more cities you add and you only have a maximum of 20 seconds to complete the game.


Mini Hack Winning Criteria

You must pitch your bot against our best house bot playing a game where there are 80 cities on the map. To do this you will need to select 'house-competition' and then select game style '407 | 80 Cities | Stake 0 | Prize 0'

competition_bot_select.png

Your bot will be judged against the housebot-competition by comparing your best route against their best route around the cities. Your performance is calculated by taking the house bots best route total distance around the cities and subtracting your best route total distance around the cities. This will then become a rolling average so the lower the score the better and negative number is positively great as you will have beaten the housebot.

For example:

Game No Your Best Route Total Distance Housebot Best Route Total Distance Difference
1 1000 1010 -10
2 990 1020 -30
3 530 540 -10
4 1000 1000 0
5 600 580 +20
6 800 800 0

Your current average net distance performance over these 6 games would be -5.

You will need to play a minimum of 50 games against the housebot-competition to qualify as the 'average net difference' will be calculated over a number of games to eliminate any luck in your strategy.

You can keep track of your performance on the night of the hack by following this Results Page link

Important If for some reason you or the housebot do not submit a valid route or the game times out this result will NOT be recorded on the results page.

Biggest Difference Bonus Competition
There is also a prize offered to the bot that beats the house bot by the biggest margin in a one off game. This is shown on the leader board in the biggest difference column and will also highlight the current winning row in gold as it may well not be in the top spot. So even if your bot is not consistently the best but occasionally crushes the house bot you will still have a chance of winning.


Programmers Reference

Understanding The Gamestate
Your calculateMove() function will be passed the current state of the game, the 'gameState'. The gameState is a python dictionary containing the following keys:

  • CityCoords - A list of the city co-ordinates as positioned on a 100 by 100 grid. No two cities will share the same spot.
  • IsLeading - A Boolean value indicating whether you are winning.
  • MyBestDistance - A floating point value of the total distance of your best route submitted so far.
  • OppBestDistance - A floating point value of the total distance of your opponents best route submitted so far.
  • MyBestSolution - The list of city indexes for your current best route eg [2, 6, 3, 8, 9, 5, 4, 7, 1, 0]
  • OppBestSolution - The list of city indexes for your opponents best route eg [2, 6, 3, 8, 9, 5, 4, 7, 1, 0]
  • EndTime - The epoch time, in milliseconds at which this game will end.
  • GameLength - The total game length in milliseconds
  • DealsTotal - Not used in this game. So will always be set to 1.
  • MyScore - Not used in this game. So will always be set to 0.
  • OppScore - Not used in this game. So will always be set to 0.
  • GameStatus - A string that will have value "RUNNING" if the game is in progress or a reason the game has ended otherwise.
  • IsMover - A boolean that represents whether you can submit a route. Always set to True as long as game is running.
  • GameId - An integer representing the unique game id for the current game.
  • OpponentId - A string containing the name of your opponent.

Understanding The Map
The list contained in CityCoords are the x and y co-ordinates of all the cities in the game.
For example ([84, 87], [58, 97], [69, 17], [69, 83], [71, 36], [19, 76], [19, 22], [15, 51], [10, 64], [7, 2]) would represent a 10 city game. The top left of the board is position [0, 0].
When the game is in play these will be plotted onto a green map with each city represented as a black dot.

Submitting a route
To submit a route you need to return a list of city indexes in calculateMove. For example

return {"Path":[3,1,2,0,4,5,8,7,6,9]}

would submit a route around the cities that would suggest cities with the index of 3 and 1 are close together etc.
When the game is in play your route will be plotted onto the map. If your route is coloured yellow you are currently winning the game otherwise it will be shown in red. Your home city will be shown as a white dot with all others coloured in black.

Helper Functions

  • get_distance(origin, destination) - Given two city coordinates of the form [x, y] returns the distance between them
  • find_closest_city(coords, cur_city, available_cities) - Given the list of city coordinates, the current city index, and a list of available cities indexes to choose from calculates the closest city (from the list of available cities) to the current city and returns it. For example, find_closest_city(gameState["CityCoords"],0,[1,2,3,4,5,6,7,8,9]) would return a number between 1 and 9 that is the closest city to city 0.

Bot Strategy

Here are some suggestions of strategies to improve your bot's performance.

Only submit a route if its better than your current best solution

Only submit a solution if you know it is better than your current best solution. The goal here is to save processing time. If you submit every solution you calculate, you lose time waiting for your code to be called again. If you only submit solutions that are better than your current best, you will be able to iterate through more possible solutions in the time available.

Do not submit a route which is the same as your opponents best route

Do not submit the same route as your opponents best solution, again you will waste time and the route will only be rejected by the server. Please note the starting at different point and going in the same order will count as the same solution eg [0,1,2,3,4,5,6,7,8,9] is the same as [5,6,7,8,9,0,1,2,3,4] or doing the same route in reverse [9,8,7,6,5,4,3,2,1,0] etc

Keep track of the time

Submitting a route is slow so it might be best to go through the maximum number of solutions you can and only submitting the best candidate at the very end of the 20 seconds game time.

Nearest Neighbour

Pick a city and then travel to the next closest city that you haven't already visited. So for example if you have the following 10 city map:

tsp_example_map.png

Starting at city 'A' you can plot a reasonably good route around the cities by just going to the next closest city as shown below:

tsp_example_map2.png

Make sure you keep track of the distance as you go around the cities to follow the rule of only submitting a route if you know it can win.

Swap your starting point

Using nearest neighbour try a different starting city as this will quite often lead to a different result which may or may not be better. So starting at city 'J' would yield the result below:

tsp_example_map3.png

Reduce cross overs

Reducing the number of times you cross over your previous path can lead to a better solution. So if you use the nearest neighbour starting at city 'A' you can see that move 'C' to 'D' crosses move 'I' to 'A'.

tsp_example_map2.png

If you swap these over ie 'C' to 'I' and 'D' to 'A' you will have a better solution as shown below:

tsp_example_map4.png

Playing Strategy

They key thing to remember is its never too late so keep trying different approaches and strategies as it could be a bot starting late in the evening could jump to the top of the leader board.

If your happy with your bot strategy create a new bot to start a fresh and don't be tied to past performance. To do this follow this link and click 'CREATE NEW BOT'.

create_new_bot.png

Make sure your code uses this new bot by setting the botName to this new bot eg 'mynewbot'

botName='mynewbot'

To win the event you must submit at least 50 games which takes around 20 minutes however you can have multiple bots running which will decrease this time. If you are using the OCE its just a case of opening another browser window and running the same code with the same bot name. You can also set the OCE to play one game straight after another a set number of times, to do this click advance settings button as hi-lighted in yellow below:

oce_setup.png

You can set the number of games to play to 50:

oce_set_games.png

Even if you have a winning bot you might as well try running another 50 game batch with a different bot id as you may end up with a slightly better average. You also have a chance of beating the 'biggest difference' bonus competition with every additional game you play.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License