I found that the back power was useful when my opponents had bugs in their code.
1 Like
Iâve learned this time paradox the hard way, that you come back in time as dead as in the present, but I didnât thought for one moment to use it against my opponent⊠I really need to devote more time on developing malevolent behaviors. 
I noticed that the rewind would case some AIs to kill themselves, but it never crossed my mind that it wouldnât bring back the dead. I never used the rewind to try to kill AIs, but the thought did cross my mind. Though, the thought of using it right after an AI dies is interesting.
1 Like
Well, it is interesting but I think a bit useless because good AIs do not die. You may use it to avoid an adversary to close a loop by waiting a loop to be closed (you need to remember the previous score and compare it with the current score) and after some time, come back in time. If your adversary did not planned the back in time, he may not close his loop after coming back in time (as he wants to go somewhere else). However, once again, after two days of competition, a lot of players implemented a strategy to counter it. You just need to record all your past moves and detect when a back in time is done.
A strategy you can try if your are 1v1 is to wait the other player to close his loop, then immediately come back in time and try to destroy his loop. Finally, that was not so good because most of the time, it destroys your loop too and so you have no point.
What I finally chose was to attack after my own loop was closed (I needed to limit to size of it), and I used the back in time to avoid an useless attack if it failed (so I can continue to do my loops).
For other games than 1v1, I had no specific strategy : I was just expected what other players did not implemented something to counter a back in time attack 
It may be possible to attack one of the adversary but that leaves the other ones alone and free to do a lot of points.
Iâve found that this sort of thing could be countered by strategically being Ralphie Wiggum.
I never got my bot on any kind of level to switch in and out of Ralphie Wiggum mode during the contest. Perhaps Iâll be able to add that into how I handle the Multiplayer Arena.
Oh right⊠the Ralphie Wiggum approach is to do something so incredibly random, stupid and ridiculously poorly thought out⊠that it breaks the overly thought out AIs. Which⊠watching through contest play throughs⊠did win some poorly designed bots some battles they really should not have won.
This is kind of why I had my AI avoid the two squares closest to the edges of the area/screen.
I noticed there was times when my little bot would just decide, âyou know what is a good idea? Going off that freaking cliff! That seems quite quaint! Jovile notion, I shall do it at once.â
Adding some random thing can be good if the other player try to predict our move, which implies that he is doing some alpha-beta or min-max algorithm with an evaluation function. I did not find a good evaluation function so I preferred to use a reflex with few exploration (I just check next position with some heuristic).
However, if your action does not really influence the other player action (except if you are really close), doing too random things can be bad because you do not construct a optimum and consistent area you can close. I think here the optimal shape was a rectangle, so doing something random might lead to lose a lot of points.
1 Like
Mine was done by picking locations randomly until Wed. If I remember correctly, I was in the top forty percentile at that point. It was kind of fun watching my AI randomly break other peopleâs squares. The problem with setting random paths, was that there were times where you could score a lot of points by just moving to this one square to close off a nicely sized area, but watch you AI pick some lone spot on the other side of the grid. The other issue was that the AI that extracting meta-data from the board were become immune to the random pathing I was using. My rank was falling behind at a steady rate.
1 Like
I noticed that my code would sometimes extract data that wasnât possible, throw an exception, and die due to a time out. I was able to figure out one of the causes of this problem (I was using desired border points instead of border points). Yet, I think the other cause had something to do with my AI being on top of an unclaimed point with another AI. So, I had my AI pick a random point on the board while it took an extra turn or two to recover.
1 Like
In the beginning I implemented very simple tactic much like the depressed bender single player game. The AI would try to go in one direction, and when it encounters non free space, turn to next direction, unless it was also not free. This netted me rank 30+ in the first hours (funny!)
Afterwards I realized my âbenderâ tried to win by creating the most magnificent square ever, which failed almost every time. I had to set some limit on square crafting and settled on 10 x 10 squares.
My bot also decided to move to 0,0 grid spot once it couldnât find any free spots next to him. Interestingly sometimes it went inside other AIs squares and started building own squares inside them.
I wished that I could have improved this âtrolling inside squareâ behavior but I didnât have enough free time to implement something like that. I just settled on to improving the free cell finding to closest cell instead of 0,0.
Overally I had much fun during the contest, I havenât been in any other contest before so this was my first time. See you guys in the next multiplayer contest!
2 Likes
3+ players
My final strategy was to have a list of squares I could reach before anyone else and then try an x first and a y first elbow to each of these positions (idea from Magus). These are then ranked by:
- Squares taken
- Efficiency (squares/turns)
- Voronoi of next square in the elbow
- Voronoi of last square in the elbow
These elements are used to compute a score with a linear function and the best is picked.
Voronoi: What is meant by Voronoi is the number of squares I can reach before anyone else in a given situation. For example when considering an elbow to a location and having to decide if I will go x first or y first the one that gives the most voronoi for the next square will be picked. This leads my bot to color squares closer to other people first, thereby making quite a literal wall dissuading everyone from coming to my area. The Voronoi of the last square also has some importance because you want to go towards a place where you have as many options as possible afterwards.
Linear Eval: In the begining I had if else rules with priority on efficiency then squares then Voronoi⊠but I found that a linear function was much better because your bot is then willing to sacrifice some short term efficiency for better future plays (Voronoi).
Updating the Target: In what I have outlined above a target is picked and then it is followed untill completion. What improved my play alot was to every turn scan for better elbows when I was doing an elbow with efficiency higher than 1 (completing a rectangle). This was done by looking for an elbow which would give better efficiency. This regularly lead to bigger non-rectangular areas and improved ranking noticeably. When doing an elbow to close a rectangle I was also scanning for corruption of the rectangle by ennemies, if it was corrupted pick another target.
The coefficients in the evaluation were different for 3 and 4 player games.
Endgame
If there wasnât a single square I could reach before anyone else I had a primitive backup AI that would go to the nearest neutral cell with a tie break on the Voronoi, this was the behaviour in the endgame where there are a few neutral cells here and there, or on the first turn of a game where everyone starts on the same cell.
Back in Time
When a back in time from another player was detected a new target was computed to avoid crashing. I didnât use BIT myself though I experimented with it a bit, I think this game is 99% about your moves and using Back in Time is not a priority.
2 players
I used Minimax with alpha beta pruning and an evaluation function built of squares owned and Voronoi in a linear fashion (idea from Magus). This leads to wild behaviour compared to other AIs but it performed quite well and 1v1s wernât very important for ranking anyway.
Improvements: I think the fundemental workings of the AI, thinking with elbows, is flawed and should be replaced with scanning for rectangles for example. I think the Voronoi ideas are pretty solid but may need refinement and some way of finding the best coefficients.
Final Rank: 91 (~60 in multi without changing code)
5 Likes
Hi guys!
What a fun contest again! Congratulations to the team! I really liked the back feature, it forced us to think differently and add a dimension we are not use to have. The subject was great and despite its similarities with tron, I did not started from this IA but wrote something completely different.
I start trying to find the biggest rectangle which pass by my bot, and which is in my Voronoi territory. Once found, I memorize it like a list of cell to follow, its coordinate to detect if another player penetrated in the rectangle, and name it Path. At each turn I keep the current board state, the path I planned so that any back in time does not break what I planned. If the path is still valid, ie no other player get into the rectangle, I continue the planned path. It avoids making my bot shrinking on itself if an opponnent is going close to the rectangle and modifying the Voronoi territory.
If a player get inside the rectangle, I go back in time the max I can up to when I started following this path, and I consider the voronoi territory as if the player was at the position he enter my rectangle. Thatâs not really great because it is making my bot taking a much smaller rectangle, but is better than doing nothing 
If my bot canât find a rectangle, it will go to the first free area in its voronoi territory, or the first free territory on the board if not found.
I also generate a random move if I am on the same coordinate as another player. I did this because I got several time a situation where my bot and another one are stuck on a couple of free squares and they are switching from one to another
Simple no? I finished in the top 100, which is great!
A few thoughts on the contest:
- In my opinion, 8 days is too short, it is a rush all along, and you canât really experiment different possibilities⊠I would expect at least 2 weeks, perhaps 3. The week end of the final, I had so many things planned, I had only a couple of hours to try (and fail ) adding additional featuresâŠ
- We still have complains on the leaderboard stability over time. The conclusions I had in the following thread are I think still valid : you can keep the previous trueskill evaluation when a player resubmit, so that you can run less matches and save CPU or use this additional CPU to run matches continously to keep the loaderboard alive. If playing a lot of matches is mandatory, your trueskill evaluation will still be an evaluation arround your actual real skill. In this challenge you introduced a âfinal phaseâ on which players have a additional number of matchs to play. Thatâs super great, just make the average of the trueskill level during this phase to have a better and much more stable evaluation of the skill of each bot.
- And keep in mind it is not mandatory to propose 1vs1 and 1vs1vs1 and 1vs1vs1vs1 matches. It would be very fun if the next challenge is a 1vs1 only (and would again save CPU
)
My 50 cents
Manwe
6 Likes
I still think there is something wrong about the rankings. My code ranked 143/2018 in the contest, but the same code ranks 93/2130 in the multiplayer gameâŠ
1 Like
Dimkadimon : If the ranking is able to correctly assess the rank of the three top players, isnât that good enough ?
But how do we know that it can access the top 3 correctly? Recar won the contest, but AlexSurin is now first in multi-playerâŠ
2 Likes
I donât know ⊠what formal definition of the winner would you propose ? Do the games data concur that this definition do hold for the final ranking of the best players ?
Since the TrueSkill ranking system uses a Gaussian belief distribution to characterise a playerâs skill, all mean skills (that is, ÎŒâs) will always lie within ± 4 times the initial Ï (more precisely with probability 99.99%). Experimental data tracking roughly 650,000 players over 2.8 million games support this claim: Not a single ÎŒ ever happened to be outside the range ± 4 times the initial Ï and 99.99% of the ÎŒâs happen to be even within ± 3 times the initial Ï.
I think you spotted exactly what we are trying to say:
Trueskill gives an estimation of your skill with +/- 3 Ï
Practically what is the value of Ï? It starts at 8 and It should be something like 0.7 after a great number of matches, and wonât decrease because sometimes you win and sometimes you lost.
What does it means? That your real score is between your score +3Ï and -3Ï. Applied to our current leaderboard, that means that you certainly have a score + or - 2 points which when you are arround the top 100 at a precise moment in time, represent a real rank between 50 and 170. I think we could estimate that a range of 1 point is certainly more realistic, and it means you certainly have a real rank between 70 and 130. Meaning each time you repush the same bot you will end up in this range
It is exactly why I suggested during the final phases to compute the means of the score in order to have more stable results and not relying on the last few matches to gain 0.2 or 0.3 points which represent a consequent number of places. If Recar won the contest it is certainly because its bot finished with a few victoriesâŠNow AlexSurin was certainly in average above in score, and now took its place back. The 3 first player are clearly the good ones since they have more than a point with the 4th bot.
Concerning the training area, it should not take the mean into account since everyone can improve his bot and repush. In this case we will just have an estimation of our new bot, which is great already no? Push the same bot several time, an average of its score will certainly give you a better estimation of its real value.
3 Likes
What bother with me with your idea of an averaging is that i wonder if it will be sufficient to settle all disputes ⊠hence my question about a rigourous definition of winner, one that everyone could agree on.
If i follow you, the current definition is that a bot will win, if its estimated level is in the range of the first players, and then it gets lucky with its (lasts) matches. Is that really totally wrong ? Or is it only somewhat wrong ? If everyone knows the rules beforehand, maybe itâs totally okay. Itâs certainly better than a system that would pop out a winner out of the 100 th âbestâ bots with one random roll of the dice.
My opinion is that the system is good, and that in order to propose something better, one would need to define the notion of âbestâ. I think itâs (almost) easy to agree on what best mean when the game is 1vs1. For me itâs far much harder with mutiplayer games. Is a bot that never ever end up beyond 2d place better or worst than a bot that end up first with 80 % probability, and last with 20% probability ? I have no idea what trueskill thinks about that. Nor do i have an idea of how the community would react if that bot or that one was declared winner. What about a bot that wins all 1vs1 not matter what, but end up always 2d in multiplayer, against a bot that get a 85% first position 15% second in multiplayer, but always end up last in 1vs1 (Itâs popular to have different bots for 1vs1 and 1vs many âŠ)
The main complaint here seems to be that the final rankings is still random, despite the effort of the team to add more games in order to have a more precise result. Although everyone seems to agree that the algorithm is quite good, and really is able to distinguish âgoodâ bots from âbadâ bots.
Rather than an averaging, i would suggest that there is a final tournament that would run with only top bots, with a firm and published rule that then gives the winner out of the data (wich would be accessible ideally âŠ). With ten bots all matching possibilities should be tested ⊠maybe it would also be possible to give beforhand the rules of the final matching rules (Symetric start / number of object / Number of 4 player matches / Number of 3 player matches etc etc.)
To sum up (cause itâs a bit messy)
1/ True skill is good for objectivly grouping bots by estimated strength
2/ Something better is needed to elect a winner.
3/ Averaging might not help to obtain something much better. It might be hard to implement also (no idea about that). [My idea of a final tournament is probably much harder to implement though âŠ]
1 Like
Well not sure it is perfect, but when testing it gives pretty good results. The main idea is more that this averaging will keep a contribution from the previous matches which will in the end stabilize the leaderboard.
I made some experimentations with trueskill a year ago, the tool is available on github : https://github.com/Manwe56/trueskill-ai-contest-test-tool
Have a look at the readme on the webpage, it gives a lot of info, even how to configure a situation where a player A wins on B which wins on C which wins on A and discover how trueskill would rank them. You can modify the tool and experiment at willâŠ
We will still have players complaining about leaderboard stability. I donât think we can really make something before the final stage or after in the training area : to keep the leaderboard live and taking into account updated bots, we must use approximated skill (and not mean skill) that gives you an idea of your bot strength. What would be nice is instead of giving an exact ranking to the coders (which is in the end the source of the complains), why not giving them an estimation? For example, you are estimated 100/2000 which means we are confident your bot is between 70 an 140 based on its sigma value.
You can represent it like
70/100/140 over 2000
And play with colors and tooltips explaining the different values. So that you are not guarantying a rank anymore. If you donât reset the skill of the players each time they resubmit, you will even additionaly erase the vicious effect of the last hours where you think your bot is a killer, but it is just because everyone above you just resubmit
When you run the final stage of a contest, keep a trace of the skill of each player so that you can give a chart for each player compared to other ones. We would clearly see that with means things are stabilizing. If you have those statistics with past contest, it is certainly an excellent database to learn what should be done.
Concerning the 3 and 4 players matches, I understand it is interesting from an AI point of view, but for me it is adding a lot of noise. Even ignoring the fact you must finetune your AI for each number of players if you want to inprove, when you have a look at your games, you often face a frustrating situation where you finish 2nd or 3rd just because you have been fighting with another player and the other has been alone. You are not feeling like the other IA was better than yours.
So I guess next time a 1v1 only game would be great!
I know the team is making great efforts to improve :)! I am sure you will find new enhancements that will ensure everyone is happy. Averaging is not hard to implement, just run a match for each player on each step, and at the end of the step take a snapshot of the leaderboard. Comparing to now, what change is that the players will finish their final additional games at the same time.
Anyway until you donât have a system that ensures that in the last 5 minutes you can loose or gain 20 places in the leaderboard (And I saw it for my bot in live on Platinium rift from the 30 to the 50âŠ) it means you donât have the good system.
We are not trying to rewrite the past, just making sure to enhance the future, and remove the frustrations.
5 Likes
I like your proposition of a range rather than a hard position (or perhaps in addition to ?) a lot.
On the 1vs1 matter, i am ambivalent. I do agree that 1vs1 is the most easy part, no ârandom noiseâ, you can really concentrate on making your bot the best it can be ⊠But maybe that random noise is what make that challenges so enjoyable in the first place. It does add strange depth to them.
I also agree that itâs a bit strange that a lot of time people would start to build different code for each possible number of players. Because optimizing a 1vs1 bot is such a different task that building a winning 4vs4 free for all one âŠ
What i would love to see is a challenge where there is a different leader board for each number of players consideration. And then maybe the winner is just elected base on weighting of each configuration. I think there are good chances that bests players for one setting, will still be also the best players for others settings (like the top 100). Just because the 1vs1 and 1vs4 do share some caracteristices, especially when bots are still weak.
It does sound much easier on the coding game team to just give a challenge with a fixed number of players though âŠ
Random number of bots multiplayer is a lot of fun, but once you begin to really tune your program, you end up filling like you really are competing on different games.
3 Likes