Documentation Intelligence Artificielle de Quoridor

Some of you, programming experts or simply curious, may have wondered how the game on this site was coded. To answer these questions, let's take a look under the hood and see how it works. Initially, the online version of Quoridor was programmed in PHP, but the server didn't handle the AI's large loops very well. So, I rewrote Quoridor in JavaScript, which increased the game's performance at least tenfold. Let's first look at how the Quoridor game board is modeled, then how we check if a player is stuck, and finally, what the AI algorithm is.

Modeling the Game Board

To model the game board, I used an undirected graph. Each square is represented by a node of the graph, and each possible move by an arc with a value of 1. This graph is represented by its adjacent matrix. The 81 nodes (9 x 9) are arranged vertically and horizontally. We therefore have a matrix with 81 rows and 81 columns. For simplicity, I created a 100x100 array. I only use the rows and columns starting from the second row. The first square of the board is therefore square 11 (see diagram). Thus, the first number represents the row and the second the column. Example of square 25: second row, fifth column.

Thus, if a move is possible, the value 1 is placed in the array; otherwise, it will be the value 0. This matrix will therefore represent the adjacent matrix. For example, if it is possible to move from cell 25 to cell 26, then there is a 1 in row 25 and column 26. Concretely, the adjacent matrix in JavaScript corresponds to a list (or an array) of 100 elements, where each element is a list of 100 elements.
Thus, if : Graphe[25][26] = 1          //We can go from box 25 to 26.
And if Graphe[25][27] = 0          //We cannot go from box 25 to 27.
Likewise if Graphe[25][35] = 1          //We can go from box 25 to 35 below.
And Graphe[25][37] = 0          //We cannot go from cell 25 to 37.

When a wall is placed, the graph value changes from 1 to 0 in 4 places, because walls separate 2 squares and passage is bidirectional.

The breadth-first graph traverse

One of the rules of Quoridor is the prohibition against blocking a player.
To verify that a player can still reach a square on the finish line, it is necessary to traverse the graph. There are two types of traversal: depth-first search (DFS) and breadth-first search (BFS). For this game, I chose to use breadth-first search. Some might argue that depth-first search would be faster, but that's my choice.
Le parcours en largeur utilise une File foncionnant sur le principe FIFO (First In First Out ou Premier entré premier sorti). Pour décrire rapidement l'algorithme :

- The first node is placed in the queue, and the search is performed for accessible nodes.
- These nodes are placed in the queue, and the first node is stored in a list to be marked as visited.
- The first node is removed from the queue, and the search is performed on its successors, and so on until the queue is empty.

Here is a JavaScript implementation of breadth-first graph traversal :


//*****************************************************************************************
//       Parcours ou descente en largeur dans le graphe (matrice adjacente)	             //
//*****************************************************************************************		
// initialisation
	game.graphe.init = function (graphe) {
		var visited = [] ;
		for(var i = 0; i < graphe.length ; i++){
			visited[i] = 0; //initialise la liste des noeuds visités à 0 (i est le noeud)
			}
		return visited ;
		} ;

// méthode de descente en largeur
	game.graphe.descenteEnLargeur = function(graphe, start, visited,ligneDestination){
		var valide = false ;
	// creation d'une file vide
		var file = [];
	// intialisation de la file avec le premier sommet
		file.push(start);
		visited[start] = 1;
		var t ;
		var arc ;
		var lignedescente ;
		while (file.length != 0) {
			t = file.splice(0,1) ;    // sort le premier élément de la file
			for(var i =0 ; i < graphe[t].length ; i++) {
				arc = graphe[t][i] ;
				if (visited[i] == 0 && arc == 1) {
					visited[i] = 1;
					file.push(i) ;

    // Partie spécifique au jeu pour vérifier si une ligne est atteinte
					lignedescente = Math.floor(i/10) ;
				if (lignedescente == ligneDestination) {
					valide = true ;		
						}
    // Fin de la partie spécifique à ce jeu
					}
				}
			}
			return valide ;  // return visited ;  //de façon + générale
		} ;

