undo move vs. Position Cloning

[bob]

...
The only advantage for assembly language is none of those, it is purely performance, because we know things about the program that the compiler can't deduce, which lets us optimize better, but which also makes it harder to understand the program later.

In fact assembly language gives you the "power" to optimize better. Because chess is a competitive game and chess programming lead us to competition... having the strongest tools could give you some advantage. At end only doing true games between programs will provide a measure of the goodness of the tools, algorithm, implementation and so on.

The scope of the test reported, based on perft, was done only to show how we can get a faster program even at the first stage of developing. Maybe i was wrong comparing my perft with those of Crafty because my perft use the same procedures of the true program and is "implemented" only throwing away things from alfa-beta (no tree cutting, no hash tables...). I was thinking that even Crafty perft was done in the same way but now you say that is'nt true, so i'm wrong on that.

About the lines of code, Freccia engine is now:

- move generator: 991 lines
- alfa-beta 197
- data + debug routines: 692

For now i think that the program could be understood later, almost by me... but i will say that for sure only after some year from today.

The last aspect is very programmer depending. The same problem becomes from any language, i think.

That's all well and good. But Crafty is around 50,000 lines of C. The primary search, evaluation, and such is well over 5,000 lines of C. Which will turn into 20-30K lines of assembly. _that_ is not so easy to support. Did that in Cray Blitz where we had over 20,000 lines of assembly written solely for speed. But what you gain in execution speed, you lose 100 times over in terms of making changes to the code. In the case of Crafty, I change things on a daily basis. Right in the middle of the search, or in the middle of the evaluation. From experience, that turns into a major effort when using assembly language.

I'm not sure how you would use a normal search for perft. There can be no pruning of any kind. Move ordering is irrelevant. No evaluation. Etc...

[stegemma]

...But then why do you like assembly language programming? It's the simplest of all. Only a small handful of very simple concepts to grasp and the rest comes out of the manual or op-code reference.

I think you actually think simple things are more interesting or you would not avoid the "complexities" of high level languages.

What makes the complexities of a program doesn't derive from language but from algorithms and data definition (and maybe a lot of other things, depending on the program). I'm a C++ programmer, for commercial applications, so i don't avoid high level languages. I can say that i like C++ the same as assembly but for different reasons. In Freccia i try to merge my C++ experience (thinking by class/obiect) with my my way to like assembly (to know exactly what are happening). My first C program was a chess program and some year ago i've started a chess program in C++. Because my first running chess program was in assembly, i don't like at all the poor performance of mine C and C++ experiment, wrote with the same "concepts" as the assembly program have.

Maybe one choose the preferred language based on the first ones that he/her know. I've started from the Texas TI57 SOA, that was nearly like assembly... so assembly like languages are my first love and cannot forget them.

[mcostalba]

The last aspect is very programmer depending. The same problem becomes from any language, i think.

I don't know. When I downloaded Glaurung sources for the first time, after few days I was alreading doing damage on them

And after less then a month I had already crapped up the poor Glaurung in a lot of parts.

To quickly become productive I think it depends 20% on the language of choice and 80% on how clean and elegant the engine is developed. And here I have to say Tord made a really nice toy: I read other sources before to pick Glaurung and I choose it not because of its strenght but because it was well developed and organized in a logical way, easier for me to understand. I choose it by feeling.

And after I choose Glaurung I never turned back again

[stegemma]

...That's all well and good. But Crafty is around 50,000 lines of C. The primary search, evaluation, and such is well over 5,000 lines of C. Which will turn into 20-30K lines of assembly. _that_ is not so easy to support. Did that in Cray Blitz where we had over 20,000 lines of assembly written solely for speed. But what you gain in execution speed, you lose 100 times over in terms of making changes to the code. In the case of Crafty, I change things on a daily basis. Right in the middle of the search, or in the middle of the evaluation. From experience, that turns into a major effort when using assembly language.

I'm not sure how you would use a normal search for perft. There can be no pruning of any kind. Move ordering is irrelevant. No evaluation. Etc...

Mmmm... my program isn't finished yet, so the evaluation function is pratically missing. I think that the final full program will be shorter, in number of code lines, of the whole Crafty. I could verify this before november, when i plan to have finished Freccia.

To convert alfa-beta in perft is an easy task. I use something like this:

Code: Select all

