Search algorithm in it's simplest forum

[MahmoudUthman]

Kevin Hearn, thanks.
I'm implementing MVV/LVA as advised by you, I made a new generator for captures that places captures into five different arrays {Queen(p,n,b,r,q),Rook(p,n,..),Bishop(p...),Knight(p...),Pawn(p...)},then merges the five "in the same order" into the final array that will be used as the ordered captures in the search, but I don't know where to place promotions, should I place captures and non captures promotions ahead of capturing a queen by pawn (as the first choice ) or in the end of queen captures ?
if MVV/LVA 's logic is based on material difference shouldn't that be the right order, since Promote To(Q)=+Q , Capture(Queen using Piece)=+Q-(0 or piece) if the queen was protected ?
And Should MVV/LVA order Change at Endgame since the king becomes more valuable attacker ?
http://en.wikipedia.org/wiki/King_(che ... _gameplay

As an assessment of the king's capability as an offensive piece in the endgame, it is often considered to be slightly stronger than a bishop or knight – Emanuel Lasker gave it the value of a knight plus a pawn (i.e. four points on the scale of chess piece relative value) (Lasker 1934:73). It is better at defending nearby pawns than the knight is, and it is better at attacking them than the bishop is (Ward 1996:13).

[kbhearn]

Kevin Hearn, thanks.
I'm implementing MVV/LVA as advised by you, I made a new generator for captures that places captures into five different arrays {Queen(p,n,b,r,q),Rook(p,n,..),Bishop(p...),Knight(p...),Pawn(p...)},then merges the five "in the same order" into the final array that will be used as the ordered captures in the search, but I don't know where to place promotions, should I place captures and non captures promotions ahead of capturing a queen by pawn (as the first choice ) or in the end of queen captures ?
if MVV/LVA 's logic is based on material difference shouldn't that be the right order, since Promote To(Q)=+Q , Capture(Queen using Piece)=+Q-(0 or piece) if the queen was protected ?

Your eval probably already evaluates the pawn on the seventh as a few pawns, and the promotion square may well simply be protected. I could see an argument for ordering =Q after ?xQ but before ?xR. I could also see an argument for not including the promotion at all in qsearch and leaving that for the real search to deal with. One of the rationales for MVV first is that you're taking away pieces that can take your stuff back while simultaneously making it harder for your opponent to find a capture of sufficient value to keep pace. If you want to order by expected material difference, that'd be best done by SEE instead of MVV-LVA, but i believe in typical cases MVV-LVA converges faster (i.e. if there's a queen swap (QxQ PxQ no material won) it's usually better to get that out of the way first to reduce the number of captures before going after the sequence that wins an exchange since the tree is smaller with the queens gone.

And Should MVV/LVA order Change at Endgame since the king becomes more valuable attacker ?

The king is the most valuable attacker since you can't afford to lose him. Since you're already legality screening i could see potentially moving his captures around, but it's really not that big a deal.

http://en.wikipedia.org/wiki/King_(che ... _gameplay

As an assessment of the king's capability as an offensive piece in the endgame, it is often considered to be slightly stronger than a bishop or knight – Emanuel Lasker gave it the value of a knight plus a pawn (i.e. four points on the scale of chess piece relative value) (Lasker 1934:73). It is better at defending nearby pawns than the knight is, and it is better at attacking them than the bishop is (Ward 1996:13).

[MahmoudUthman]

Direct search to depth 8 from starting position (69099951 nodes,37049926 Qnodes) then unlimited QuietScene was taking around 32 seconds , after implementing MVVLVA ~30 Seocnd (66232500 , 35382535) i think the nodes count didn't improve that much because the MVV/LVA generator (it's faster than the roiginal one by ~30M NPS ,at ~130M NPS for perft6 startpos for example) uses a slightly differnt quiet order than the original one, after implementing killers the number drops signifcently to ~3 seconds (6076479,3632315) , right now the evaluation function i use uses (attack tables taken from chessprogramming wiki,material difference,simple mobility differnce *5)
,how good or bad are those numbers ?
moving on to the history chess programming wiki claims that:

However, all of those statements were made at the time when typical search depth was much lower than today. Nowadays authors of the leading programs say that given enough search depth, history heuristic produces just a random noise. In Crafty it is not used anymore [5] , whereas Ed Schröder, author of Rebel, advocated not taking into account the cutoffs from the last couple of plies.

is this true for all engines even simple ones (because of hardware performance), or is this specific to advanced engines and pretty much deep depths ,should i implement it or are there new alternatives ?

[kbhearn]

You won't see much of a qsearch from the starting position at depth 8 as barely anything will be in position to take anything else after a mere 4 moves from each side, so the ordering won't show up yet. You should see an improvement in a midgame position.

