Author: Uri Blass
Date: 09:53:02 06/25/04
Go up one level in this thread
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
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.