Constructing Agents for Connect-4: Transposition Tables

This post is the 5th part of a series of 7 articles:

  1. Constructing Agents for Connect-4: Initial Notes
  2. Constructing Agents for Connect-4: Tree Search Algorithms
  3. Constructing Agents for Connect-4: Board Representations
  4. Constructing Agents for Connect-4: Move Ordering
  5. Constructing Agents for Connect-4: Transposition Tables
  6. Constructing Agents for Connect-4: Opening Databases
  7. Constructing Agents for Connect-4: Final Considerations Using transposition tables (hash tables) is another way to speed up the tree search. They are mainly used to avoid multiple analyses (analysis of whole subtrees) of individual positions during the search. In connection with iterative deepening, it is also possible to optimize move ordering using transposition tables. In this project, however, iterative deepening is not used for the alpha-beta search, as it could not achieve any runtime advantages. Regardless of the board game under consideration, the use of transposition tables in combination with tree-search results in an enormous saving of knots, so that a halving of the search time is quite realistic.
  Note: The related Java framework for Connect-4 is available on GitHub and can be downloaded from: http://github.com/MarkusThill/Connect-Four.

Permutations of Move Sequences

In many games, changes in the order of moves within a move sequence often lead to the same position. The different arrangements of a move sequence can also be referred to as permutations, whereby a permutation represents a bijective representation of a set of plys on itself. The individual permutations can be generated using a finite number of transpositions, where a transposition is defined as a permutation that exchanges exactly two elements (plys) with each other. However, the term transposition table comes from English. Chess moves are often referred to as transpositions.

It should be noted that not all permutations of a move sequence necessarily lead to the same position in the game. Individual permutations may contain impossible moves or might result in other states. In a chess game, for example, it is not possible to draw a figure on a square that is already occupied by a piece of the same player; this could happen with certain changes in the move sequence. Furthermore, a single transposition, in which a ply of one player is swapped with a ply of the opponent, results in an illegal move sequence, since two plys of the same player would follow each other directly. Therefore, it is better to keep the plys of each player in separate move lists. But not all permutations of the separate move sequences necessarily always lead to identical states. In the gameConnect-4, this is prevented by the gravity rule of the game, in the case of chess or checkers, for example, by the hitting moves. Tic Tac Toe and Gomoku, on the other hand, are games for which all permutations of a move sequence (each treated separately for both players) lead to the same position in the game.

A Hash Method according to Albert L. Zobrist

Since under certain circumstances several thousand or even millions of nodes of the search tree are examined per second, a particular efficiency of the hash method is required when using transposition tables. Therefore, a function is sought which maps a state of the game to a hash value (and index of the hash table) without any special effort. Albert L. Zobrist already introduced such a procedure in 1970. It is particularly suitable for board games and is now widely used in chess programming. This is described in more detail below. The central operation for zobrist-hashing is the bitwise exclusive OR (XOR), with which n-digit dual numbers are linked to obtain a unique position key. In general, a list of random numbers is created, each of which corresponds to a piece at a certain position. A set of random numbers must be generated for each player. In general, the number of required random numbers can be described as follows:

N_Random = Number of players × (Number of figure types per player) × Number of fields

where certain special moves may have to be coded separately. Connect-4 would therefore require 2 x 42 random numbers. When you add a piece, you simply update the current key by XOR-ing it to the corresponding random number. It is also possible to remove or move pieces without any problems. This and other special features are quickly apparent when looking at some basic properties of the XOR link (notation: ):

  1. (associativity) and (commutativity): The sequence of the individual moves is not relevant for the construction of the key. Permutations of a move sequence lead to the same key (if the positions are also identical).
  2. x\nleftrightarrow x=0: This allows you to remove a piece from the Zobrist key. To move a piece, it is first removed from the key and then reinserted elsewhere. Two bitwise XOR operations are required for this.
  3. The bit-by-bit XOR combination of any number of n-digit random dual numbers produces an n-digit random number as well. This is by no means the case with all operations (for example, for bitwise AND operation).

