GNUchess program's PVS Algorithm

Description: Researched and understood how PVS algorithm works in GNUchess program. In order to understand the algorithm I implemented the Alpha-Beta cutoffs algorithm and Principal Variation Search algorithm and ran it on sample input values.

Figure 1: Sample gametree for comparing Alpha-Beta and PVS algorithm.

Example 1:Output generated by Alpha-Beta cutoffs program:

In regular minimax, all nodes would have been visited. Total number of nodes = 15
In AlphaBeta, the number of nodes visited is 14. Cutoff occurred at node N4 because the alpha value (6) was greater than the beta value (5). Node N10 was cut off.

Example 2:Output generated by PVS program:

For the same gametree, the number of nodes visited using PVS is 13.
Cutoff occurred at N4 (N10 was cutoff) and also at N5 (N12 was cutoff).
N10 was cutoff due to basic alpha beta pruning.
N12 was cutoff due to PVS algorithm. This cutoff occurred since at N5 alpha 9 >= beta 6. PVNode with a value of 9 was assumed at N5. Since N13 and N14 were also less than 9, this assumption proved to be right.

However, if the following values are put into the tree:
N12 = 10
N13 = 11
N14 = 11

In this case, N12 = 10, would be the final PVS value at N0.
N14 would be cutoff since at N6 alpha 11 >= beta 10.

So, when PVS finds that minimax at node N6 = 11, it knows that the previous assumption of cutting off N12 = 10 was incorrect. So, it has to now search N12 with alpha = 9, beta = 2147483647 score = 10.

The above example illustrates two important things:

• If move ordering is good, PVS usually does better than alphabeta. More nodes can be cutoff. (In the example tree, one extra node was cutoff).
• If the move ordering is not so good, PVS might have to re-search some of the subtrees incurring performance penalty. In any case, PVS will not search any more nodes than alpha beta, but it might have to re-search some of the subtrees like the example with the changed values mentioned above.

Output generated by GNUchess program with my printfs showing tree depths, scores, Alpha Beta values and PV Nodes.

Example 3: Move 1

Initial RootPV = 3299
The RootPV did not change till depth 10 since the computer did not find a better move than what it thought initially. So, it chose d5

Example 4: Move 2

Initial RootPV = 4013.
The RootPV changed to 3690 in between since the computer found a better move than the initial move. (changed from Nf6 to Nc6)

The computer initially generates a PVRoot and the rest of the moves from the hash table. These moves are generated based on the scores by the Evaluate() function.
The evaluate function calculates the score based on such formula:
c1 * material + c2 * mobility + c3 * king safety + c4 * center control + ...
Evaluate() -> Calls all below routines plus a bunch of other criteria ScoreP, ScoreN, ScoreB, ScoreR, ScoreQ, ScoreK

In the above case, till depth 6 (ply=6), the computer could not find a high score for the set of moves and it still had time to think of new moves. It generated a new move (Nc6) for which the new score returned was better than the current best and also better than alpha.
(score > best) && (best > alpha)

This move (Nc6) became the new RootPV.
SearchRoot: RootPV changed. OldRootPV = 4013, NewRootPV = 3690. score = -20, alpha = -26
The computer then generated new moves from the hash table and calculated the minimax scores for them. At depth9, a maximum possible score was attained for this RootPV. So, this move (Nc6) was chosen.
SearchRoot score = -32768. Idepth = 9, RootAlpha = -99, RootBeta = 51, RootPV = 3690

Example 5: Move 3

In this case FAIL HIGH is hit. A score > Beta was returned. The alpha-beta windows had to be readjusted (RootAlpha = 38, RootBeta = 32767) and search had to be done in a regular alpha beta manner. However the final move did not change.

Example 6: Move 4

In this case FAIL LOW case is hit. A score < Alpha was returned. The alpha-beta windows had to be readjusted (RootAlpha = -32767, RootBeta = 1177) and search had to be done in a regular alpha beta manner. However the final move did not change.

Example 6: Final move.

The computer got a very good score at Idepth = 1. It did not have to search beyond that

PVS Code

/*
 * chess.h has the node struct and the gametree defined
 */
#include "chess.h"

/*
 * PVS algorithm with alphabeta
 */
static int
minimaxAB(struct node *n, int a, int b)
{
	boolean_t fFoundPv = FALSE;
	int newb;
	int val;
	int newa;

	if (n->child == NULL) {
		return n->value;
	}
	n->alpha = INT_MIN;
	n->beta  = INT_MAX;
	if (n->knd == Min) {
		struct node *r;
		for (r = n->child; r != NULL; r = r->sibling) {
			newb = MIN(b, n->beta);
			if (fFoundPv == TRUE) {
				printf("Calling1 minimaxAB with Minimal Window %d %d\n",
					a, a+1);
				val = minimaxAB(r, a, a + 1);
				if ((val > a) && (val < newb)) {
					val = minimaxAB(r, a, newb);
				}
			} else {
				val = minimaxAB(r, a, newb);
			}
			printf("minimax at node %s, alpha = %d, beta = %d score = %d\n",
				r->name, a, newb, val);
      		n->beta = MIN(n->beta, val);
			if (a >= n->beta) {
				int nline = FALSE;
				if (r->sibling) {
					printf("\nCUTOFF for %s because alpha %d >= beta %d\n",
						n->name, a, n->beta);
					nline = TRUE;
				}
				for (r = r->sibling; r != NULL; r = r->sibling) {
					printf("Nodes cutoff: %s\n",
						r->name);
				}
				if (nline == TRUE) {
					printf("\n");
				}
				break;
			}
		}
		return n->beta;
	} else {
		struct node *r;
		for (r = n->child; r != NULL; r = r->sibling) {
			newa = MAX(a, n->alpha);

			if (fFoundPv == TRUE) {
				printf("Calling2 minimaxAB with Minimal Window %d %d\n",
					newa, newa + 1);
				val = minimaxAB(r, newa, newa + 1);
				if ((val > newa) && (val < b)) {
					val = minimaxAB(r, newa, b);
				}
			} else {
				val = minimaxAB(r, newa, b);
			}
			printf("minimax at node %s, alpha = %d, beta = %d score = %d\n",
				r->name, newa, b, val);
			if (val > n->alpha) {
				printf("Found PVNode. val = %d, alpha = %d, beta = %d\n",
					val, n->alpha, b);
				n->alpha = val;
				fFoundPv = TRUE;
			}
			if (n->alpha >= b) {
				int nline = FALSE;
				if (r->sibling) {
					printf("\nCUTOFF For %s because alpha %d >= beta %d\n",
						n->name, n->alpha, b);
					nline=TRUE;
				}
				for (r = r->sibling; r != NULL; r = r->sibling) {
					printf("Nodes cutoff: %s\n",
						r->name);
				}
				if (nline == TRUE) {
					printf("\n");
				}
				break;
			}
		}
		return n->alpha;
	}
}
int
main()
{
  int val;

#if 0
  printNode(game1);
#endif
  val = minimaxAB(game1, INT_MIN, INT_MAX);
  printf("\nPVS Alpha Beta Minimax at root position %s is: %d\n",
  	game1[0].name, val);
  return 0;
}