AlfaGemma is back

[stegemma]

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:

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&#40;pNode->pMove < &#40;pNode+1&#41;->pFirstMove&#41;
		&#123;
			ExecuteMove&#40;pNode->pMove&#41;;

			uint64_t boTheKing = board.boBits&#91;clsBoard&#58;&#58;boKings&#93; & board.boBits&#91;clsBoard&#58;&#58;boFriends&#93;;
			bool bIsInCheck = &#40;pNode->bIsAlreadyInCheck ||
				                 boTheKing != pNode->boMyKing ||
												 &#40;pNode->pMove->boSrc & pNode->boKingRays&#41; != boEmpty&#41;
											? IsInCheck&#40;boTheKing, false&#41;
											&#58; false;
			if&#40;bIsInCheck&#41;
			&#123;
				PopBoardState&#40;);
				continue; // next move
			&#125; else
			&#123;
				++nodescount;
				++pNode->nValidMoves;
				if&#40;pNode == pLastNode&#41;
				&#123;
					// eval
					pNode->pMove->alfavalue = board.value + Evaluate&#40;);
					// ---> &#40;test value&#41;
				&#125; else
				&#123;
					SwapColor&#40;);
					++pNode;
					pNode->nMoves = 0;
					continue; // next ply
				&#125;
			&#125;
		&#125;else //------------------------------------- end of moves
		&#123;
			if&#40;!pNode->nValidMoves&#41;
			&#123;
				pNode->alfavalue = pNode->bIsAlreadyInCheck ? -valMate &#58; valDraw;
			&#125;
			if&#40;pNode == pStartingNode&#41; break;

			int val = -pNode->alfavalue;
			--pNode;
			// returns "alfa"
			pNode->pMove->alfavalue = val;
		&#125;

		//------------------------------------------- undo last move
		PopBoardState&#40;);

		//------------------------------------------- test value & beta cutoff
		if&#40;pNode->pMove->alfavalue > pNode->alfavalue&#41;
		&#123;
			pNode->alfavalue = pNode->pMove->alfavalue;
			if&#40;pNode->pMove->alfavalue >= -&#40;pNode - 1&#41;->alfavalue&#41;
			&#123;
				if&#40;pNode == pStartingNode&#41; break;
				--pNode;
				pNode->pMove->alfavalue = -valInfinity;
				PopBoardState&#40;);
			&#125;
		&#125;
	&#125;

	pNode = pStartingNode;
	PopBoardState&#40;);

	return pNode->alfavalue;
&#125;

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:

Code: Select all

dummy node
dummy node
root <- iterative deepening
starting node <- pNode
...other nodes...

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:

Code: Select all

satana.AlfaGemma: 48
satana.AlfaBeta: 33
satana.2.1.14: 39

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.

[Luis Babboni]

!! I´m not able to understand C++, but seems the FreeBasic "Alpha Beta" of Soberango that not have Beta I invented, is not an original idea!

[stegemma]

!! I´m not able to understand C++, but seems the FreeBasic "Alpha Beta" of Soberango that not have Beta I invented, is not an original idea!

My Drago uses this algorithm since 1993 but the algorithm itself is some year older than this.

Of course it is just a different way to implement AlphaBeta, so the inventors are Shannon and others, not us.

PS: if you look at Drago sources, then you know why I've rewritten the code in C++ here's a section of Elabora.asm of Drago:

Code: Select all

...
;-----------------------------
El_fine_livelli:
	mov bp, [si.n_valore-SIZE Nodo]
									  ; carica il valore del nodo precedente
	neg bp                    ; lo cambia di segno
	cmp bp, MINIMO            ; evita di tagliare se Š la prima variante
	jne El_no_minimo
	mov bp, MASSIMO
El_no_minimo:
	mov di, [si.n_ultima-SIZE Nodo] ; prima mossa di questo nodo
	mov ax, MASSIMO                 ; assegna un valore fittizio
	jmp El_valuta_finale
;-----------------------------
El_prossima:
	add di, SIZE Mossa        ; prossima mossa
El_valuta_finale:            ; cerca la mossa migliore e ne pone il val. in ax
	dec [si.n_resto]          ; diminuisce numero mosse ancora da eseguire
	js El_risali_ultimo       ; se finite esce

	mov dx, [si.n_mobilita]   ; somma la mobilita' del Nodo
	; sar dx, 1
	add dx, [di.m_valore]     ; carica il valore

	cmp dx, bp                ; confronta col valore del Nodo precedente...
	jge El_taglia_ultimo      ; ...se maggiore o uguale risale
	cmp dx, [si.n_valore]     ; confronta col valore di questo nodo
	jle El_prossima           ; se minore o uguale, ignora la mossa
	mov ax, dx
	jmp El_valuta_finale
;-----------------------------
Gm_matto_o_stallo:
	 mov ch, colore            ; punta al Re
	 sub ch, SIZE pezzy/2
	 mov bl, ch
	 mov al, [bx.casa]         ; carica posizione del Re
	 mov ah, al
	 call Scacco               ; si chiede se il Re Š sotto scacco
	 mov ax, val_stallo
	 jnc El_risali_stallo      ; no: allora Š stallo
	 mov ax, val_matto         ; s : Š matto
	 neg ax
	 jmp El_risali_matto
;-----------------------------
; ritorna al livello precedente
El_risali:
;-----------------------------DEBUG
	mov ax, [si.n_numero]
	sub ax, [si.n_resto]
	add c_giocatel, ax
	adc c_giocateh, 0
;-----------------------------DEBUG
	mov ax, scarto
	sub precisione, ax        ; ripristina il valore richiesto per proseguire
	and [si.n_legali], 0ffh   ; se non ci sono mosse legali...
	je Gm_matto_o_stallo      ; ...verifica se matto o stallo
	mov ax, [si.n_valore]     ; senno' carica il valore del nodo
;-----------------------------
El_risali_stallo:
;-----------------------------
El_risali_ultimo:
;-----------------------------
; ax deve contenere il valore della mossa appena giocata
; non risale se si tratta di un'iterazione non completata
	mov dx,[si.n_maxmosse]            ; si chiede se il numero massimo di mosse e'
	cmp dx,[si.n_maxmosse-SIZE Nodo]  ; >= a quello del nodo precedente
	jl El_iterazione                  ; senno' esegue un'altra iterazione
;-----------------------------
El_risali_matto:
;-----------------------------
; ax deve contenere il valore della mossa appena giocata
	cmp si, OFFSET albero     ; verifica se primo livello
	je El_ritorna             ; se lo e', esce da Elabora
;-----------------------------
	sub si, SIZE Nodo         ; risale di un nodo
	xor colore, BIT_INVERTI   ; cambia colore
	inc val_matto             ; preferisce i matti piu' brevi
	mov di, [si.n_mossa]      ; punta all'ultima mossa eseguita
	;neg precisione
	;neg scarto
;-----------------------------
...