In addition, Zobrist-Hashing allows incremental modification of the key. This is of particular advantage during the tree search, since only very few XOR operations are required in each node to update the key. The Connect-4 search even requires only one XOR operation per node. Using a simple hash function, e. g. a modulo function, the index within the transposition table is determined using the key. In some cases, the modulo function can also be converted to a bitwise AND operation. This is always the case when using transposition tables of size . However, unambiguous keys cannot be generated with this method; the mapping of the game states to the set of keys is not injective. For example, in the game Conect-4 occasionally errors occurred when 32-bit keys were used. When using 64-bit keys, no more errors could be observed, but they cannot be excluded (this is due to the fact, that we store the 64-bit Zobrist key in the hash table instead of the position. To prevent any errors, one would have to store the bit-boards of both players in the hash table).

Design of the Transposition Tables

As mentioned above, the Alpha-Beta Search for Connect-4 is divided into two stages for performance reasons. The use of a two-stage transposition table also brought significant runtime advantages. This is mainly due to the fact that entries for nodes at lower levels are not overwritten by the higher levels. Since hits in the transposition table of the first stage in particular lead to a considerable saving of nodes, the separation into two stages makes sense. For each node, the system first checks whether an entry exists in the corresponding transposition table. If this is the case, the search can in many cases be interrupted at this point and the corresponding value returned. Otherwise, the search continues as usual and the result for the node is inserted into the corresponding transposition table. Since the hash function is not injective, several keys may be assigned the same index in the transposition table. Such collisions cannot be avoided, but there are some strategies to deal with them. However, only linear probing was tested for this project. A reduction of the runtime was not possible, so that already existing entries in the current version of the program are simply overwritten in case of a collision.

Each entry in a transposition table consists of three elements:

  1. position key: Since collisions can occur during the reading process, it is necessary to save the corresponding position as well. In this case, you may want to use the Zobrist key to identify the position and store it for each entry in the transposition table. As mentioned above, however, it can happen that identical Zobrist keys are generated from two different positions. This is avoided by selecting a suitable key length. However, errors can only be completely excluded if the complete position, i. e. the bit boards of both players, are stored for the respective entries in the transposition table.
  2. Value of the position.
  3. Type of node: Since the value of a node is only exact if it lies between alpha and beta, the node type information must be included in each entry of the transposition table in addition to the value of the node. As already mentioned, the value can be an exact result, an upper or a lower limit.

Enhanced Transposition Cutoffs

In general, before the actual alpha-beta search starts, the transposition table is first examined for a suitable entry in each node. In many cases there is no such entry, so a detailed analysis of the position is necessary. These are tried to be avoided with the Enhanced Transposition Cutoffs (ETC). The basic idea behind it is as follows: If the transposition table does not contain a suitable entry for the current position, it is still possible to find individual after-state positions in it. In the hope of achieving a cutoff, you create the keys of all subsequent statements and look them up in the table. Often such a cutoff can be achieved without having to expand the current node further. However, since hash accesses are usually very time-consuming, this procedure often only has a real advantage in nodes near the roots. In the Connect-4 program, ETCs are therefore only used in the first stage of the Alpha-Beta search. Their use accelerated the search by about 15%.

Other Optimizations

As mentioned in an earlier blog post, the use of mirror or rotational symmetries can speed up the search considerably. This can also be used for accessing the transposition tables. If a query does not return a result, a repetition with mirrored or rotated positions is often successful. Generally speaking, the generation of symmetrical positions is comparatively complex, so that this can only be done up to a certain search depth. In the Connect-4 game, this measure made it possible to speed up the search for empty fields and positions with only a few pieces (without using the opening databases). With an increased degree of filling of the transposition tables, the number of collisions increases rapidly. To avoid this, you should try not to make unnecessary entries in the tables. As it turns out, it is not necessary to access the transposition tables in each node of the Connect-4 search tree. Thus, the filling level of the two transposition tables could be significantly reduced by using the tables only on every second level of the search tree. As a result, the number of entries during the search is almost halved and fewer collisions occur.

Appendix

Accessing the Transposition Table in lower Levels

CFour/src/c4/AlphaBetaAgent.java view raw
// int transPosition = (unsigned long)zobr % lTransPosSize;

// should be equal to above operation (time)

// Check for Entry in Transposition-Table

