AI for Tic-Tac-Toe (Part 1)

TicTacToe0

Neural Network is a subject which interests me. Nevertheless, I was never idea about an application of the artificial intelligence. Recently, I remembered an old application I have created: a simple Tic-Tac-Toe. This game is easy, an "expert" can avoid traps and never lose. I have implemented a false intelligence in this game which was unbeatable. When you play, you have not thousand of combinations. First point, you can rotate the board and use symmetry to reduce the number of possible combinations. Second point, when the opponent have filled two cells in a line, you will fill the last one to avoid the opponent to win.

So, my question: is a neural network able to tend toward an unbeatable intelligence? Fortunately, a lot of people use Tic-Tac-Toe to explain Neural Network. I have found an interesting website (Neural network with learning by backward error propagation).

In the first step, I won't present Neural Network, but methods to create a bot to play to Tic-Tac-Toe. Even if I think this is an easy game, the aim is the understanding of the game. These bot could be used as reference to compare the performance of the Neural Network.

1st competitor: 'Full Random'

Before to talk about this AI, I present other competitors. The first of them is 'Full Random' and it plays randomly. If this player plays again itself the result is uncertain.

Battle #1: 'Full Random' vs 'Full Random'

The next chart shows the percentage of victories of this simple player. The first player has an important advantage.

2nd competitor: 'Partial Random'

The next competitor named 'Partial Random' use a random choice except if it can align three cells or if the opponent align two cells. This competitor is better than the first, but many traps exists.

The 'Partial Random' can align 3 cells and avoid that the opponent align cells (except the cases where there are traps)
The 'Partial Random' can align 3 cells and avoid that the opponent align cells (except the cases where there are traps)
Battle #2: 'Partial Random' vs 'Full Random'

This is the result if 'Partial Random' is the first to play.

Battle #3: 'Full Random' vs 'Partial Random'

This is the result if 'Partial Random' is the second player.

Battle #4: 'Partial Random' vs 'Partial Random'

Conclusion

This first article shows two competitors. One which play randomly and the second which prefers to align cells.

The battle #1 presents the real proportion of the different cases: 10% of Ties, 60% for 1st player and 30% for 2nd player.

The battle #4 shows the proportion of traps. So half of cases are traps: 30% for 1st player and 15% for second player.

Next time, I'll present you the third competitor. The unbeatable player.

The Golden Disk

Le disque d'or

Catacombes comme décors
Je suis un chercheur de trésors
Qui parcourt les couloirs hantés,
Veille les esprits égarées.

A suivre les profanateurs
Son ombre est couverte de sang
Se retourner est une erreur
Le fait de son acharnement.

Autre silhouette, féminine
Sur le chemin, se placera
Et une relation intime
Ne peut conduire qu'au trépas.

Voir au loin la couleur du ciel,
N'est gage de trouver la sortie
Son porteur est sacrificiel
Même s'il semble indécis.

Par la lueur de la lanterne
La mort se retrouve tangible
De milles manières possibles,
Rendant funeste ces lieux ternes.

Vincent Majorczyk

Level of detail and geometries merger

The Level Of Detail avoids to display a far object with lot of details. In fact, if an object is far, we can't see the complexity of the object. So the aim of the LOD methods is to decrease the complexity of the object depending of the distance on the point of view.

A model with two resolutions. The studs are composed of 16 quads or 64 quads.
A model with two resolutions. The studs are composed of 16 quads or 64 quads.

Ldraw uses a basic LOD: many objects may use two different resolutions (it concerns cylinders and curved surfaces). On the picture, meshes of stud are more detailed in the second case. The LDraw format file has been created before the 3D evolution in computer sciences, so it considers non smoothed primitive. With this technical limitation, if you want great visual result, you need to increase the number for primitives. So using smoothed surface may resolve the using of detailed meshes. Next, the Ldraw format is a tree structure. Each file contains an average of 15 primitives (quads, triangles, lines) and a list of links to other files. This structure is convenient if you have memory limitation but today graphical cards prefer big meshs than lot of little parts of an object. The program wastes time during tree traversal, transformation selection and culling. The best way is certainly to merge the object whose the memory size is relatively small. So the culling time is insignificant and the global time is lower even with a high resolution.

These screenshot show the computation time to display the same object. The top left image corresponds to the low resolution. At the top-right, the merged low resolution. At the bottom-left, the high resolution. At the bottom-right, the merged high resolution case.
These screenshot show the computation time to display the same object. The top left image corresponds to the low resolution. At the top-right, the merged low resolution. At the bottom-left, the high resolution. At the bottom-right, the merged high resolution case.

