Après de nombreux tournois, mon bot (posté il y a maintenant plus de 6 mois) est désormais premier du classement, yeyyy 😀
Classement au 04/06/2013
[Post Initial]
Après AI Challenge “Ants” 2011, en manque de défi d’IA, j’ai effectué pas mal de recherche sur internet afin de trouver un concours qui me plairait.
Et je l’ai trouvé (enfin partiellement) FinalBot est un site concu il y a un peu plus d’un an, avec pour but d’hoster différents concours d’IA.
Lors du lancement, 2 jeux sont mis en place:
Un jeu de dark chess (les échecs avec du brouillard de guerre! Il fallait y penser!) et , de manière plus importante: un jeu de Hold’em Poker.
Top 2! (11/06/2012) Le premier est … loin oO
J’avais déjà eu l’envie de faire une IA sur ce thème du poker. Mais la mise en place du jeu peut être laborieuse et chronophage, ce qui m’avait un peu refroidi.
Bref, découverte du concours:
J’arrive après la guerre: le site et le concours ont été lancé durant l’été 2011 et une fois les récompenses données aux vainqueurs, le site a vu sa fréquentation décroître. Les bots développés sont toujours présents et 3 compétitions sont organisées automatiquement tous les jours (standard, headsup, bigpool). C’est CLR plateforme uniquement (C#/CPP/F#)
J’ai créé un bot début Août, random bot d’abord, afin de tester le site. Puis je m’y suis réellement mis. J’ai récupéré et testé un bon paquet de librairies “permettant” de calculer les probas dont j’avais besoin.
J’ai fini par choisir un package(C#) créé par Keith Rule (lien). Cet utilitaire ne fonctionne pas, comme je l’avais imaginé, sur des tables de données précalculées. Non, les probas sont re-calculés à la volée. C’est extrêmement bien optimisé (pour du C#), ce qui permet de calculer ces probas avec une bonne précision dans le temps imparti.
Mon bot est assez simpliste pour le moment. Il joue relativement safe et tente des bluffs dans un seul cas: s’il est le dernier à parler, que tout le monde à check et qu’il a des jetons. (dans ce cas là uniquement 30% du temps) Il n’analyse pas le comportement de chaque joueur en face (c’est le prochain pas)
Beaucoup de règles sont donc implémentées, avec de nombreux tresholds variables selon le nombre de joueurs toujours à la table, les valeurs de base étant setté via la bonne vieille méthode empirique et de bon sens. (donc très clairement améliorable!) Le Heads-Up (1v1) est géré de manière indépendante (car il faut être, de manière générale, bien plus agressif en 1V1 que dans une partie avec plusieurs adversaires)
Après des mises à jour successives, je me suis rendu compte que le rythme des tournois mis en place sur le site officiel était bien trop faible pour avoir une visibilité un tant soit peu précise sur les conséquences des “améliorations” apportées au bot. De même pour le client de test (permettant de faire des matchs offline, entre les bots fourni (raisebot-callbot etc) et les bots développés (dont on possède les dll bien sur!)) : Problème: ce client de test permet de faire … 1 match par 1 match. Pas de quoi avoir des stats précises :/
J’ai donc prit cet exe de test, browsé son code (via ILSpy) pour récupérer les méthodes utilisées pour ajouter les joueurs, lancer les matchs, récupéres les scores etc. Ensuite, création d’un nouvel exe winform sur visual studio. Intégration des dlls de l’exe de test, et je me suis fait mon tool à moi (très design, comme d’hab)
FinalBot Canon Launcher – Un design hors du commun
Grace à ce tool, j’ai désormais la possibilité de voir ce que mon bot vaut … véritablement: (données basées sur le % de première place) Ici un exemple avec 1000 parties:
Tiens tiens, la version 8 semble moins efficace que la 7…
Problème: je n’ai pas les DLLs des concurrents! (à venir, le premier du concours m’ayant “promis” sa DLL) A l’heure actuelle (je n’ai pas touché au bot depuis au moins 1 mois et demi) je suis 2ème du classement continu (La montée à pris du temps, dû au fait qu’il y a seulement 3 tournois/jour)
The AI Challenge is all about creating artificial intelligence, you will create a computer program (in any language) that controls a colony of ants which fight against other colonies for domination.
Basic situation, the antHill on the top left corner, ants are white dots. Grey dots are food and blue is water (can’t go through)
Simple fight: 2 versus 1. The 2 orange ants will survive.
Complex map control by good players
Complex game control with several players
Here’s a game introducing the concept: (pro players)
NB: click on the fullscreen button in order to appreciate the game and +/- keys in order to adjust the speed.
Loading…
Rules are simple :
You gain points(2) by razing enemy hills. You lose one point per hill lost.
Every time you pick a food (get close to it), it disapears and creates a new ant in your ant hill
I’m going to describe briefly here how my C# bot works. It’s very far from being perfect, even far from being good but I made something working. And I finished it on time.
The code contains a couple of array -maps- containing different infos, updated in real time for some, and at the begining of every turn for others.
mapWater: Water map
mapVisible: number of my ants seeing a specific Tile
mapLastTurnSeen: Map of last turn value I’ve seen the specific Tile
It computes every routes in a certain range in order to protect my hills, attack enemy hills or collect food. Add them to a list and sort them afterwards
Food routes are less important than defendHills & attackHills ones. I picked a coef 3 in order to make this distinction. Thus a 3 cells AttackHill route is equivalent to a 9 food route.
After the filter applied, I give the “real” orders right away. (I won’t change them)
The defendHills make 2 of my closest ants go towards one enemy. No more.
One piece of food is target by only one of my ant (the closest, if not used for defending or attacking ofc)
Phase II: Attack close enemy ants
After that I make my free ants attacks close enemy. The idea is to “push” enemy and to diffuse my ants towards enemy hills.
Phase III : The Sentinel
After that I make, if I got enough ants, one of them stay close to my hill. This way I can see if an enemy is coming. This ant will not stay static because of the previous calls. If a food just appears, it will go collect it which will generate a new ant (which will probably take the “Gardian” position, if nothing else is needed) Same if an enemy ant approches, it will go fight it.
Phase IV: Explore the map
A good exploration state
Then and last, I call the ExploreMap function where Free ants will go explore the map.
I use a map monitoring the last tour I’ve seen every cell in order to make the ant goes somewhere “new”.
It goes towards 8 differents directions (E/N/S/W and combinaison like N-E)
I start one cell further the view range of the picked ant. If alls cells are already seen, I go one cell further. (Water tiles are not taken into account)
The 8 cells are then sorted by turn they have been seen. The ant will go toward the “oldest”
TECHNICAL DETAILS
1.Movement
Directions are made with an A* algorithm. I use the following one that I’ve modified just a little bit.
I have a list of timeout routes which helps me to not compute too long – complicated – routes again and again.
I wanted to do the same with computed routes (to not have to compute them again and again if needed, but they can change if I discover that an unseen tile is actually a water tile) I started to filter them every turn but it was really too time-consuming.
2. Fight:
Everytime I give an order, I test the “safety” of the area. My implementation is not really good, but it gives a basic idea of the security (not optimized though)
I sorted safety into 3 different categories (following some advice I found on the forum, Memetix® style)
SAFE: no worries it’s ok
KILL: I can expect to have a 1-1 trade with the enemy
DIE: It will be worse.
Some of the following conditions make my ants decide (or not) if they should go to a KILL area like :
If there’s a food between the enemy and I. If I have a lot of ants etc etc.
If it’s considered to be unwise to go, the ant will try a close direction, or to stay put or even to go back in order to avoid death.
PROBLEMS ENCOUNTERED
1. A* Algorithm
First of all, the A star algorithm.
I picked C# because it’s the language I use at work and I’m the most used to. However, existing Astar code are legion in c++ but real few in C#
I tested 2 very well graded on source code website. Istarted with what I thought was the best of them. Timeout used to occur if the path was 10-15 tiles long. I developed my bot during 2-3 weeks with this algo, making a lot of concessions because of the timeout problems. Then I found out it wasn’t normal at all and found a new one, which was described as “not perfect” because it’s not giving the shortest path.
It was the worst error I made, to not have discovered this one before. I kinda lost one week and a half.
2. Exploration
I started with monitoring how many ants were seeing every tile, trying to send them where tiles were “less” seen. It was working ok but I had some very bad “cycles” where ants used to jitter.
I switched to the last turn seen way, which gave me better results.
Before my final submission (like 12 hours before :s) I still had some bad behaviours: in some maze_map, ants used to stack at one point and jitter alltogether, like if it was awesome to finally have some security or friends or I don’t know. Anyway, I patched it quickly: ants which don’t have any orders at the end, if surrended by more than 7 ants in some small perimeter should go towards the closest enemy.
It’s dirty, it’s last minute modification, but I think it was worth it.
NB: After almost every group of modification I made during the last 2 days, I ran a couple of test games (~10) where I’m supposed to win against middle-skilled opponents. It happens that results were pretty bad so I could review the previous modifications.
CONCLUSION
I spent a lot of time on the exploration system. I wanted to go step by step and not rush the global feature bot too soon.
The first implementation I made was just monitoring enemy position, creating an array of “Unsafe” positions and … that’s it. It was obviously not good at all, my ants were just fearing every single enemy. I found the memetix post (link) and tried to implement it, but I guess I screwed up because I had to make some modifications and the result is far from my expectations. Time went fast and I couldn’t have a “proper” fighting system and the result is that I can’t really play map control like pro players do: having walls of ants facing each other.
Anyway, it was a really interesting contest. I’m glad I found it quite soon (I think I missed the 2 first weeks but I had 1month and a half to develop something) I’m also glad that “Fredo”, a colleague of mine followed me on this event, so we could compare and improve our bots. I think the result would have been way worse (yeah, it’s possible I’m sure!) if I was alone on it.
Even if they won’t see that, I’d like to thanks the organizers for their amazing job. The game engine was awesome, the starter pack perfects, tools aswell. The finals (even if it’s still going on) are really interesting. The community was very friendly and best players gave tips and shared their source code at the end, which is very nice and very interesting.
To introduce the topic, I’m going to quote wikipedia (I know, it’s bad, but at least I will not lose anyone at the first line :))
The inverse kinematics problem is simply stated as, “Given the desired position of the robot’s hand, what must be the angles at all of the robot’s joints?” This is in contrast to the forward kinematics problem, which is, “Given the angles at all of the robot’s joints, what is the position of the hand?”
Humans solve the inverse kinematics problem constantly without conscious effort. For example, when eating cereal in the morning, humans reach out for their spoon without considering the relative configuration of their shoulder and elbow required to reach the spoon.
In this project, one of the goal was to implement a function allowing to compute the pseudoInverse of a non-square matrice. After some researches, the SVD and Greville algorithms seemed to be the one to use. For now I’m not going to enter too much into the rest of the project, but I mostly wanted to make my code available for people who would like to do the same ( I couldn’t find any code of the Greville algorithm at this time) Mine is coded in C++ with the GSL library
In the archive, you will find the implementation of the Greville and SVD algorithm, plus a simple test code allowing the test of the performance of both of them. To make it faster, you can see below some information about the speed of the two algorithm.
The second assignment in the Stavanger University “Cryptography and Network Security” course was slightly harder, especially because during the generation of the key we have to play with huge numbers. I developed the application in Java and used the BigInteger class to handle these huge numbers.
The program works like that:
1. First, you have to generate your own public and private keys and you save the public key in a file (.pk extension)
2. Then, type your message and sign it, then save it in a file ( .mes extension)
3. The last step (the most important) is the part where you check if the message loaded really comes from the official writter. So you have to load his public key, load the message and then press check.
Here is a screenshot of the application:
For information, I have implemented the digital signature algorithm with a 1024 bits long p and a 160 bits long q (for people who knows what the DSA algorithm is all about)
I use a hash function made by myself. You can find everything in the code at the end of this post.
And you can download the whole project (code + exec + report) here : > Download <
First assignment of the course : “Cryptography and Network Security” I was following in Stavanger University, Norway.
The goal was to develop a Feistel Cypher, we could choose an existing one or create one of our own conception.
After some tries, I realized that my cypher wasn’t really secure, so I implemented the DES (Data Encryption Standard), with one modification: The key required doesn’t need to be 64bits long, a function generateKey makes the key as long as the size of the plaintext.
Screenshot of the application:
GUI of the Java application
You can download the whole project (source + exec + pdf report) here : > Download <
Après AI Challenge “Ants” 2011, en manque de défi d’IA, j’ai effectué pas mal de recherche sur internet afin de trouver un concours qui me plairait.
