Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Design choices in Crafty

Author: Uri Blass

Date: 22:22:57 06/23/04

Go up one level in this thread


On June 24, 2004 at 01:04:01, Dann Corbit wrote:

>On June 24, 2004 at 00:59:01, Uri Blass wrote:
>
>>On June 24, 2004 at 00:01:45, Dann Corbit wrote:
>>
>>>On June 23, 2004 at 23:47:20, Uri Blass wrote:
>>>
>>>>On June 23, 2004 at 21:03:33, Dann Corbit wrote:
>>>>
>>>>>On June 23, 2004 at 20:54:24, Russell Reagan wrote:
>>>>>
>>>>>>On June 23, 2004 at 19:52:45, Ed Trice wrote:
>>>>>>
>>>>>>>If you profile Crafty, you will find something like only 11% of the computation
>>>>>>>is spent on the evaluation routine. Say you were to make this code execute twice
>>>>>>>as fast. Then, overall, the entire program would be only 5.5% faster.
>>>>>>>
>>>>>>>To make a big performance gain, you have to attack the bottlenecks.
>>>>>>
>>>>>>
>>>>>>I agree with that logic. At the same time, I think it should come with a
>>>>>>warning. A lot of times people mistakenly interpret this advice as, "ignore
>>>>>>optimization until the program is operational." I think that by doing that, you
>>>>>>are placing the upper limit on how fast the program can potentially be much
>>>>>>lower than it should be.
>>>>>>
>>>>>>Let's say I write my program, and I ignore optimization issues early on. The
>>>>>>program is now operational, and now I start to work on optimizations. I profile
>>>>>>it, hunt down hot spots, and get to the point where there are no obvious
>>>>>>bottlenecks. The program is still ten times slower than Crafty. Now what? I am
>>>>>>saddled with a poor overall design, and nothing short of a complete rewrite is
>>>>>>going to improve the situation.
>>>>>
>>>>>
>>>>>I don't think I have ever disagreed with any post more than I disagree with this
>>>>>one.
>>>>>;-)
>>>>>
>>>>>Never, never, never, never optimize a program before it is working correctly.
>>>>>And when I say never, I mean not ever.
>>>>>
>>>>>The only exception to this rule is in the choice of algorithms.  There is no
>>>>>sense picking a bad algorithm to start with.  And even if you did happen to pick
>>>>>the wrong algorithm, then it is not hard to change it.
>>>>>
>>>>>Your advice is bad advice.  I hope that nobody listens to it.  Permature
>>>>>optimization does absurdly more harm than good.  For every ounce of benefit,
>>>>>there are a trillion gallons of downside.  When you start programming ANYTHING,
>>>>>including a chess program, write clear, simple code that best expresses the
>>>>>algorithm in the most straightforward manner.
>>>>>
>>>>>Now, let's go farther.  Suppose that you have chosen some fundamentally bad data
>>>>>structures.  If your program is written in an abstract enough manner, it won't
>>>>>matter.  And the more abstract you make it, the less it will matter.
>>>>>
>>>>>My point:
>>>>>1.  Write clear code.
>>>>>2.  Choose good algorithms.
>>>>
>>>>I can say that 2 can be divided to the following steps:
>>>>
>>>>2.1. Write bad algorithm that does the same task as the good algorithm that you
>>>>plan but the implementation of it is relatively simple.
>>>>
>>>>2.2.Improve the bad algorithm.
>>>>
>>>>I use these 2 steps in my attack tables.
>>>>
>>>>First I wrote a very slow algorithm to calculate them from scratch and it was
>>>>more important for me to prevent bugs and later I used the previous code in
>>>>order to help me to debug the program when I changed it to incremental
>>>>update(without incremental update movei could probably search more than 10 times
>>>>slower than it searches today because having loops for every square on the board
>>>>to see if it is attacked from one of 16 directions(8 knight directions and 8
>>>>queen directions) after every move is very slow.
>>>>
>>>>64*16=1024 and it is not all the story because you may need to look for many
>>>>squares in some direction only to find that the square is not attacked from that
>>>>direction so there are thousands of calculations for every node.
>>>>
>>>>I even did not consider to write a chess program without that optimization.
>>>>
>>>>>3.  Write abstract code that hides the implementatiion details when possible.
>>>>>4.  When everything works well, profile it.
>>>>>5.  Speed up the stuff that will benefit from it.
>>>>
>>>>What do you suggest about the question of using global varaibles?
>>>
>>>Global variables are good to have in every program.  Examples in C are stdin and
>>>stdout, which I suspect you use in your program.  However, a variable should be
>>>made global if and only if it HAS to be global.
>>>
>>>Global variables created due to laziness will cause many bad things:
>>>1.  Evil side effects:
>>>int i;
>>>int bar(void)
>>>{
>>>   int accum = 0;
>>>   for (i = 0; i < 5; i++)
>>>      accum += i;
>>>}
>>>void foo(void)
>>>{
>>>   int sum_of_sums = 0;
>>>   for (i = 0; i < 5; i++)
>>>      sum +=  bar();
>>>}
>>
>>I do not use varaibles with no meaning like i as a global varaibles.
>>
>>The question is what about varaibles with clear meaning:
>>
>>I can give examples:
>>1)nodes
>>2)ply
>>3)hply
>
>These are all terrible choices for global variables.
>
>Here are some good choices:
>
>A position hash table
>A pawn hash table
>A configuration object
>
>Why are they good choices?  Because if then different threads need to do some
>chess calculations, they will probably all need to touch the hash tables.  And
>if some threads are inquiring about systems settings, it is good to keep them in
>a single place.
>
>>The question is also what to do when I add varaibles
>>
>>I am not going now to change all the global varaibles that I have to local
>>before WCCC (no time for it) but I think to add to my evaluation using the phase
>>of the game that is defined by the value of pieces of the opponent and to have
>>opening evaluation and endgame evaluation instead of one evaluation.
>
>I agree.  In fact, I would do nothing but test for robustness.  If your program
>has a learning feature, it might be a good idea to play it online against strong
>programs at slow time controls to uncover bugs, opening book problems, and also
>to save problem positions in a local file.

Thanks for the advice.

It is certainly good for top programs not to do significant changes
in the week before WCCC but in my case I still hope to get significant
improvement before WCCC because movei still has a lot of lack of knowledge.

I believe that both evaluation and search can be improved significantly and I
still hope to do some significant improvement before WCCC(In the worst case I
always can use a stable version that promoted to Leo's first division).

I feel that the simplest way to improve the search is to add more global
arrays(the point is that I use also the history of the game in my search
decisions).

Maybe I should add global arrays and not global varaibles.
I already have some arrays that tell me information about history of the game
and I use them for my search decisions.

I will probably try to add more arrays in the hope to use them to improve my
search.

Uri



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.