Search algorithm in it's simplest forum

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Re: Search algorithm in it's simplest forum

Post by MahmoudUthman » Thu Feb 26, 2015 9:58 pm

Kevin Hearn,Thomas Petzke,Reinhard Scharnagl,Sven Schüle , thank you (It's a pleasure to be here)
Sven Schüle wrote:Hi Mahmoud,

since I find mixing fail-soft and fail-hard confusing (you can read more about it in the CPW if you want to know the difference) I prefer to write the search based on fail-soft only. A very basic alpha-beta negamax search with quiescence search could look like this:

Code: Select all

int qSearch(int alpha, int beta)
{
    int bestScore = evaluate();
    if (bestScore >= beta) return bestScore;
    generateLegalQSMoves();
    for (all moves) {
        makeMove(move);
        int score = -qSearch(-beta, -Max(alpha, bestScore));
        unmakeMove(move);
        if (score > bestScore) {
            bestScore = score;
            if (bestScore >= beta) break;
        }
    }
    return bestScore;
}

int search(int alpha, int beta, int depthLeft, int height)
{
    if (depthLeft == 0) return qSearch(alpha, beta);
    generateLegalMoves();
    if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
    int bestScore = -INF;
    for (all moves) {
        makeMove(move);
        int score = -search(-beta, -Max(alpha, bestScore), depthLeft - 1, height + 1);
        unmakeMove(move);
        if (score > bestScore) {
            bestScore = score;
            if (bestScore >= beta) break;
            if (height == 0 && bestScore > alpha) {
                bestRootMove = move;
            }
        }
    }
    return bestScore;
}
this code pretty much made every thing clear for me :) with the exception of :
1-Does height mean ply to give higher score for the mat in less moves ,or is it something else?
2-

Code: Select all

 if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0); 
-(INF-Height) for white and (INF-Height) for black ? or the same thing regardless of the side to move.
3-if Generate Legal Moves return one move can I return (+INF,-INF) at once for example :

Code: Select all

 if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
else if(numberOfLegalMoves ==1) return (WhiteToMove?+INF:-INF); 
4- is this Iterative Deepening usage right ?

Code: Select all

IterativeDeepining()
{
for &#40;int Depth = 1; &#40;Depth < MaxDepth&#41;&&!&#40;UCI.STOP&#41;; ++Depth&#41;
&#123;
	for &#40;RootMove&#58;RootMoves&#41;
	&#123;
		MakeMove&#40;RootMove&#41;;
		RootMove.Value=search&#40;-INF,+INF,Depth, ply&#41;
		UnMakeMove&#40;RootMove&#41;;
	&#125;
	//sort the moves by value, highest comes first
&#125;
return FirstRootMove;
&#125;
or do I need to call it search like this "RootMove.Value=search(WhiteTo Move ?-INF:+INF,WhiteToMove?+INF:-INF,Depth,ply)
" ?

I know most if not all of my questions may seem stupid :shock: , or imply a lack of effort ,but I really did search and read a lot before asking here and I think I understand alpha/beta concept and some of it's enhancements.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Search algorithm in it's simplest forum

Post by kbhearn » Fri Feb 27, 2015 6:52 am

MahmoudUthman wrote:Kevin Hearn,Thomas Petzke,Reinhard Scharnagl,Sven Schüle , thank you (It's a pleasure to be here)
Sven Schüle wrote:Hi Mahmoud,

since I find mixing fail-soft and fail-hard confusing (you can read more about it in the CPW if you want to know the difference) I prefer to write the search based on fail-soft only. A very basic alpha-beta negamax search with quiescence search could look like this:

Code: Select all

int qSearch&#40;int alpha, int beta&#41;
&#123;
    int bestScore = evaluate&#40;);
    if &#40;bestScore >= beta&#41; return bestScore;
    generateLegalQSMoves&#40;);
    for &#40;all moves&#41; &#123;
        makeMove&#40;move&#41;;
        int score = -qSearch&#40;-beta, -Max&#40;alpha, bestScore&#41;);
        unmakeMove&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
            bestScore = score;
            if &#40;bestScore >= beta&#41; break;
        &#125;
    &#125;
    return bestScore;
&#125;

int search&#40;int alpha, int beta, int depthLeft, int height&#41;
&#123;
    if &#40;depthLeft == 0&#41; return qSearch&#40;alpha, beta&#41;;
    generateLegalMoves&#40;);
    if &#40;numberOfLegalMoves == 0&#41; return &#40;isInCheck&#40;) ? -&#40;INF - height&#41; &#58; 0&#41;;
    int bestScore = -INF;
    for &#40;all moves&#41; &#123;
        makeMove&#40;move&#41;;
        int score = -search&#40;-beta, -Max&#40;alpha, bestScore&#41;, depthLeft - 1, height + 1&#41;;
        unmakeMove&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
            bestScore = score;
            if &#40;bestScore >= beta&#41; break;
            if &#40;height == 0 && bestScore > alpha&#41; &#123;
                bestRootMove = move;
            &#125;
        &#125;
    &#125;
    return bestScore;
&#125;
this code pretty much made every thing clear for me :) with the exception of :
1-Does height mean ply to give higher score for the mat in less moves ,or is it something else?
Height is the distance from the root (it sometimes goes by other names). In his pseudocode it's used to make sure the best move is extracted from the root and stored in a global so the program knows what to play and not just the score of the position after searching (this can be done in other ways (but this is simple for now). It is also often used to index into a per-ply preallocated data structure for the search (each ply will need its own movelist preserved for instance, might want its own copy of the board if you use copymake, may have local heuristics data, etc). For this purpose everytime you recursively call the search height+1 is passed as height.
2-

Code: Select all

 if &#40;numberOfLegalMoves == 0&#41; return &#40;isInCheck&#40;) ? -&#40;INF - height&#41; &#58; 0&#41;; 
-(INF-Height) for white and (INF-Height) for black ? or the same thing regardless of the side to move.
No! The number of legal moves == 0 means the position is stalemate or checkmate and there is no more searching to be done, either a draw score or mate score is returned. In a negamax framework all scores are from the side to move in the current node so -(INF-Height) means it's really bad for the side to move (they're checkmated). 0 means draw score. The score will be negated appropriately as it's backed up to the root.
3-if Generate Legal Moves return one move can I return (+INF,-INF) at once for example :