History heuristic is still used in many (most?) engines but i don't think it's a huge gain as between the TT move (i haven't seen you mention using one yet and if not, this should probably be your next addition), captures, killers there's a very good chance you've already gotten a cutoff if you're going to. It wouldn't hurt to add it, but you could worry about other things first and there's certainly alternatives.

To get more depth in a timely manner you have to start looking at pruning and reduction techniques because even with perfect ordering you get stuck at sqrt(moves) as your branching factor which is somewhere around 7 for the midgame. The biggest gain of commonly used ones being from null move pruning and late move reduction.

You'll also want to flesh out your eval a little more to give it some basic concept of pawn structure, passed pawns, and king safety.

[MahmoudUthman]

Kevin Hearn, thanks.
I'm trying to implement the PV ordering using a Triangular PV-Table
but I can't understand the need for one or how to use one.
For example:
*do we try the previous iteration's PV line first and then the rest of the moves in there normal order (using other move ordering techniques).
*or do we try the previous iteration's PV line first then we try the one before it if it's different and so on until we have exhausted all the possibility's ?


*if I was using only the previous ID iteration's PV Line shouldn't a single array of Length(n)=MaxDepth be enough and every time I enter a new iteration I overwrite the previous one's value after using it .

According to Chess Programming Wiki:

PV in PVS
As demonstrated by Daniel Shawul with TSCP [6] , and explained by Harm Geert Muller [7] , inside a perfectly stable NegaScout aka Principal Variation Search, a fail-high at a PV-node compared to a null window is always confirmed by the re-search with an exact score improving alpha and will either become part of a new PV at the root or overwritten by a further improvement. Thus, under such conditions, there is no need to keep an array of principal variations, but only one.

MoveType pvArray[N];

However, with a transposition table, aspiration, selectivity and that like, one cannot guarantee such stable behavior.

*if it's the first case why cant this be used with ordinary Alpha Beta(nega max framework) ?
I tried to look into the code of several engine to understand this, but all of the ones I look into use TT to retrieve PV's

[hgm]

Fairy-Max uses the tri-angular array method to get its PV. (Except that it does not store it in a tri-angular array, but maps that on a stack in a 1-dim array. It just stacks the best-PV-so-far from the branch it is working on behind the best-PV-so-far of the lower levels. When the search of a move returns with an in-window score, it then copies the PV of the level it just returned from as new best-so-far of the current level, after prefixing with the searched move.) It doesn't use the PV for anything else than printing, btw; for move ordering it relies on the hash move (which should also hold the PV).

[MahmoudUthman]

H.G.Muller , Thank you.
but I'm planning to implement the TT later (after ensuring everything is okay to avoid increasing bugs), so how can I do that without one?
It seems that the idea I have about using pv's in ordering is wrong:
for example if my engine returns the following(direct search no ID)
search 1 best move d2d4 through evaluation
search 2 best move d2d4 through d7d5 through evaluation
search 3 best move e2e4 through d7d5 f1f5 through evaluation
search 4 best move d2d4 through e7e5 b1c3 b8c6 through evaluation
search 5 best move e2e4 through d7d5 f1f5 b8c6 f5f1 through evaluation
------------------------------------------------------------------------------
what information should I use in ordering exactly, is it something like this:
*use D1's best move as the first move in D2
*use D3's best move as the first move in D4 & d7d5 as the first one in the spawned search ,then f1f5,followed by different PV lines from previous iterations (search 2 next, search 1) and so one ,or how does' it work exactly ? how much information should I store (get) from a previous iteration(s) other than it's best move ?

[hgm]

One way would be to copy the PV from the previous iteration from the tri-angular array to some other global array before you start the next iteration. And then in the search use the ply level to get the move for that level from this array, and if it exists, sort it first, and erase it from the array. This guarantees the first thing the search will do is replay that PV, and find the best move to append to the end. Once the search has reached the end of this branch, the array is entirely cleared, and will not affect the rest of your search.

Looking in the array for the PV move is what you can then later replace by probing the TT, which will not only remember the moves in the previous PV branch, but all moves in the previous iteration's search tree.

[OliverBr]

You will have to get a pen and paper and a hex calculator to really understand what it is doing, but I think that olithink would be really hard to beat for beauty and simplicity combined.

It is a bit terse, but that is also part of the peculiar beauty of the C language. On the other hand, it is not an engine like those that compete for the smallest possible code and are therefore overly terse.

Once you see what he is doing, you will be floored by the accomplishment in such a small space.

And what he achieves in such an economy of scalle is incredible.
Go here:
http://home.arcor.de/dreamlike/chess/
Get this:
http://home.arcor.de/dreamlike/chess/Ol ... 32.src.zip

Single source file of 45K and yet 2372 Elo for 5.3.2:
http://www.computerchess.org.uk/ccrl/40 ... t_all.html

For a little while there, I forgot how much I love olithink. It's beautiful. It certainly shows how important mobility is.

@Dann, this is really very nice from you. Let's not forget your support and your contributions!
PS: Here is new link: http with an update (5.3.5) ://brausch.org/home/chess/