Incremental Updating of Objects in INDIGO

B. bouzy

IBP-Laforia 1996/28: Rapport de Recherche Laforia / Laforia research reports
9 pages - Mars/March 1997 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Incremental Updating of Objects in INDIGO

Résumé : Ce rapport décrit la mise à jour incrémentale des données utilisée par le programme de Go Indigo. A cause de la taille du goban et des contraintes de temps, les mécanismes incrémentaux sont intéressants pour effectuer cette mise à jour. La mise à jour d'une position comprend la construction d'une hiérarchie d'objets reliés par un grand nombre de dépendances. L'approche classique consiste à parcourir la hiérarchie des objets pour les mettre à jour. Dans Indigo, nous utilisons une approche différente basée sur les caractéristiques spatiales du jeu de Go. Chaque objet est un "objet posé" avec un "lieu" et une "trace". Celle-ci n'est autre que l'ensemble des intersections desquelles dépend l'objet. Quand un coup est joué quelquepart sur le goban, le programme ne parcourt pas la hiérarchie des dépendances. Il utilise les "traces" des objets. Les objets dont la trace rencontre le lieu du dernier coup joué sont détruits et seulement eux. Ce mécanisme allège la tâche du programmeur en repoussant le problème de l'incrémentalité dans la spécification des traces des objets, il réduit sensiblement le temps de réponse d'Indigo, par un facteur moyen de 20 environ sur des gobans 19x19, et enfin il ne modifie pas le niveau de jeu d'Indigo.

Abstract : This paper shows the incremental updating that is used in the Go playing program Indigo. Due to the size of the board and time constraints, incremental mechanisms are relevant to update data. The evaluation of a position includes the construction of a taxonomy of objects which are linked by a lot dependencies. Classical incremental approaches use browsing of the taxonomy to update objects. In Indigo, we use a different approach that use the spatial features of the game of Go. Each object is a "relying object" with a "location" and a "track". The later is the set of intersections on which the object depends. When a move is played somewhere on the board, browsing dependencies is not necessary and "tracks" are used instead. The objects whose track meets the location of the move are deleted and the other ones are not. This mechanism simplifies the task of the programmer in pushing the incrementality problem into the specification of the track of each class of objects. This mechanism slightly reduces the response time of Indigo by a ratio of about 20 on 19x19 boards without modifying the play of the program.

Publications internes Laforia 1996 / Laforia research reports 1996