AlfaGemma is back
Posted: Thu Aug 04, 2016 1:33 am
In my first attempt to write a chess program, I've "invented" my own version of AlphaBeta. I wasn't knowing about the existence of the original AlphaBeta at the times and I were working in Z80/6502 assembly so I've wrote an iterative algorithm, not a recursive one. After some year I've implemented a version of that algorithm in Drago; then I have know about AlphaBeta so I've called mine "AlfaGemma", more than for joke than to provide a name to something that already exists, in other form.
In Drago and Raffaela I've used my AlfaGemma and not AlphaBeta. In Freccia I really don't remember what I've used (!) but in Satana I've switched to AlphaBeta in C++.
The idea to convert AlfaGemma in C++ seems to be a little insane... but I'm more comfortable using my own algorithm than with AlphaBeta; debugging was easier to me with AlfaGemma.
I wish to obtain a clean code in C++, while AlfaGemma was based on jumps (in assembly). For the nature of the algorithm, first it looked like it needed some repetition in the code but at the end I've found the optimal way to write it.
Because in this forum I've found a lot of ideas and hints, I think that somebody can find useful my AlfaGemma in C++, so I share it:
First you must observe that I already use an array of nodes, that acts like a stack, in fact. That's why AlphaBeta is not optimal to me: AB is based on the CPU stack but I already have one so while to duplicate it?
The Pop/Push board simply do memcpy from the whole board information, to simplify undoing moves. The board contains even color state and castling/en-passant information. My MakeMoves() build an array of pseudo-legal moves, that's why the test for legality (IsInCheck and other details to speed check testing).
The pNode points to actual node. The previous one was used by iterative deepening and it is the root:
This idea was inherited directly from Drago.
In a round-robin test Satana-AlfaGemma vs Satana-AlphaBeta (two version of this) my algorithm wins with this results:
That's interesting because the AlfaGemma doesn't have the moves ordering yet! Both algorithm have Transposition Tables and other stuffs disabled. the book is the same for both, of course.
Now I'm testing against other softwares too, with different time s control. I think that enabling TT and maybe quiescence could give even better results.
In Drago and Raffaela I've used my AlfaGemma and not AlphaBeta. In Freccia I really don't remember what I've used (!) but in Satana I've switched to AlphaBeta in C++.
The idea to convert AlfaGemma in C++ seems to be a little insane... but I'm more comfortable using my own algorithm than with AlphaBeta; debugging was easier to me with AlfaGemma.
I wish to obtain a clean code in C++, while AlfaGemma was based on jumps (in assembly). For the nature of the algorithm, first it looked like it needed some repetition in the code but at the end I've found the optimal way to write it.
Because in this forum I've found a lot of ideas and hints, I think that somebody can find useful my AlfaGemma in C++, so I share it:
Code: Select all
int clsEngine::AlfaGemma(int iDepth)
{
clsSimpleNode *pStartingNode = pNode; // pNode = current node already set by caller
clsSimpleNode *pLastNode = pStartingNode + iDepth - 1;
pNode->nMoves = 0;
pNode->alfavalue = (pNode-2)->alfavalue = -valInfinity;
PushBoardState();
for(pNode = pStartingNode; !bTimeExpired; ++pNode->pMove)
{
//------------------------------------------- create moves
if(pNode->nMoves == 0)
{
PushBoardState(); // store board state
MakeMoves();
pNode->pMove = pNode->pFirstMove;
pNode->alfavalue = (pNode - 2)->alfavalue;
InitFastCheckTest(); // sets pNode->bIsAlreadyInCheck
}
//------------------------------------------- execute moves
if(pNode->pMove < (pNode+1)->pFirstMove)
{
ExecuteMove(pNode->pMove);
uint64_t boTheKing = board.boBits[clsBoard::boKings] & board.boBits[clsBoard::boFriends];
bool bIsInCheck = (pNode->bIsAlreadyInCheck ||
boTheKing != pNode->boMyKing ||
(pNode->pMove->boSrc & pNode->boKingRays) != boEmpty)
? IsInCheck(boTheKing, false)
: false;
if(bIsInCheck)
{
PopBoardState();
continue; // next move
} else
{
++nodescount;
++pNode->nValidMoves;
if(pNode == pLastNode)
{
// eval
pNode->pMove->alfavalue = board.value + Evaluate();
// ---> (test value)
} else
{
SwapColor();
++pNode;
pNode->nMoves = 0;
continue; // next ply
}
}
}else //------------------------------------- end of moves
{
if(!pNode->nValidMoves)
{
pNode->alfavalue = pNode->bIsAlreadyInCheck ? -valMate : valDraw;
}
if(pNode == pStartingNode) break;
int val = -pNode->alfavalue;
--pNode;
// returns "alfa"
pNode->pMove->alfavalue = val;
}
//------------------------------------------- undo last move
PopBoardState();
//------------------------------------------- test value & beta cutoff
if(pNode->pMove->alfavalue > pNode->alfavalue)
{
pNode->alfavalue = pNode->pMove->alfavalue;
if(pNode->pMove->alfavalue >= -(pNode - 1)->alfavalue)
{
if(pNode == pStartingNode) break;
--pNode;
pNode->pMove->alfavalue = -valInfinity;
PopBoardState();
}
}
}
pNode = pStartingNode;
PopBoardState();
return pNode->alfavalue;
}
The Pop/Push board simply do memcpy from the whole board information, to simplify undoing moves. The board contains even color state and castling/en-passant information. My MakeMoves() build an array of pseudo-legal moves, that's why the test for legality (IsInCheck and other details to speed check testing).
The pNode points to actual node. The previous one was used by iterative deepening and it is the root:
Code: Select all
dummy node
dummy node
root <- iterative deepening
starting node <- pNode
...other nodes...
In a round-robin test Satana-AlfaGemma vs Satana-AlphaBeta (two version of this) my algorithm wins with this results:
Code: Select all
satana.AlfaGemma: 48
satana.AlfaBeta: 33
satana.2.1.14: 39
Now I'm testing against other softwares too, with different time s control. I think that enabling TT and maybe quiescence could give even better results.
