Introduction
Everyone can enter our Travelling Salesdrone Problem competition with a chance to win a HD Drone.
The competition runs from Monday, 6th February to Thursday 15th Feb 12:00 noon GMT
Read more to find out how to play.
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, if the default game loaded is not Travelling Salesdrone, select this game type from the Game Type drop down and choose the drop down option on the new button to create a new file based with the Travelling Salesdrone template code.
This Travelling Salesdrone template code is ready to run however this code will play a very poor strategy. You can jump in and 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 you're new to Python there are many help guides on the net including:
If you are a more experienced programmer and you particularly want to use your own development environment, you can download our demo client that uses API calls to receive game updates and submit game moves:
Objectives
The challenge for this competition is to create a bot to solve the well known Travelling Salesman problem. We've upgraded the salesman to a drone, but the principle 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 you must play using game style 407.
At the start of the game you are given a random set of X and Y coordinates on our 100 by 100 grid. These coordinates represent the cities. Both players are given the same set of coordinates.
You can start your route at any one of these cities but you must visit every city and return to your starting point. 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, you'll see your route 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 route, then the winner will be the person who gets to that solution first.
You might be interested to see that we tell you what your opponent's current best route is. You can use this information however you like, but, 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.
You only have a maximum of 20 seconds to complete the game.
Competition Winning Criteria
You must pitch your bot against our best housebot, named housebot-competition, playing game style 407 where there are 80 cities on the map. To do this you will need to select opponent 'housebot-competition' and then select game style '407 | 80 Cities | Stake 0 | Prize 0'
Your bot will be judged against the housebot-competition by comparing your best route against housebot-competition's best route around the cities. Your performance is calculated by taking the total length of the housebot's best route around the cities and subtracting the length of your best route around the cities. This will then become a rolling average so the lower the score the better. Negative numbers are positively great as you will be beating the housebot.
For example:
| Game No | Your Best Route Total Length | Housebot Best Route Total Length | 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 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 during the competition 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.
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:
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:
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:
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 a move 'C' to 'D' crosses move 'I' to 'A'.
If you swap these over ie 'C' to 'I' and 'D' to 'A' you will have a better solution as shown below:
Playing Strategy
They key thing to remember is it's never too late so keep trying different approaches and strategies as it could be a bot starting late in the competition that could jump to the top of the leaderboard.
If you're happy with your bot strategy you can create a new bot to start afresh and you won't be impaired by your past performance. To do this follow this link and click 'CREATE NEW BOT'.
 |
Make sure your code uses this new bot by setting the botName, at the top of your code in the Editor page, to the new bot name, e.g. 'mynewbot'
botName='mynewbot'
Each bot must submit at least 50 games to be entered into the competition. Playing 50 games takes around 20 minutes, however, you can have multiple instances of your bot running which will decrease this time. If you are using the OCE it's 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 the Advanced Settings button as highlighted in yellow below:
 |
You can set the number of games to play to 50:
 |
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.