Author: Tony Werten
Date: 23:31:43 11/16/05
Go up one level in this thread
On November 16, 2005 at 15:18:56, Frederik Tack wrote: >On November 16, 2005 at 02:03:42, Tony Werten wrote: > >>On November 15, 2005 at 18:18:04, Frederik Tack wrote: >> >>>On November 15, 2005 at 04:33:46, Tony Werten wrote: >>> >>>>On November 14, 2005 at 19:20:59, Frederik Tack wrote: >>>> >>>>> >>>>>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. >> >>Increment a counter every time you capture the king and be surprised :) >>This was the reason I wrote a special move generator when in check. > >I actually followed you advice and tested it out. I am surprised in the sense >that it happens a lot less than you and me thought. > >In a typical opening position the result was +- 0,5% of the nodes. >In a typical midgame position (with king still in the center of the back row) >the result was +- 1%. >In a typical endgame position (with the king exposed in the center of the board >and enemy rook, bishop and knight and 3 pawns on the board) the result was +- >3%. > >When i think of it, these low percentages aren't so surprising at all, since the >king captures are always put at the end of the movelist by my move generator, so >in most cases, they are cut-off during alpha-beta search. I'm puzzled. Capturing a king gives an immediate cutoff. It should be searched first. Searching it last means you have wasted a lot of nodes. When you move the kingcapture forward, and then count, you will get about 25%. It means (since you only count kingcaptures in 3%) that in 22% you have searched part of a tree that you could have avoided. To me this sounds like you basicly doubled your branchingfactor, to save you from doing InCheck. But maybe I'm not getting it. Tony > >>> >>>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. >> >>I understood that you generated a complete attacktable before you notice being >>in check. Maybe you also do it for InCheck, but you don't need to. >> >>If you weren't in check before the move, and the move isn't a king(castle)move >>or EP capture, you only have to check if a) a queen could attack your king if it >>is on the fromsquare of the last move and b) if there is a slider behind the >>fromsquare (capable of attacking the king) in the same direction as >>kingsquare->fromsquare. >> >>Most of the time a) will fail. >> >>When you are in check, most moves will be illegal and having a special >>out_of_check generator will be more efficient. ( to help you prevent a bug I >>noticed in my engine: sliding a pawn between the checking piece and the king >>could be a promotion if the king is on the opponent back row) >> > >I don't always generate a complete attack table. If i detect a check by one type >of piece, i don't generate the rest of the attack table. However, since most of >the times, the king isn't in check, indeed the full attack table is generated. >This isn't as time consuming as you think because i don't actually generate an >attack table, but an attack bitboard. Most of the logic is precomputed in >constants and the attack bitboard is produced by some simple logical operations. > >Your method is certainly interesting. I'll try it out and make a comparison when >i find some time. > >Tx > >Fred
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.