[Eliot-dev] Re: optimisation board_search

[Olivier Teuliere]

Bonjour,

2009/1/12 Philippe Chataignon <address@hidden>:
> De mon côté, depuis plusieurs années, je suis reparti d'Eliot pour en
> faire un générateur de parties qui alimente ensuite un serveur et des
> clients (en Python et avec wxpython pour le client) pour jouer en
> duplicate (à l'occasion je peux fournir ces programmes à ceux qui sont
> intéressés).

J'envisage d'intégrer une architecture client-serveur dans une future
version d'Eliot, donc vos programmes Python pourront peut-être me
donner des idées...

> Je suis reparti de la version 1.4 en C et j'utilise les programmes
> sous dic/ et game/ mais pas l'interface graphique. J'ai regardé les
> programmes de la version 1.7a et j'ai vu qu'il y avait une
> optimisation dans board_search. J'ai transposé cette optimisation en C
> et je me suis rendu compte qu'il y avait un problème quand il y avait
> un joker dans le tirage. Je me suis dis que c'est ce qui avait
> justifié le passage de la 1.7 à la 1.7a et j'ai regardé les
> modifications.

L'optimisation est en place depuis relativement longtemps (version 1.5
je pense).
Ce n'est pas ça qui a causé le bug de la version 1.7, mais un manque
de distinction entre le joker pur (méthode Tile.isPureJoker()) et un
joker associé à une lettre (méthode Tile.isJoker()).

> Ma question est : n'y a-t-il pas encore un problème avec le deuxième
> terme qui vaut True si le dernier bit de m_mask vaut 1 (la lettre a
> est dans le masque de cross ? dans la version C il est toujours à 0).
> Ne vaut-il pas mieux avoir seulement :
> return m_mask & (1 << iTile.toCode()) || (iTile.isPureJoker());

Je pense que ce test est nécessaire. Tout d'abord, il s'agit d'un "et"
logique, et non pas d'un "et" binaire, ce qui fait que la lettre A
n'est pas privilégiée par rapport aux autres.

L'idée derrière ce test est qu'un joker pur (non encore associé à une
lettre au sein d'un mot) matche n'importe quel masque de cross _sauf_
le masque vide. Par exemple, si le mot COQ est placé en H6, la case I8
aura un cross-check vide (aucun mot de 2 lettres ne commence par Q).
Un mot horizontal ne pourra pas passer par la case I8, même si c'est
un joker qui est placé sur la case.

En pratique, supprimer ce test ne fausse pas les résultats de
recherche, parce que le seul cas d'utilisation de la méthode check()
est justement l'optimisation dont vous parlez. Cette optimisation
consiste à éviter certains calculs (la formation des débuts de mots)
lorsqu'on est sûr par avance qu'ils ne mèneront à rien, mais si l'on
n'est pas sûr (i.e. si le cross-check matche avec la lettre courante)
on fait quand même les calculs. La seule incidence de la suppression
du test est donc de "moins optimiser" : certains calculs qui
pourraient être évités ne le sont pas.

Pour vous en convaincre, vous pouvez placer un log après la ligne "if
(match)" (ligne 284) dans board_search.cpp.
En faisant une recherche avec le tirage "?R", lorsque COQ est placé en
H6, on passe 13 fois dans le if, contre 16 fois si on supprime le test
dans la méthode check().

Si mes explications ne sont pas claires, n'hésitez pas à le dire :-)

Cordialement,
-- 
Olivier