if (lKey[index] == zobr) {
	short v = lValue[index];
	switch (lFlag[index]) {
	case TRANSPOSEXACT:
		return v;
	case TRANSPOSLOWER:
		if (v >= beta)
			return v;
		if (v > alpha)
			alpha = v;
		break;
	case TRANSPOSUPPER:
		if (v <= alpha)
			return v;
		if (v < beta)
			beta = v;
		break;
	}
}
boolean isExactValue = false;

Try mirrored positions as well:

int moves[];
// Mirror Board

long f1 = getMirroredField(PLAYER1);
long f2 = getMirroredField(PLAYER2);
 if (tds != null && countPieces() <= 10)
	 moves = tds.getBestMoveList(fieldP1, fieldP2);
 else
// dynamic move-ordering

moves = generateMoves(PLAYER1, true);
// Check, if symmetry is still possible. If current board is symmetric,

// only one half of the board must be evaluated

if (symPos)
	if ((symPos = ((f1 & fieldP1) == 0L && (f2 & fieldP2) == 0L)))
		if ((f1 == fieldP2 && f2 == fieldP1)) {
			int tmp[] = new int[8];
			for (x = 0; moves[x] != -1; x++) {
				if (moves[x] < 4)
					tmp[y++] = moves[x];
			}
			for (x = 0; x < y; x++)
				moves[x] = tmp[x];
			moves[x] = -1;
		}
// Try to find mirrored board in Transposition-Table

if (depth < 16 /* && symPos */) { // scheint ohne das

									// Auskommentiere schneller zu sein

	long nZobr = toZobrist(f1, f2);
	int transPositionN = ((int) nZobr & (lTransPosSize - 1));
	if (lKey[transPositionN] == nZobr) {
		short v = lValue[transPositionN];
		switch (lFlag[transPositionN]) {
		case TRANSPOSEXACT:
			return v;
		case TRANSPOSLOWER:
			if (v >= beta)
				return v;
			if (v > alpha)
				alpha = v;
			break;
		case TRANSPOSUPPER:
			if (v <= alpha)
				return v;
			if (v < beta)
				beta = v;
			break;
		}
	}
}

Enhanced Transposition Cuttoffs (ETCs)

CFour/src/c4/AlphaBetaAgent.java view raw
for (x = 0; moves[x] != (-1); x++) {
	t = zobr ^ rnd[1][moves[x] * 6 + colHeight[moves[x]]];
	long k;
	short v;
	byte f;
	// Hash-Table ist in zwei Stufen unterteilt, daher die

	// Unterscheidung

	if (depth > 13) {
		transPosition = ((int) t & (transPosSize - 1));
		k = key[transPosition];
		v = value[transPosition];
		f = flag[transPosition];
	} else {
		transPosition = ((int) t & (lTransPosSize - 1));
		k = lKey[transPosition];
		v = lValue[transPosition];
		f = lFlag[transPosition];
	}
	if (k == t && f != TRANSPOSLOWER && v <= alpha)
		return v;
}

Accessing the Transposition Table in higher Levels

CFour/src/c4/AlphaBetaAgent.java view raw
int index = ((int) zobr & (transPosSize - 1));
// Check, if current board is in Transposition-Table

if (key[index] == zobr) {
	short v = value[index];
	switch (flag[index]) {
	case TRANSPOSEXACT:
		return v;
	case TRANSPOSLOWER:
		if (v >= beta)
			return v;
		if (v > alpha)
			alpha = v;
		break;
	case TRANSPOSUPPER:
		if (v <= alpha)
			return v;
		if (v < beta)
			beta = v;
		break;
	}
}

Note: Several paragraphs of this blog post are in parts taken from my Master’s thesis or from a translation of my Bachelor thesis and some earlier project work.

Markus Thill

Markus Thill
I studied computer engineering (B.Sc.) and Automation & IT (M.Eng.). Generally, I am interested in machine learning (ML) approaches (in the broadest sense), but particularly in the fields of time series analysis, anomaly detection, Reinforcement Learning (e.g. for board games), Deep Learning (DL) and incremental (on-line) learning procedures.

Deriving a Closed-Form Solution of the Fibonacci Sequence using the Z-Transform

The Fibonacci sequence might be one of the most famous sequences in the field of mathmatics and computer science. Already high school stu...… Continue reading