Quoridor's AI Heuristic

The idea is simple: the game's AI determines the shortest path for the two pieces and their respective lengths.
Let D_AVS be the distance the player (the opponent) must travel to the finish line.
Let D_IA be the distance the AI must travel to the finish line.
The algorithm compares the two values if : \[ D_{ADV} < D_{IA} \] Then the AI's pawn moves forward. Otherwise, the program tries to place a wall on the opponent's shortest path. To calculate the shortest paths, I used the Floyd-Warshall algorithm, not Dijkstra's. This is because the Floyd-Warshall algorithm calculates the shortest paths from all nodes in the graph, while Dijkstra's algorithm calculates the shortest paths starting from an initial node. Let's compare the respective complexities of these two algorithms. Number of vertices :
Nombre de sommets : \[ 9 \times 9 = 81 \] Complexity of the Floyd-Warshall algorithm : \[ O(V^3) = 81^3 = 531\,441 \] For Dijstra's algorithm or A*, the complexity is : \[ O(E + V \log V) = 144 + 81 \log(81) \approx 500 \] But we still need to multiply by 9 for the 9 points of the final line, so 9 x 500 = 4500
We can do even better thanks to the "algorithmic cheater's node."
The principle of this trick is to add an extra vertex behind the two finish lines, inaccessible to the pieces but accessible to the algorithms. This node is connected to the 9 final nodes. Thus, a single use of the Dijkstra algorithm towards this hidden node is enough to determine the shortest path in one go. Well, I chose the Floyd-Warschall algorithm, but this will allow me to create a new AI in the future. We're not finished with our AI sequence yet. If the program doesn't find any walls to place, the piece advances along the shortest path. There are still a few strategic subtleties, but I'll keep them to myself, or you'll have to ask me.

Here's a JavaScript implementation of the Floyd-Warschall algorithm :
```
// *********************************************************************************************************/
// algorithme de Floyd Warshall pour trouver les plus cours chemin dans le graphe à partir d'un sommet     */
//**********************************************************************************************************/

	game.graphe.FloydWarshall =function(grapheJ){
		var jeuG = grapheJ ;
		var INFINI = 1000 ;
		//var len = jeuG.length ;
		var len = 100;
		var valeur ;
		var chemins = [];
		var dist = new Array(100);
		for (var i = 0 ; i<=99 ; i++) {
				dist[i] = new Array();
			}
		var pred = new Array(100);
		for (var i = 0 ; i<=99 ; i++) {
				pred[i] = new Array();
			}
// boucles d'initialisation de l'algorithme
		for (var i=0 ; i < len ; i++) {
			for (j=0 ; j < len ; j++) {
				pred[i][j] = j ;
				dist[i][j]  = INFINI ;
				if((jeuG[i][j]) == 1){
					valeur = jeuG[i][j];
					dist[i][j] = valeur;
					}
		
				}
			}
// boucles de détermination des plus courts chemins de l'ensemble du graph (distances et chemins)

	for (var k = 0; k < len; k++){
			for (var i = 0; i < len; i++) {
				for (var j = 0; j < len; j++) {	
				if (dist[i][j] > (dist[i][k] + dist[k][j])) {
					dist[i][j]= (dist[i][k] + dist[k][j]) ;
					pred[i][j] = pred[i][k] ;
						}
					}
				}
			}
			chemins[0] = dist ;
			chemins[1] = pred ;
			return chemins ; 
		}		;

//**************************************************************************************//
// Recherche des chemins les plus courts à partir des sommets initiaux et finaux        //
//**************************************************************************************//
	game.graphe.courtChemin = function (start, end, pred){
			var chemin = [];
			chemin.push(start) ;
			suivant = pred[start][end] ;
			chemin.push(suivant) ;
		while(suivant!=end){
			suivant = pred[suivant][end];
			chemin.push(suivant) ;
			}
		return chemin ;
			}	

		 
```

Please leave your comments with your feedback and suggestions :

The Algorithms of Quoridor.fr

Modeling the Game Board

The breadth-first graph traverse

Quoridor's AI Heuristic