Diploma: Tanchiki and Genetic Programming

Published on July 15, 2013

Diploma: Tanchiki and Genetic Programming

Hey.

When choosing the topic of the diploma, the desire to create something practical was taken into account, which influenced the choice of topic. It was decided to develop a platform for holding AI tank programming competitions. In general, the idea is not new and such things have already been done ( http://robocode.sourceforge.net , for example). But there are several reasons why the tanks were chosen:

  • These same tanks served as a platform for the theoretical part of the diploma: the study of GP in relation to the task of managing the object
  • As mentioned above, I wanted to encode something of my own, develop a protocol, program the server and clients.
  • Work with OpenGL in practice
  • Try C11


I will not talk about evolutionary programming, because it has been discussed many times here, and, besides, describing it again after writing a diploma is not a pleasure.

Unlike other implementations, my tanks are in 3D. They drive through the terrain, which is read from an external file with a height map . Also, the plans were at least somewhat realistic physics, but this was not enough time and energy.

Protocol


For communication, the binary protocol is used over UDP. Why is UDP? It preserves message boundaries because it is a message-based protocol. This means that the data comes in exactly the same portions as it was sent, which greatly simplifies the network part. Given the lack of time, this, in my opinion, is a reasonable decision. Instead of UDP, one could use SCTP, for example. But it was not implemented under Windows, and development was carried out under this OS.

The protocol consists of packets, each of which begins with id. Therefore, the size of packets is often known in advance - by the first byte. For packages of variable length, a static part is provided in the package body, which allows determining the size of the entire package.
In the code, packages are described by C-structures with alignments disabled.

Components


Tanchiki consist of a network server, test and "genetic" clients and a viewer program.
The server processes requests, sends notifications and conducts all calculations.
The test client is for debugging. It reads tank control commands from standard input and sends it to the server. For example, pi (power increase) - increase engine power, s (shoot) to shoot, ll (look left) - turn the gun slightly to the left.
"Genetic" client - launches a genetic tank control program in Slash / A language . This is a language specially designed for the GP and VM for its execution. The VM command set has been expanded with tank-specific commands.

Example program on Slash / A:
input/   # gets an input from user and saves it to register F
0/       # sets register I = 0
save/    # saves content of F into data vector D[I] (i.e. D[0] := F)
input/   # gets another input, saves to F
add/     # adds to F current data pointed to by I (i.e. D[0] := F)
output/. # outputs result from F


The viewer program is designed to monitor the battle. You can soar above the map using WASD, F, V and rotate the camera with the mouse.
During development, a couple of test clients (for the victim tank and the winning tank) and the viewer were some of the main debugging tools.

Screen:


C11


C11 added a lot of different features. The following were useful to me:
  • Type-independent macros (math and math.h)
  • Multithreading


Also, the Variable Length Arrays and Designated Initializers from C99 were useful. Well, the ability to declare variables not only at the beginning of scope was also very useful.

To build the C part, we used the excellent pellesc.de compiler with excellent help on libraries, language and environment.
To build the C ++ parts, GCC (MinGW) was used.

Link to sources: http://code.google.com/p/morrigan . Unfortunately, I am poorly versed in licenses, so for the second project I choose “Other Open Source”. Somehow I’ll definitely read some kind of educational program.
In principle, there is only one unsortable dependency - Winsock. Why morrigan wiki. From the very beginning, I decided to call the project a female name, and then the idea came about the goddess of war.

I made up the diploma at LaTex, which I never regret and I advise everyone. This is not as scary as it might seem, especially after a year of preparing protocols for laboratory in LaTex. In case of difficulties, google saved me (which resulted mainly on tex.stackexchange.com ) and good package documentation. Looking at my friends who painfully manually arrange the page numbers in the frame, the captions to the figures and tables and links to them, I once again became convinced of the correctness of the decision.

Overall, I am satisfied. I managed to get a little distracted from the ubiquitous OOP and program for my own pleasure.

References