Author: Uri Blass
Date: 14:02:37 06/27/04
Go up one level in this thread
On June 27, 2004 at 04:50:57, Volker Böhm wrote: >On June 25, 2004 at 12:53:02, Uri Blass wrote: > >>On June 25, 2004 at 12:38:59, Uri Blass wrote: >> >>>On June 25, 2004 at 11:51:01, Volker Böhm 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 >>>>10 Times, are you sure???? >>> >>>More than it. >>> >>>>In My experience it´s got even 3 times faster (with no eval but material) for >>>>the following reasons: >>>>1. Incremental attack tables need an "undo". Thus allways changing the >>>>attack-tables twice for every move (copying the attack tables is a little >>>>slower). >>> >>>I always had an undo but only the makemove was very slow so this is not >>>the reason that it was very slow. >>> >>>>2. Many moves are made by pieces that may move very much (example queen). When I >>>>move a queen I have to remove it´s attack to 8 direction, move it and add it to >>>>8 direction. >>> >>>Yes but when you calculate it for every square you need to look at 16 directions >>>for every square in the board. >>> >>>64 squares*16 directions and for the directions that are not knight directions >>>you often has a lot of empty squares. >>> >>>You have thousands of calculation to do. >>> >>>> >>>>Is your factor "10" tested or just an opinon? If it is tested I would like to >>>>get a idea how you update your attack-tables that fast - perhaps you can tell >>>>me. >>> >>>I do not think that the secret is updating the attack tables very fast but doing >>>everything very slow at that time. >>> >>>Remember also that I did not have piece list when I started. >>> >>> >>>>I get about 1,2 million nodes per second on a celeron 1,3 GHZ in a complex >>>>situation with a perft search (building attack-tables incrementally and all >>>>other "set-move stuff" as zorbrix - keys, piece-tables, material sum, ...). >>> >>>When I started I was not close to that speed and my perft was very slow. >>>I doubt if you can get 1.2 million nodes with the information about the >>>directions that every square is attacked without incremental move generator. >>> >>>The information that I get is: >>>1)32 bit number that tell me for every square the directions that it is attacked >>>by white and the directions that it is attacked from black >>>2)for every direction what is the attacking square from that direction. >>> >>>It is impossible to do it fast without a piece list when for every square you do >>>a loop in all directions to find the directions that pieces attack it. >>>When you find a piece it is not the end of the work for the square and direction >>>and you need to check based on the type of the piece if there is an attack. >>> >>>Uri >> >>I can add that the reason that I have fast perft is that I have legal move >>generator so I do not need to make the last move because I know that it is >>legal. >> >>The job of the attack tables is to allow generating list of legal moves. >> >>If I count only move that I make with no evaluation I will probably get less >>than 1.2 M nodes per seconds even if I do no evaluation. >> >>The make move function also update the attack tables and the pin arrays so I can >>look later in a table to find if a piece is pinned or if the king go to attacked >>square so I can be sure of the legality of a move before I make it. >> >>Uri > >Hi, > >for non incremental attack tables you should not move from 64 in 16 directions. >Just add the attack for every piece on the board. You are right but I did it in an non optimal way at that time. It is not important now because now I have incremental update and I do not expect to earn something from getting rid of it for a non incremental update. 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.