if ALFA
  call CercaMigliore ; call "Find Best Move"
  je ag_finite ; jmp if ended
else
  mov edx, [esi.nEseguita]    ; point to last played move
  lea edx, [edx+size Mossa]   ; next move
  cmp edx, [esi.nMosse+size Nodo]  ; it is the last one?
  jge ag_finite ; jmp to end
endif

At first stage i've filled alfa-gemma with this conditional statements, only to have a working perft. As you can imagine, i've soonly duplicated the alfa-beta, throwing away selected part of code, so in fact i have two separated procedures with the same structure and only the relevant parts active in each one. Still, my perft is alfa-beta without cutting. When alfa-beta will be increased with genethical code, hash and other stuff, they will be more different from now. The called procedures, as the move generator, check checking and any other stuff will remain the same for both procedures. If i wish a faster perft i could think perft as a different procedure from alfa-beta, giving very faster program (just for perft) but that does'nt give me any advice of the performance of the true one, that is what i'm expecting from perft. Still, if perft is not implemented in changing regular alfa-beta maybe it is a little less usefull, for the purpose of perft of verifying the perfctness of our move generator?

(a fastest perft could be done, for sample, not storing any move, as the move generator does, but executly them as soon as they were found as legal or pseudolegal; this could give a perft about 2 or 3 times faster since now)

[bob]

...That's all well and good. But Crafty is around 50,000 lines of C. The primary search, evaluation, and such is well over 5,000 lines of C. Which will turn into 20-30K lines of assembly. _that_ is not so easy to support. Did that in Cray Blitz where we had over 20,000 lines of assembly written solely for speed. But what you gain in execution speed, you lose 100 times over in terms of making changes to the code. In the case of Crafty, I change things on a daily basis. Right in the middle of the search, or in the middle of the evaluation. From experience, that turns into a major effort when using assembly language.

I'm not sure how you would use a normal search for perft. There can be no pruning of any kind. Move ordering is irrelevant. No evaluation. Etc...

Mmmm... my program isn't finished yet, so the evaluation function is pratically missing. I think that the final full program will be shorter, in number of code lines, of the whole Crafty. I could verify this before november, when i plan to have finished Freccia.

To convert alfa-beta in perft is an easy task. I use something like this:

Code: Select all

if ALFA
  call CercaMigliore ; call "Find Best Move"
  je ag_finite ; jmp if ended
else
  mov edx, [esi.nEseguita]    ; point to last played move
  lea edx, [edx+size Mossa]   ; next move
  cmp edx, [esi.nMosse+size Nodo]  ; it is the last one?
  jge ag_finite ; jmp to end
endif

At first stage i've filled alfa-gemma with this conditional statements, only to have a working perft. As you can imagine, i've soonly duplicated the alfa-beta, throwing away selected part of code, so in fact i have two separated procedures with the same structure and only the relevant parts active in each one. Still, my perft is alfa-beta without cutting. When alfa-beta will be increased with genethical code, hash and other stuff, they will be more different from now. The called procedures, as the move generator, check checking and any other stuff will remain the same for both procedures. If i wish a faster perft i could think perft as a different procedure from alfa-beta, giving very faster program (just for perft) but that does'nt give me any advice of the performance of the true one, that is what i'm expecting from perft. Still, if perft is not implemented in changing regular alfa-beta maybe it is a little less usefull, for the purpose of perft of verifying the perfctness of our move generator?

(a fastest perft could be done, for sample, not storing any move, as the move generator does, but executly them as soon as they were found as legal or pseudolegal; this could give a perft about 2 or 3 times faster since now)

I can't interpret the above. There's no way to add _one_ test and convert a real alpha/beta search using things like extensions, reductions, forward-pruning, null-move, hash tables, repetition check, PVS-search, quiescence search, etc. (not to mention parallel search) into a simple perft test that does zero pruning, zero extensions, zero reductions, zero q-search, etc. Perft is a pure depth-first walk of the tree, no moves excluded, nothing extended, etc. Everything goes to a fixed depth.

[stegemma]

...I can't interpret the above. There's no way to add _one_ test and convert a real alpha/beta search...

Sorry, mine was just a sample, maybe i was explaining myself the wrong way. Obviously there's not just ONE "if ALFA" directive but one each time it is needed. In my program (that is very simple, for now) it works, in other one i can't know. If the alfa-beta is completed by the other thing you've mentioned then the final code could be so bad (a lot of if else endif) that a separated perft is of course the better solution. Even in my program now i have a separated perft.

