Author: Uri Blass
Date: 23:19:31 06/23/04
Go up one level in this thread
On June 24, 2004 at 01:22:57, Uri Blass wrote:
>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
I can add that what I do not plan to try to do is changes in the structure of
the search algorithm(it is too dangerous) but I hope that changing the boolean
conditions of pruning or extension can lead to improvement and another hope for
improvement is in the evaluation.
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.