The official Fatica Labs Blog! RSS 2.0
# Saturday, December 3, 2011

Since I had an amazing number of views on my previous article about my chess engine rewriting and publishing it OS, I decided to extend a little bit more the discussion. Unfortunately this is not a brand new argument, since there is a lot of good articles on the web, but in order to me some missing point exists: if you start reading the code of a fully fledged engine, even in C#, you will probably get lost in a big mesh of heuristics and optimizations without really get what’s really happens. By contrary, if you read the literature you will find a lot of pseudo code but nothing really working, and something that is a detail for the pseudo code, can be really difficult to implement in real life just to see what’s happens. Here we will show how a plain algorithm from the literature behave in it’s essence, solving a real chess problem. Of course this will not works in a real playable engine but it has a big advantage: it is *understandable* and can be the starting point to optimize, so by gradually reaching the fully fledged engine we eventually get each single steps better.

Which algorithm use ? Chess engines uses some flavor of an algorithm called MiniMax, with an immediately ( even for a simply case ) necessary optimization called Alpha Beta Pruning. This is what we will show by example here below. So what exactly is MiniMax ? It is an algorithm that works by producing a tree of the possible games in which each node is a possible status and each arc that produce the transaction is the move ( the decision ) the player can do. At each node we can weight the result of the player Mini and the player Max, Mini win if that value is little, and Max win when the value is high, so Mini want to *minimize* a score function, and Max want to maximize it. Since chess is a symmetric game, we can say that a good result for Mini is a bad result for Max and vice-versa. This lead us to a single evaluating function, with sign changed depending on the player. This simplification is referred in literature as Negamax.  Lets see an example of a game tree, by starting from a specific chess position (2rr3k/pp3pp1/1nnqbN1p/3pN3/2pP4/2P3Q1/PPB4P/R4RK1 w - - 0 0):


The position is our root node, and a portion of the resulting tree is:


Well it is a portion, its impossible to draw it all even for just a few play, it is even impossible computationally enumerate all nodes eve for a few ply, because of the high branching factor chess has. The branching factor is a measure on how many nodes are generated from a root, in other word, in chess is an average count of the possible moves a board has. For chess this number is about 35, and so we have, for each ply an exponentially increasing number of nodes like 35^n, where n is the number of ply. Let’s consider too why it is so important having a correct move generator: just a single wrong move somewhere will mess an enormous amount of nodes.






average number of nodes per ply in chess:

1 35
2 1225
3 42875
4 1500625
5 52521875
6 1838265625

Of course this is just average data, can be even worst in some situation. You can always know the exact count of nodes by using the perft test contained in the same project, but I suggest you to start with a 5/6 ply and see how long it takes befor tryng 8/9 ;)

So some optimization is necessary since such an exponential explosion can’t be managed with any kind of CPU. The only game I know in which generating all the tree is probably tic-tac-toe, but for chess is absolutely not the case. So we introduce alpha beta pruning in our algorithm, but how can we prune some nodes despites to other? let’s have an example with the same position shown above, and suppose we move the Knight in c6 ( Nxc6), the black can catch it with the rock, or with the pawn, Rxc6 and  bxc6 respectively. In an alpha beta pruning scenario as soon such a move refute the white move, ie the move give a gain better than the current opponent better score, the search stops at that level. This is an enormous gain in term of performance, the only draw back is that we have just a lower bound of the actual score of a position, so we don’t really know if we can do better, but we stay on the fact that we can do enough. How this is achieved by code? Let see what we need:

  1. A way of score the position: material balance is more than enough for this sample.
  2. An algo that traverse the algo keeping track of the best score for a player ( alpha ) and for the opponent ( beta )
  3. A way to sort the move ordered so the “strongest” are seen first, the weak later.

Point 1 is easy, just give some value to each piece type, and sum it considering positive the white if the white is the player or vice-versa. The algorithm we will see soon, but the tricky part is the 3). As you probably guess, having good move navigated first, increment the changes of stops the search ( the so called beta-cut off ) with a dramatic performance increment. So the first real heuristic that will give your engine strength and personality is that function. In the example we will use a very basic ordering strategy, that put all promotion and good capture in front, all the “other” moves in the center, and the bad captures at the end. ( a good capture is one in which the catcher has less value or equal to the captured ).

So let’s show the “Vanilla” algorithm. Why “vanilla” ? because a real chess engine extends a lot this concepts,and add lot of other functionality to make the engine responsive, but the one shown do the job and it is ( hopefully ) as clear as understand as the pseudo code, whit the difference that it is working code you can inspect and debug and use for learn:

The interesting portion are the Search function. I used delegates to extract the non algorithm related code so it appear simple as pseudo code, but it is working. Then I wrote a test case using this search function here:


       public void TestQg6()
           using (var rc = new RunClock())
               var engine = new SynchronEngineAdapter(new SimpleVanillaEngine(7),
                   "2rr3k/pp3pp1/1nnqbN1p/3pN3/2pP4/2P3Q1/PPB4P/R4RK1 w - - 1 1"
               Assert.AreEqual("g3g6", engine.Search());
               Console.WriteLine("Elapsed milliseconds:" 
                   + rc.GetElapsedMilliseconds());



The code of the search is called by the class SimpleVanillaEngine, this is just a wrapper that inject the proper move generation  calls and evaluation/ordering functions. That test works in about 40 sec on my laptop, that is unacceptable for a real engine, but satisfying because… even if the code is simple, it report the correct answer, why can I say so ? because the board I proposed is some sort of standard test  for chess engines. Please note that the correct move Qg6 is reported in the test as g3g6 since our engine does not yet supports the human algebraic notation, but the move as you can guess is equivalent. This case is important because it show how an apparently wrong move can lead in a win if we look deep enough.

Well if interest in the project continue as it started, I will blog again on how to move this in a real engine.

Saturday, December 3, 2011 1:03:44 PM (GMT Standard Time, UTC+00:00)  #    Comments [0] - Trackback
Chess | CodeProject | CSharp | Games

# Saturday, November 26, 2011

I decide to publish my chess engine plays on bitbucket. Well it is almost a redo from scratch of a complete but buggy chess engine I wrote in the past that I decided to rewrite just because it was difficult to stack into the old code what I learned. The version present when I write this post contains just the move generator and the complete test for it ( I used an other nice engine: roce to compare my perft test results against. What is a perft test ? Well it is a test to prove our engine produces, from a starting board, all the possible different boards in a certain number of ply, accordingly to the chess game rules. This test also give an idea on how fast is the strategy we use to generate moves, even if this can affect just in part the overall performance of the alpha/beta pruning, we should not write a slow blobby monster. Lets see below a session of the test working:


The strange string showing the position are board situations expressed in FEN Notation, that is almost the standard notation we use to talk about board situations. How many test does FelpoII move generator passes ? Well here is the file containing the FEN boards, with the depth plies move counts shown, there is a lot of positions, even tricky and generally challenging positions ( in term of rules ).

What is the performance ? Since almost all chess engine are written in C++ or in C, can a C# engine works at the same level of magnitude of performance ? Here below the performance we have for the starting position:

Depth: 6 119060324 moves 5,34 seconds. 22283422,048 Move/s. Hash Hit=1400809

The same test with roce ( that is a C++ chess engine ):

Perft (6): 119060324, Time: 4.208 s

So almost the same, that is good if we remember that we wrote in C# Smile We just used a little hack: as you probably know ( or will know if you will start playing with chess engines development ) chess engines uses hash tables to store information about a board ( by using hashes against Zobrist Keys ) this tabled is sored in an unamanaged big memory array, this achieved a really sensible increase in performances.

Well some more details about the engine:

  • It uses a 0x88 board representation
  • It uses object oriented code ( so it is easier to understand compared to traditional C++ engines )
  • The internal random numbers for the zobrist key are generated by a Mersenne Twister Generator, that really solved some nasty bug due to wrong hash conflicts when I used the standard random algo of c#.
  • It uses a trasposition table in unmanaged memory to increase performance.
  • It has a performance comparable ( at least in move generation ) with traditional C/C++ engines


What we can do next ?

Complete the engine with a good working Negamax alpha – beta pruning algorithm.

What can we do with the code as is ?

We can use the move generator as is to validate game moves in a two human player UI, or generating fancy images from FEN positions, write a WPF ( another ) chess board ( winboard compatible? so a lot of engines are already written for it) and so on.


Saturday, November 26, 2011 10:11:13 AM (GMT Standard Time, UTC+00:00)  #    Comments [3] - Trackback
CodeProject | CSharp | Games

# Saturday, August 14, 2010

Fine delle vacanze, e fine del “giochino” passatempo fatto con Microsoft XNA Game Studio. In pratica ho aggiunto la possibilità di avere un modo match o un modo “training”, e finalmete c’è un sistema di punteggi ed una certa “Game logic” in termini di palle da giocare, punti moltiplicati per sponda, penalità se si tocca il computer o la sedia, etc. Il gioco è giocabile.


Saturday, August 14, 2010 8:47:49 PM (GMT Daylight Time, UTC+01:00)  #    Comments [0] - Trackback
Games | XNA

# Thursday, July 29, 2010

La cosa bella di saper programmare è che la vastità di cose che si possono fare non ha praticamente limiti. Uno dei task più divertenti è sicuramente la scrittura di un videogioco: si spazia dalla conoscenza pura di un linguaggio, alla matematica 3d, all’arte e, ovviamente l’idea. La parte matematica, per chi si interessa dell’argomento, è ben definita, basta leggere uno o più classici, tra i quali segnalerei, per averne usato ed abusato OpenGL SuperBible, Mathematics for 3D Game Programming & Computer Graphics, ed altri che per legami con qualche particolare framework sono oggi anacronistici. Dal punto di vista artistico, un gioco ha texture, modelli suoni, musiche… tutte risorse facilmente reperibili, anche in Open Source, anche gratuitamente – se non si vuole fare un gioco da vendere – in rete. Il problema di quasi tutti i framework era che nessuno forniva metodi per caricare diversi tipi di “asset”. Fortunatamente questo gap è stato colmato da XNA Game Studio. Basato su DirectX – Direct3d è facile ed intuitivo da usare per chiunque abbia visto un po’ di grafica 3d, ma offre veramente dei grandi vantaggi in termini di import di risorse  (texture, suoni, modelli 3d in svariati formati, etc ). In pratica basta “compilare” l’asset e poi chiamare Load<tipodellasset>(“Nome”) ed il gioco è fatto.

Ciò detto, per fare un gioco ( che per il programmatore è più divertente che giocarlo ), serve un idea: o si fa il solito clone, o si trae ispirazione da qualcosa… nel mio caso, negli uffici di una delle ditte in cui ho lavorato, c’erano delle putrelle a vista: a qualcuno venne l’idea di lanciare una pallina da tennis e di bloccarla con bello stile nello spazio che la putrella crea con la sua doppia “T”. Al dil à dell’idiozia della cosa, e di quanto ancor più idiota sia pensare di creare un videogame con quell’argomento, ecco nascere “Putrella ! ( The Game)”. La stanza è un po’ claustrofobica, il monitor è anch’esso allietato dallo stesso videogame, quasi a citare una più famosa scena che compariva su un disco del 1969… 

Difficile da spiegare… ma vediamo qualche screenshot:


Un bel freccione verde fosforescente per scegliere dove tirare la pallina. Per inciso la pallina è una mesh sferica disegnata con Milkshape, e la texture invece è gentilmente offerta da google maps. La strana scriita in greco sulla pallina invece…

Ovviamente si può modificare la posizione di lancio e anche lo “Ziembolo” che è un piemontesismo per dire “Spin”






Beh, con lo spazio si decide la forza, e in altro a destra compare un decanewtonmetro un po’ old fashion: si tratta in realtà di una immagine di un milliamperometro corretta, la lancetta invece è una texture di una linea che viene fatta ruotare per simulare uno strumento analogico. Con due stupidaggini l’effetto è alquanto realistico.






Non sempre si fa putrella, anzi per la verità non lo si fa quasi mai: di solito la pallina cade, fa qualche rimbalzo e la storia finisce li… Già, ma come rimbalza una pallina ? Per questo ci viene in aiuto quello che si chiama engine fisico, ovvero uno strumento software che ci permette di simulare un mondo di corpi rigidi, data una descrizione del suo stato iniziale e delle forze applicate ai vari elementi. Io ho scelto OOPS. In realtà è ancora un progetto giovane, ha qualche problemino, ma è fully managed, facilissimo da usare, e per quello che dovevo fare bastava. Come è modellato il mondo ? Niente di speciale, la pallina è, nella “lingua” di OOPS una CollisionSphere, I muri sono dei CollisionPlane, e tutto il resto, putrella compresa, delle CollisionMesh. Ah, dimenticavo, la putrella l’ho disegnata con MilkShape, mentre le altre paccottiglie ( sedia, scrivania, computer ) sono modelli free presi in rete.




E’ difficile fare putrella, un po’ più facile è fare il cesto ( bin ). Anche questo è fatto con MilkShape. Visto che Milkshape non supporta la CSG ( Constructive Solid Geometry, ammazza che parolone ) bisogna ingegnarsi , facciamo due tronchi di cono, li infiliamo uno dentro l’altro, e a quello + interno cambiamo l’ordine dei vertici, semplice e banale, nonchè funzionante.





Ancorchè difficile, prima o poi ci si riesce. Ma chi cambia l’inquadratura ? Molto semplicemente, quando la pallina rallenta, la Camera ( anche qui un concetto 3D, la camera è l’unione della ViewMatrix e della ProjectionMatrix ) da fissa si trasforma in una chasing camera. Per evitare movimenti troppo bruschi, I vettori sono interpolati in modo da avere una prospettiva che gradualmente si avvicina alla palla.





Bene in pratica cosa ho dovuto scrivere per fare questo gioco ? Molto, molto poco. Sempre di più nella programmazione bisogna saper scegliere e fare leva sulle cose buone già costruite, ed aggiungere un piccolo contributo di qualità, che altri possano usare. In questo caso la cosa che ho aggiunto penso possa essere questa.

Thursday, July 29, 2010 10:24:17 PM (GMT Daylight Time, UTC+01:00)  #    Comments [0] - Trackback
Games | XNA

My Stack Overflow

Send mail to the author(s) E-mail

profile for Felice Pollano at Stack Overflow, Q&A for professional and enthusiast programmers
About the author/Disclaimer

The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

© Copyright 2021
Felice Pollano
Sign In
Total Posts: 157
This Year: 0
This Month: 0
This Week: 0
Comments: 140
This blog visits
All Content © 2021, Felice Pollano
DasBlog theme 'Business' created by Christoph De Baene (delarou) and modified by Felice Pollano