[stegemma]

...To quickly become productive I think it depends 20% on the language of choice and 80% on how clean and elegant the engine is developed. And here I have to say Tord made a really nice toy: I read other sources before to pick Glaurung and I choose it not because of its strenght but because it was well developed and organized in a logical way, easier for me to understand. I choose it by feeling.

And after I choose Glaurung I never turned back again

I think that this can confirm my idea that is more important the programming style than the language used. Maybe if Glaurung was written in assembly (i don't know what is Glaurung but i suppose that it is in C) you could need more time, to learn about it, but the more time will be rewarned by more speed (IMHO). Another interesting thing is that you don't want to search for something else... as i love assembly because was my very first programming language (i know: Glaurung is a chess program not a language).

While learning about neural networks and genetical algorithms i've found an interesting concept, that i hardly can explain in english. The concept is that the search that a GA does is like the search of the higgest mountain on a land. When you find a mountain, you try to climb it, just to see if it is the higgest. The GA can find an high mountain but nothing grant that it is the higgest one. When it start climbing those mountain, all the population "convert" to that solution and is hardly to make them to change solution and axplore something else. That's seems to happen in chess programming, IMHO: there are well known algorithms that everybody think about the better ones. The only work seems to find variations on those algorithms, not to find and study new ones. The same is for programming language. I think that chess programming has almost rechead the top of the actual mountain/solution and it's very very hard to scroll down everybody to make them see that (maybe!) that's not the higger one. But maybe i'm wrong and i'm climbing the wrong mountain...

[mcostalba]

Another interesting thing is that you don't want to search for something else... as i love assembly because was my very first programming language (i know: Glaurung is a chess program not a language).

While learning about neural networks and genetical algorithms i've found an interesting concept, that i hardly can explain in english. The concept is that the search that a GA does is like the search of the higgest mountain on a land. When you find a mountain, you try to climb it, just to see if it is the higgest. The GA can find an high mountain but nothing grant that it is the higgest one. When it start climbing those mountain, all the population "convert" to that solution and is hardly to make them to change solution and axplore something else. That's seems to happen in chess programming, IMHO: there are well known algorithms that everybody think about the better ones. The only work seems to find variations on those algorithms, not to find and study new ones. The same is for programming language. I think that chess programming has almost rechead the top of the actual mountain/solution and it's very very hard to scroll down everybody to make them see that (maybe!) that's not the higger one. But maybe i'm wrong and i'm climbing the wrong mountain...

The assembly mountain is too steep for me.

BTW regarding looking at different mountains, have you tried to rewrite your alghoritms in C (exactly transaltion) give them to a good compiler and see what happens ?

Perhaps you could find some surprises.....

[stegemma]

...BTW regarding looking at different mountains, have you tried to rewrite your alghoritms in C (exactly transaltion) give them to a good compiler and see what happens ?

Perhaps you could find some surprises.....

I've wrote in the past something similar in C (my very first C program was in fact almost the same of my assembly chess program, but rewritten, not exactly translated). I could try but already know the result. Freccia makes large use of some assembly thing that you don't have in C, specially processor flags. You can avoid them, in C, but you'll get more compiled instructions than in assembly.

Maybe when Freccia has been finished (before november, i hope... because i have a tourney to play) i could try a C translation and make Freccia Assembly play against Freccia C. The one who'll win will be the candidate for Freccia 2 project

[Fguy64]

This thread got a bit confused because the both of you are talking about different things.

The fastest is to undo the changes to large data structures, and clone the small ones. You need to think about the trade off in effort between undoing a change and copying it back.

Undoing moves should be faster than copying 4.5K of memory. If it's not, something is wrong.

What Marco describes is a small optimization for the case where you copy a datastructure (to have only 1 copy instead of 2).

OK I didn't look closely at this entire thread, so pardon if i am going over old ground. In search I do a form of cloning I suppose. But I don't actually clone the position and make a move in the clone. It just seemed that most of the work required to update a position , including game state variables, was being done by my move legality routine. So it seemed a relatively small matter to use this work to assemble a new position.

All of this in light of the current limitations of my program, such as no hash table. Also, the effect of storage methods on performance is not one of my strengths, although that is changing fast enough.