Code: Select all

 if &#40;numberOfLegalMoves == 0&#41; return &#40;isInCheck&#40;) ? -&#40;INF - height&#41; &#58; 0&#41;;
else if&#40;numberOfLegalMoves ==1&#41; return &#40;WhiteToMove?+INF&#58;-INF&#41;; 
Nope, 1 legal move means you have to make this move at this node but it doesn't tell you anything about how good/bad the position is after making it. At the root, you could detect and automatically make the move and that would be fine. But deeper into the search a node with 1 legal move still needs a correct evaluation so that it can back it up to the root where there IS a choice (i.e. if i look at checking my opponent with the queen, and his only legal move is to capture that queen, and then my position is very bad (i'm just down a queen) i need to know that at the node where i was checking with the queen so i don't do it. if it leads to a mating attack i need to know that too so i do do it!.
4- is this Iterative Deepening usage right ?

Code: Select all

IterativeDeepining&#40;)
&#123;
for &#40;int Depth = 1; &#40;Depth < MaxDepth&#41;&&!&#40;UCI.STOP&#41;; ++Depth&#41;
&#123;
	for &#40;RootMove&#58;RootMoves&#41;
	&#123;
		MakeMove&#40;RootMove&#41;;
		RootMove.Value=search&#40;-INF,+INF,Depth, ply&#41;
		UnMakeMove&#40;RootMove&#41;;
	&#125;
	//sort the moves by value, highest comes first
&#125;
return FirstRootMove;
&#125;
or do I need to call it search like this "RootMove.Value=search(WhiteTo Move ?-INF:+INF,WhiteToMove?+INF:-INF,Depth,ply)
" ?
You're actually doing a multipv search there. every move after the first no longer needs to be searched at (-INF,INF) window because you have a lower bound on what's acceptable and it'll thus be (alpha,INF) you search for, and if it returns any less than alpha, it's worse and you don't need to know how much worse. Things are actually even simpler to do iterative deepening with the enclosed search that's already extracting the root move for you (at height = 0):

Code: Select all


for &#40;depth=1; &#40;depth<maxDepth&#41; && !timetomove; depth++)
  /*value =*/ search&#40;-INF,INF,depth,0&#41;;  // value is not actually used

// bestRootMove now contains the best move found as the search function extracted it for you

I know most if not all of my questions may seem stupid :shock: , or imply a lack of effort ,but I really did search and read a lot before asking here and I think I understand alpha/beta concept and some of it's enhancements.
Edit: Note that before you have a transposition table, iterative deepening doesn't make much sense. The big gain from iterative deepening is that on the next ply you have TT moves for most of the tree that are mostly correct and allow you to search a close to minimal tree. With no TT, you may as well just stick to doing a fixed depth search for the time being.