The screen-shots show that we obtain speed-up of 25 and 33 for respectively the low and high resolution.

  • low resolution non-merged: 10.4 + 4.5 = 14.9ms
  • low resolution merged: 0.2 + 0.4 = 0.6ms
  • high resolution non-merged: 29 + 14.2 = 43.2ms
  • high resolution merged: 0.2 + 1.1 = 1.3ms

Three points needs to be implemented:

  • LDraw format proposes two type of line (line and optional line) which are merged. These type of line need to be splitted to use them correctly.
  • The second point concern the color, it exists two type of objects: the monochrome parts and the part with motifs (patern). Commonly, monochrome part use the color 16 for each primitive. So color mechanism don't need to be implemented as a color vector. But for patern part, object should be splitted to separate monochrome color and motif.
  • The third point, concern the propagation of the color during the merge. An color indexes vector exists but we don't use it because there are difficulty which the color 16. During the merge, the color 16 may needs to be replace by an other color and I'm sceptique about the interrest to use indexes vectors to group colors.
  • From the application point of view, we need to create a mechanism to exclude a part of the object during the merge. Many times, we will need to separated parts of an object (for example: a door need to be be separate from an house to allows interaction with the door).

Tanned Dinosaure

A few years ago, my sister given me a wooden dinosaur skeleton. After some thinkings, I have chosen to make an original thing. I don't know if it's really original or not, but I have imagined that the skeleton shines in the dark. Nevertheless, my aim was to avoid to illuminate nearby objects. So I have used fluorescent paintings on the bones which and I have lighted up the dinosaur with ultra-violet light. This is absorbed by most of the material and it reflects on fluorescent objects.

I have bought a set of four fluorescent paintings (yellow, green, blue and red/orange). If my first intention was to use an unique color, I have hesitated to chose one of them. I was worried, because I couldn't predict the result: yellow and green colors seem me too common, blue and red might be too dark. So I have used green, red and blue. Now, I think blue color is the worst choice because difficult to see.

The base is a wooden box modified and painted with metallic color. I have installed four LEDs with reflectors on each corner. I have added a special plaster to create a ground with volcanic appearance. This is a plaster for model railroading with a granite texture.

The electronic is composed of a micro-controller, a voltage regulator and diodes. I have used Pulse-Width-Modulation to obtain a smooth evolution of the light intensity.

Geometry

This third post concerns many points of a LDraw Loader with OpenSceneGraph Library. OSG has plugins with read different format. Each plugin is related to a file format. OSG offers to create customized loader plugins. To be honest, I don't know how are constructed all formats of different 3D models. OBJ format need to read a file with the material properties and I'm not sure that it exists 3D model format which use more complex tree structure. So the LDraw format is special, made of repetitive patterns, and it needs to load many files to complete a model. A file which needs to load a file which needs to load a file ...

Application which uses Qt and OpenSceneGraph. It displays LDraw format. At the right of the window, the tree corresponds to the graph of OSG. At the left, there are many data about the selected item (here transformmatrix)
Application which uses Qt and OpenSceneGraph. It displays LDraw format. At the right of the window, the tree corresponds to the graph of OSG. At the left, there are many data about the selected item (here transformmatrix)

For the LDraw loader, I don't want use recursive algorithms because bugs may easily appear. The second point, I need to keep all of the loaded file in memory and avoid to load many times the same pattern. I think it exists in OSG a mechanism to avoid this but I'm not sure of its use. So I have chosen to have a list of models and I have split the loading process into 2 parts: the loading of the data from a file and a mechanism which links models. So when the program load data, it creates a geometry model and stores the name of the model. Next, the model is put in the models list. During the second step, for each loaded model, the program reads the name of children. If the file is already loaded, it creates a link to the corresponding model, else it loads the file and store it in the queue of the list of models. This system is easy to implement but I don't know if it is the best method. Nevertheless, it appears that LDraw models are a support to avoid to recreate model and I will use an another format in my future applications.

