Author: Frederik Tack
Date: 15:18:04 11/15/05
Go up one level in this thread
On November 15, 2005 at 04:33:46, Tony Werten wrote:
>On November 14, 2005 at 19:20:59, Frederik Tack wrote:
>
>>On November 12, 2005 at 18:19:47, Tord Romstad wrote:
>>
>>>On November 12, 2005 at 05:48:14, Frederik Tack wrote:
>>>
>>>>I have to disagree on that one. It's better to take performance into account
>>>>from the beginning and make a good design for your program. If you only do it at
>>>>the end, you might find yourself unable to do the neccessary performance
>>>>improvements because your design doesn't allow it anymore.
>>>
>>>This reasoning is flawed. The risk that you wil ultimately be unable to
>>>do the necessary performance improvements because your design doesn't
>>>allow it is much *bigger* if you heavily emphasise low-level optimisation
>>>from the beginning. When the program is young, you don't know how it
>>>is going to evolve, and your ideas of which problems you will find and
>>>where the bottlenecks in the finished program will be are very likely to
>>>be incorrect. You will end up optimising your data structures for what
>>>you perceive as problems early on, and these early optimisations will
>>>come back to haunt you later when you face all the *really* difficult
>>>problems which you cannot imagine yet.
>>>
>>>The way to avoid painting yourself into a corner is to make an effort
>>>to make your low-level algorithms and data structures as simple and
>>>flexible as possible, even at the expense of some speed. Try to keep
>>>things fluid, and to make it easy to rip out the low-level code and
>>>replace it with something very different when the need arises. When
>>>you have a good search and eval, no serious bugs, and no very good
>>>idea about how to proceed, you can finally consider profiling your code
>>>and try to optimise some of the bottlenecks.
>>>
>>>Regarding your question at the beginning of the thread: I also use
>>>a pseudo-legal move generator (except when in check, when I use
>>>a special check evasion generator which only returns legal moves).
>>>However, I always check the moves for legality before I make them.
>>>Stalemate detection works as follows:
>>>
>>>int search( ... ) {
>>> ...
>>> int legal_moves = 0;
>>> move_list = generate_moves();
>>> for(move in move_list) {
>>> if(move_is_legal(move)) {
>>> legal_moves++;
>>> make_move(move);
>>> search( ... );
>>> unmake_move(move);
>>> }
>>> }
>>> if(legal_moves == 0)
>>> return STALEMATE_VALUE;
>>> ...
>>>}
>>>
>>>This works fine, and has no measurable cost whatsoever.
>>>A little flaw is that I cannot detect stalemates in the
>>>qsearch, but I can live with that.
>>>
>>>Tord
>>
>>Both ways are possible i guess. I like to work bottom-up, make the smallest
>>components first, test them toroughly for bugs and performance, then combine
>>them in to bigger components, optimize performance again. That is just the way
>>it works best for me.
>>But anyway, we are drifting away from my original point here, which is that i
>>find it a complete waste of resources to use legal move generation just to
>>detect stalemates, especially since stalemates only occur during endgame.
>>
>>Btw, the move generator that you describe above as being a pseudo-legal move
>>generator is actually a legal move generator. For every generated move, you
>>execute the move_is_legal function. Wether you execute this during move
>>generation or during search makes no difference.
>>
>>My algorythm is really pseudo-legal. The first lines in my search algoritm are
>>as follows :
>>
>>function Negamax(PositionPtr: PPosition; Depth: integer; Alpha, Beta:
>>TEvaluation): TEvaluation;
>> if abs(PositionPtr^.Material) > (evKing - 99999) then Result := - evKing
>> else if Depth = 0 then Result = Evaluate(PositionPtr)
>> else begin ...
>>
>>I never test if the king is in check. In the first line i just check the
>>material balance (which is incrementally updated during move generation). evKing
>>is the value of the king which is the maximum integer value. If the balance
>>indicates that the king was captured i just return the value -evKing which means
>>checkmate.
>
>Did you check how often this happens ?
>For every time it happens, you make a call to search again, and a call to
>"generate captures".
I estimate this happens for less then 5% of the nodes. It is still better to
search an extra ply for 5% of the nodes then to execute 'incheck' for 100% of
the nodes. However, i just learned i don't have to execute incheck for all the
moves (See below).
If this is more effecient than your InCheck code, you
>should rethink the InCheck code.
>
>Typically, InCheck should hardly show up when you profile.
There's nothing wrong with the coding of my 'incheck' function. However, as Uri
explained in another post, the problem is indeed that instead of just generating
moves, i also test for 'incheck' during move generation. If i would do this
during search, i would not have to execute incheck for the remaining moves when
a fail high occurs. So actually i was wrong in my previous post when i said
there was no difference between executing 'incheck' during move generation or
search.
Tx for the reply!
Cheers,
Fred
>
>Cheers,
>
>Tony
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.