Daniel Anulliero
Posts: 684
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: Search algorithm in it's simplest forum

Post by Daniel Anulliero » Fri Feb 27, 2015 11:22 pm

MahmoudUthman wrote:I'm a beginner in chess engine programming so far I have implement Strictly Legal move generator and verified it's correctness using perft routine ,I'm trying to implement the search and evalution functions but to no avail ,reading the source code of several other programmers even simple one's like TSCP the search routine is full of heuristic and transposition code...etc which makes it pretty much hard for me to understand , could someone provide an example search routine out of this PVS ....
You could look at this source , very easy to understand
http://devwebcl.atarionline.pl/cc65/firstchess.c
Bests
Dany

nionita
Posts: 161
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Re: Search algorithm in it's simplest forum

Post by nionita » Sat Feb 28, 2015 10:21 am

kbhearn wrote: Edit: Note that before you have a transposition table, iterative deepening doesn't make much sense. The big gain from iterative deepening is that on the next ply you have TT moves for most of the tree that are mostly correct and allow you to search a close to minimal tree. With no TT, you may as well just stick to doing a fixed depth search for the time being.
Hi Kevin, I think even without TT iterative deepening makes sense, first to have a better root move order at higher depths, and second to have at least a pretty good root move when you reach the time limit (from the previous iteration).

MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Re: Search algorithm in it's simplest forum

Post by MahmoudUthman » Sun Mar 08, 2015 6:01 pm

Kevin Hearn,Daniel Anulliero,Nicu Ionita thanks.
I have implemented a basic evaluation function :(STM--->SideToMove,NTM--->other Side)

Code: Select all

#pragma once
#include"Constants.h"