A second difficulty concerns a strange choice about the Back Face Culling. The BFC avoids to display faces which aren't visible by the camera. In fact, it is interesting for speed gain during rendering. There are two modes: Clockwise and Counter-Clockwise. LDraw use CCW by default but can use CW and many time a subpart of a model need to invert the BFC mode. For example, to create a hollow cylinder, the author need use twice a cylindrical surface: an external surface and an internal surface. The two surfaces correspond to the same model with a different scale. If the BFC mode is the same for all surfaces, a camera in the center of the hollow cylinder will display no one of the surfaces. So the author of the part needs to invert the BFC of the internal surface. In the LDraw format, the Meta-Command 'INVERTNEXT' allows to change the BFC of the next submodel. I have chose to duplicate the model and flip all geometries and submodels. The new model is registered to the models list with the suffix '_INVERT'. My main use of the BFC concerns the direction of the normal vectors (for light reflexion). There is an another problem with BFC: if there are a negative scale for a submodel (the determinant of the transformation matrix is negative), BFC need to be inverted. So there are two types of inversion: an inversion of a model and a inversion due to transformations (translate, rotate, scale). An inverted model has inverted normal but transformation may change BFC but not normals. For display a brick as an group of submodel, I prefer deactivate the BFC. When I will merge all geometries of a brick in a unique object, it will be possible to reactivate BFC.

In the next post, I will talk about the colors and the Level Of Detail. Currently, only a basic LOD is implemented. This corresponds to a Ldraw specifications for the resolution mesh of a curved surface (as cylinders).

A file format for Lego Models

From LDraw website:

LDraw is an open standard for LEGO CAD programs that allow the user to create virtual LEGO models and scenes.

Ldraw standard has been created in 1995. Many softwares have been created based on this format: LeoCad, MLCAD, SR 3D Builder, Bricksmith LDView... Each of them has their specificities, SR 3D Building is used for Technic model, LDView modify primitive for best rendering, ... Also there are WebGL Viewer and many other tools (LSynth allow to create bending part, exporters to modeler 3D...).

The main competitor of softwares based on LDraw is the official LEGO software: LEGO Digital Designer. Even if a user can create models, he can't use his creation with other softwares. In fact, model exporters exist but the geometry of bricks is unavailable and the user needs an another source of geometries (as LDraw).

So today, I think to create a new LDraw viewer is a needless work. The purpose of my project is the creation of content and games based brick (I avoid to use the 'LEGO' Trademark). But before to aim this dream, we need a basic renderer. Format explanation is described in the tab 'Documentation' of the LDraw website.

My first subject is the color of brick. In a file of the LDraw library (LDCfgalt.ldr), there are the list of available colors. Each color is associated with a number. Obviously, each brick will be associated with a color. A special color exists which allows to define sub-model without specified color. It allows to create a model with many identical sub-model with different colors. The color will be propagated to children of this model. The most of basic bricks use this special color. For others, many bricks have motifs and pictures. Theses motifs are primitives with fixed color. To create new motif, you need a software which manipulates vectorial image (DAT2QP). The color may be propagated by several methods: it depends of many parameters as the file structure. Presently, I don't know the best choice of propagation method.

ghosts
Each ghost corresponds to the same sub-model with a undefined color (except eyes which are white and black). The colors are defined in the model with the four ghosts.

The second point concerns the format files. LDraw has three different extensions MPD, LDR and DAT. In fact, the three types of file use the same format. MPD is the extension of multi-parts document, it aims to group many subparts. LDR is the default extension, it contents the model. DAT is the extension for parts, it concerns basic bricks geometries. In a file, there are many types of primitives, they concern geometries (lines, triangles, quads, optional lines), relative files (children part), and meta-commands (informations, color, back-face-culling,...). So a basic brick is composed of lots of subfiles. For example, the brick 3001 (2x4) is composed of 12 different subfiles (some of them is used many times as studs). Each brick is associated with a big graph. This choice of the structure was certainly due to the memory capacity of computers: bricks use the same primitives, so few different primitives. Today, computers lost lots of time to display a brick by going though graph.

This first post is an overview of LDraw format. So Ldraw is an open format and is easy to use. There are two problems to fix: how should we gain computing time and how can we manage colors.

First article

This is the first article of this blog. Here, I will talk about my first contact with WordPress.

This website is hosted by OVH on a shared server. This configuration suggests the website can't access to the totality of the server capacities. This isn't a problem because this website dones't need a large bandwidth, and the allocated memory space for this website seem sufficient.

WordPress was installed by a service of OVH, so there is nothing to configure. WordPress is a blogging tool which allows to manage a website. It proposes many themes, many website appearances. After many tests, I have chosen the default theme (Twenty Fourteen) because I think it correctly uses the screen (the header is small). However, I have modified two parameters of the formatting of the page. First, the maximum width of the page was 1260px. I have deleted this limit to force the full-page for screens which have a bigger resolution. Second point concerns the text formatting: I prefers 'adjusted' texts.

I have also tested plug-ins to display my Curriculum Vitae, but I wasn't convinced by these tools. Today, I use a PDF viewer, but I search a best way (maybe with style sheets).