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(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?
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 (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.
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 (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
else if(numberOfLegalMoves ==1) return (WhiteToMove?+INF:-INF);
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()
{
for (int Depth = 1; (Depth < MaxDepth)&&!(UCI.STOP); ++Depth)
{
for (RootMove:RootMoves)
{
MakeMove(RootMove);
RootMove.Value=search(-INF,+INF,Depth, ply)
UnMakeMove(RootMove);
}
//sort the moves by value, highest comes first
}
return FirstRootMove;
}
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 (depth=1; (depth<maxDepth) && !timetomove; depth++)
/*value =*/ search(-INF,INF,depth,0); // 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.
with the exception of :
, 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.