Nous abordons ici les différentes méthodes de la classe Game et de ses sous-classes qui peuvent être implémentées afin d'optimiser la recherche des meilleurs coups par l'algorithme alpha-bêta.
Implémenter ces méthodes n'est pas obligatoire mais est toutefois vivement conseillé dans la mesure où les gains pour l'exploration de l'arbre des coups sont loin d'être négligeables : à arbre de coups de taille équivalente, le nombre d'évaluations de plateau peut atteindre une réduction de 70%. Il faut toutefois noter que le gain engendré est très dépendant du type de jeu implémenté : ainsi un arbre de coups présentant des situations de symétrie peut bénéficier grandement de ces optimisations.
La première optimisation réalisée par le joueur AlphabetaMemoryPlayer est l'utilisation d'une table de transposition pour le stockage des plateaux : cette table de hachage associe à des plateaux des informations sur celui-ci (note attribuée par le plateau, types d'élagage réalisé dans l'arbre des coups, meilleur coup réalisable à partir du plateau).
L'algorithme alpha-bêta de parcours d'arbre des coups est exécuté par profondeur itérative : l'arbre de hauteur 0 est tout d'abord exploré, puis l'arbre de hauteur 1, ... Pour chaque plateau de jeu, on enregistre dans la table des informations utiles permettant d'accélerer le déroulement de l'algorithme alpha-bêta pour la profondeur suivante ainsi que pour le déroulement courant de l'algorithme en évitant le recalcul de branches identiques (exploitation de symétries).
Naturellement, on limite la taille de la table qui ne peut être utilisée que pour les premiers niveaux de l'arbre en raison de la croissance exponentielle du nombre de feuilles lorsque la profondeur augmente.
Afin de pouvoir utiliser une table de hachage des plateaux de jeu (instances de Game.Board), il est ainsi nécessaire de définir pour un plateau une fonction de hachage associant à ce plateau un entier int. D'autre part, afin de stocker les plateaux dans la table, il est nécessaire de pouvoir les cloner.
Un plateau dérivant de Game.Board surchargeant les méthodes int hashCode() et boolean equals(Object) doit implémenter l'interface marqueur Hashable.
Par défaut, la classe Object, ancêtre de tous les objets Java, dispose d'une méthode int hashCode() retournant un entier utilisé comme valeur de hachage.
Soit deux références vers des instances de Object o1 et o2, si o1 et o2 sont des références vers la même instance de Object alors o1.hashCode() = o2.hashCode(). La réciproque est fausse : deux instances différentes de Object peuvent posséder le même hashCode (la fonction de hachage n'est pas injective).
Afin de pouvoir utiliser une table de hachage des plateaux de jeu, nous souhaitons utiliser une fonction de hachage portant sur le plateau représenté par l'instance de Game.Board et non pas sur sa référence (adresse mémoire). Il est donc nécessaire de surcharger la méthode hashCode().
Pour implémenter l'algorithme de hachage, il est possible de sommer les différents hashCode des objets membres de l'instance. En particulier, l'usage de la classe HashableArray est particulièrement utile car il est possible d'obtenir en temps constant sa valeur de hachage (celle-ci étant calculée au fur et à mesure lors des modifications des valeurs du tableau).
La fonction de hachage implémentée n'étant généralement pas injective (l'injectivité de la fonction de hachage étant impossible à obtenir si le plateau peut présenter plus de 2^32 positions différentes), il est indispensable d'implémenter la fonction de test d'égalité de plateaux boolean equals(Object o). Cette méthode retourne true si et seulement si le plateau courant et le l'object o sont de même type et représentent des situations de jeu identique (contenu des plateaux strictement identique : pièces du jeu au même emplacement, même joueur devant jouer pour le prochain tour,...).
Uniquement si l'on a l'assurance de l'injectivité de la fonction de hachage, il est possible de retourner (o instanceof Game.Board && this.hashCode() == o.hashCode()).
Même si cela n'a pas d'influence sur l'utilisation de l'algorithme alpha-bêta avec mémorisation des plateaux, il est déconseillé de retourner inconditionnellement true en cas d'injectivité de la fonction de hachage, dans la mesure où le contrat de Object défini par l'API Java n'est alors plus respecté.
Le stockage des plateaux dans la table de transposition nécessite la possibilité de les cloner.
Tout plateau dérivant de Game.Board et réalisant une surcharge de la méthode Object Game.Board.Clone() doit implémenter l'interface marqueur Cloneable.
La méthode Object Game.Board.clone() doit retourner un nouveau plateau de jeu. La méthode clone() issue de Object réalise uniquement un clonage superficiel (shallow cloning) dans la mesure où les références des membres objets sont copiés et non les membres objets eux-mêmes. Ceci est particulièrement problématique pour les tableaux qui ne sont donc pas copiés : c'est pourquoi il est conseillé de faire appel aux tableaux représentés par la classe HashableArray : il suffit alors de faire un appel à la méthode clone() de HashableArray dans la méthode clone() de Game.Board.
Chaque classe dérivée de Game.Board doit donc surcharger la méthode clone() afin de réclamer le clonage de chacun des ses objets membres.
Il est déconseillé de cloner les instances des joueurs (instances de Player) au sein de la méthode clone() du plateau.
Malheureusement la gestion automatique du clonage profond n'est pas prise en compte par l'API Java. Néanmoins certaines astuces utilisant la sérialisation auraient permis d'automatiser le clonage profond, au prix toutefois d'un ralentissement considérable.
La table de transposition est uniquement utilisée pour un plateau dérivant de Game.Board implémentant à la fois les interfaces Cloneable (interface définie dans l'API Java) et Hashable. Si une de ces interfaces n'est pas déclarée implémentée par la classe du plateau, aucune optimisation par l'usage de la table de transposition n'est réalisée, même si les méthodes clone(), hashCode() et equals() sont surchargées.
La méthode Game.Board.getLegalMoves() retourne la liste des coups légaux dans un ordre indéterminé. Cependant afin d'améliorer l'efficacité de l'algorithme alpha-bêta, il est intéressant que les coups soient ordonnés par ordre d'efficience décroissante : cela permet de réaliser un élagage plus efficace de l'arbre des coups.
Il est donc intéressant d'introduire pour les coups manipulés une fonction de valuation empirique de l'efficience du coup : plus le coup possède un potentiel bénéfique pour le joueur courant, plus sa valuation est élevée.
Cette méthode n'est pas déclarée abstraite dans Game.Board.Move : elles est déjà implémentée et retourne pour chaque coup une valeur aléatoire. Ainsi en l'absence de surcharge de cette méthode, la liste des coups sera exploré par l'algorithme alpha-bêta dans un ordre aléatoire. Il est donc alors possible d'obtenir des parties différentes à contrainte de profondeur d'exploration identique.
Afin d'améliorer l'efficacité de l'algorithme alpha-bêta, il est conseillé de surcharger cette méthode afin qu'elle retourne une note empirique pour le coup courant. Le calcul de cette note empirique doit être très rapide : il s'agit juste d'une estimation de l'efficience du coup, une erreur dans cette estimation n'ayant aucune influence sur la justesse du meilleur coup trouvé par l'algorithme.
En prenant l'exemple des échecs, une fonction de valuation convenable pourrait être de considérer la valeur de l'éventuelle pièce capturée lors du coup. Si aucune pièce n'est capturée, on pourra retourner une valuation faible pour le coup, tandis que si une pièce d'importance stratégique est capturée à l'adversaire (sa reine par exemple), la valuation du coup sera élevée.