Author: Volker Böhm
Date: 01:50:57 06/27/04
Go up one level in this thread
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. With a full board it is 2 * 8 directions (Queens) 8 * 4 directions (Rook + Bishop) 8 * 8 Positions (Knight, King) and 16 * 2 Positions (Pawns). This is not that slow (sure it is slower than incremental generation - I mesured about 2,5 times slower in a complex middlegame position). I am generating incrementally attack tables that knows from witch direction they are attacked (without color information, thus 8 bit) and a 2*8 Bit Piece Signature for the attack (8 Bit for each color). In total 24 Bit. I don´t have the information where the piece is exactly that attacks the field. With the direction bit it is usually quite fast to find (on average I have to look at 2,5 squares - in my tests). Thus storing the attack position is too costly for my. Greetings Volker
This page took 0.01 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.