auto Evaluate&#40;)
&#123;
	unsigned int NTM = 7 - STM;
	auto PBBV = PawnV*(_mm_popcnt_u64&#40;S&#91;STM + Pawn&#93;) - _mm_popcnt_u64&#40;S&#91;NTM + Pawn&#93;));
	auto BBBV = BishopV*(_mm_popcnt_u64&#40;S&#91;STM + Bishop&#93;) - _mm_popcnt_u64&#40;S&#91;NTM + Bishop&#93;));
	auto NBBV = KnightV*(_mm_popcnt_u64&#40;S&#91;STM + Knight&#93;) - _mm_popcnt_u64&#40;S&#91;NTM + Knight&#93;));
	auto RBBV = RookV*(_mm_popcnt_u64&#40;S&#91;STM + Rook&#93;) - _mm_popcnt_u64&#40;S&#91;NTM + Rook&#93;));
	auto QBBV = QueenV*(_mm_popcnt_u64&#40;S&#91;STM + Queen&#93;) - _mm_popcnt_u64&#40;S&#91;NTM + Queen&#93;));
	auto MaterialV = PBBV + BBBV + NBBV + RBBV + QBBV;
	return MaterialV;
&#125;
basic A/B search :

Code: Select all

#pragma once
#include"MoveGen.h"
#include"Evaluation.h"
static U64 NodesSearched=0;
static int AlphaBetaNegaMax&#40;int alpha, int beta, int depthleft&#41;
&#123;
	NodesSearched++;
	if &#40;depthleft == 0&#41; return Evaluate&#40;);
	ExtMove Available&#91;256&#93;;
	U64 InCheck;
	auto MoveCount =  Move&#58;&#58;GENALLLegal&#40;Available, InCheck&#41;-Available;
	for &#40;size_t i = 0; i < MoveCount;++i&#41;
	&#123;
		Move&#58;&#58;MakeMove&#40;Available&#91;i&#93;);
		auto score = -AlphaBetaNegaMax&#40;-beta, -alpha, depthleft - 1&#41;;
		Move&#58;&#58;UnMake&#40;Available&#91;i&#93;);
		if &#40;score >= beta&#41;
			return beta;   //  fail hard beta-cutoff
		if &#40;score > alpha&#41;
			alpha = score; // alpha acts like max in MiniMax
	&#125;
	if &#40;MoveCount == 0&#41; return InCheck?-INT_MAX+ply&#58;0;
	return alpha;
&#125;
static ExtMove RootSearch&#40;int max_depth&#41;
&#123;
	ExtMove RootMoves&#91;256&#93;;
	const long long MoveCount = Move&#58;&#58;GENALLLegal&#40;RootMoves&#41;-RootMoves;
	NodesSearched = MoveCount;//for now
	int Alpha = -INT_MAX;
	int Beta = INT_MAX;
	ExtMove BestMove;
	for &#40;size_t i = 0; i < MoveCount; i++) 
	&#123;
		Move&#58;&#58;MakeMove&#40;RootMoves&#91;i&#93;);
		auto Score = -AlphaBetaNegaMax&#40;Alpha,Beta, max_depth - 1&#41;;
		if &#40;Score > Alpha&#41;
		&#123;
			Alpha = Score;
			BestMove = RootMoves&#91;i&#93;;
		&#125;
		Move&#58;&#58;UnMake&#40;RootMoves&#91;i&#93;);
	&#125;
	return BestMove;
&#125;
ExtMove is int32 alias
Shouldn't this code be able to find all mates in a given depth?
I don't understand why it isn't finding this fool's mate even though I'm setting the depth to 9 "way above the minimum mate distance " :
Teed vs. Delmar, 1896
:"rnbqkbn1/ppppp3/7r/6pp/3P1p2/3BP1B1/PPP2PPP/RN1QK1NR w KQq - 0 1 " it playes e3 ->e4

Sven
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Search algorithm in it's simplest forum

Post by Sven » Sun Mar 08, 2015 7:27 pm

Hi Mahmoud,

in RootSearch() please pass -Beta,-Alpha to the call of AlphaBetaNegaMax(), same as in the recursive call. Making a move changes STM and thus reverts the viewpoint of all scores, so also for the AB window.

Sven
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Search algorithm in it's simplest forum

Post by Sven » Sun Mar 08, 2015 7:51 pm

Sven Schüle wrote:Hi Mahmoud,

in RootSearch() please pass -Beta,-Alpha to the call of AlphaBetaNegaMax(), same as in the recursive call. Making a move changes STM and thus reverts the viewpoint of all scores, so also for the AB window.
If that still does not help to find the mate in 3 plies then you have some problem in the move generator or Make/Unmake functions.

When trying to debug dubious search problems you could create some utility code to print variations selectively. In the given example it would be interesting to see all variations (including alpha/beta settings and scores) that your program searches in the subtree of 1.Qxh5+, but only the first three plies (three to watch out for possible illegal moves). If the legal move list after 1.Qxh5+ is not the move list containing exactly 1...Rxh5 then your move generator has a bug. Otherwise 1...Rxh5 must be searched. Does that happen? Or is 0 returned, which means that the InCheck detection which seems to be part of your move generator is broken somehow? Now many white moves are possible. Is 2.Bg6+ searched? If so, is the opponent's legal move list empty, and is InCheck set correctly?

In this simple case even stepping through the code with a debugger should help, provided you can see easily the move that is currently being made.

Dann Corbit
Posts: 9911
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Search algorithm in it's simplest forum

Post by Dann Corbit » Mon Mar 09, 2015 5:10 am

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.

MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Re: Search algorithm in it's simplest forum

Post by MahmoudUthman » Mon Mar 09, 2015 8:06 pm

Sven Schüle,Dann Corbit thanks.
the move generatore turned out to be ok,it was just (-Beta,-Alpha ) as you said.
after fixing it i have implement a Quiescence Search ,using a capture and evasion (including non capture) generatore,should i limit it's depth? and if so what is the best way to limit the depth of the Quiescence ? should i leave it open until interrupted by a time stop signal ?

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Search algorithm in it's simplest forum

Post by kbhearn » Mon Mar 09, 2015 9:17 pm

If you're only doing captures and check evasions, quiescence should not need any further limitations. Each capture removes a potential capture so it will terminate eventually (and usually quite quickly). To shrink the size of it further:

1) Move ordering
MVV-LVA (primary sort most valuable victim, secondary sort least valuable attacker) ordering for captures is a bare minimum, this gives you a high chance of finding a capture sequence that provides a cut-off asap.

2) Filtering out some of the captures
The simplest captures that can be omitted to good effect are futile captures. You've already made an eval to see if you can stand pat, so if (alpha > eval + margin + capture value) there's no need to try the capture as the other side will simply stand pat and fail high.

The most significant captures that can be omitted are bad captures, this requires implementing SEE. SEE < 0 is a bad capture and can be expected to usually make things worse than standing pat not better for the side to move.

Post Reply