Salut à tous !
Je suis en train d'implémenter l'algorithme Proof Number Search pour l'utiliser sur un certain jeu de plateau (une variante du Go-Moku, en gros).
Sauf que le draw est possible, et PNS ne le gère pas de base.
On m'a dit de faire "deux PNS" pour gérer le draw, mais d'une ça va être super lent, et de deux y'a un truc que je comprends pas c'est comment le premier algorithme s'arrête s'il trouve pas de gagnant ni de perdant puisqu'il continue tant que pn vaut pas 0 ou Infini ?

Donc pour pallier à ça j'ai changé un peu la fonction de descente : on met à 0 si gagnant, Infini si perdant, 1 si rien et -Infini si draw.
Il faut savoir que pour qu'il y ait draw, il faut absolument que tout le plateau soit rempli: donc on "sait" quand il y a draw. (le dernier coup a été joué et il n'y a pas de gagnant)
J'utilise -Infini comme "signal" en fait : si toute la chaîne à partir de la position renvoie -Infini, alors dans le noeud précédent on va les additionner (oui bon, heureusement mon infini est de l'ordre de 40Millions donc il peut les additionner dans un int sans souci, mais au pire je pourrais faire un truc rapide avec minimum, enfin bon c'est du détail) et obtenir "moins que -Infini", donc on saura qu'il y a draw.

Le hic, c'est que c'est un peu une bidouille, au final. Qui m'a l'air de marcher (et qui dit bien quand il y a draw, testé sur un plateau 3*3 où le draw est évident puisqu'impossible d'aligner 5 pierres dans ce cas par contre ce qui me fait peur ce sont les "faux positifs") mais j'ai pas de preuve. Et donc, pour finalement en venir à ma question : est-ce que ma bidouille met en danger la "véracité" de mes résultats ?
Si oui, est-il préférable de faire "un deuxième PNS" ou tout simplement de ne pas gérer le draw et de partir du principe que le résultat sera Infini ou 0 ? (sachant qu'en jouant plusieurs dizaines de fois au jeu contre différents adversaires, je n'ai jamais obtenu le moindre draw, ça semble quand même probable, mais théoriquement il est possible surtout si on commence à réduire la taille du plateau)

Merci d'avance pour vos réponses.

P.S. J'ai cherché sur Google, il y a très peu de réponses qui traitent d'implémentation et surtout, qui traitent de PNS "basique". Tout semble concentré sur df-pn, mais étant donné que mon PNS fonctionne en l'état actuel à l'exception de ce "détail", je préfèrerais ne pas avoir à tout changer. ^^

L'article reference dans wikipedia semble avoir le nul de considere:

http://en.wikipedia.org/wiki/Proof-number_search

C'est un autre algo en fait. Plus complexe, donc qui gère naturellement le draw. Mais euh, j'ai déjà un peu galéré à implémenter la version simple donc j'hésite à tout supprimer pour recommencer avec un autre algo, surtout pour une situation qui n'arrive peut-être jamais.

Ceci dit, je viens de tester et ma bidouille marche pas dans une configuration où une défaite ET un draw sont possibles selon le jeu. Ca marche que si le draw est le seul résultat possible... ce qui n'est bien évidemment pas le cas sauf sur un plateau de taille inférieure à 5.

Bref, je vais voir si je peux ajouter un "fix" assez simple à mon truc, sinon je tenterai le double-PNS en espérant qu'en fait y'en ait pas besoin.

Hm bon et bien finalement ma solution a l'air de marcher.
J'ai fait les tests suivants :
-Draw forcé dans tous les cas (plateau 3*3) : trouve le draw.
-L'un des joueurs peut forcer le draw s'il ne fait pas d'erreur, mais perd s'il en fait : trouve le draw.
-L'un des joueurs peut gagner s'il ne fait pas d'erreur, mais l'autre peut draw s'il en fait : trouve la victoire/défaite.

Pour info si jamais ça intéresse quelqu'un (ce topic étant le premier résultat Google avec "Proof Number Search draw" et le 4e sur "PNS draw"), voici l'idée générale :
-Lorsque l'on trouve un draw (ce qui dans mon cas correspond à un plateau où toutes les cases sont remplies et il n'y a aucun alignement de 5 pierres de la même couleur), on met à la fois pn et dn à -Infini.
Du coup j'ai les lignes suivantes dans ma fonction "descente" :
else if (plateau.verifierGagnant(depth) == -1) //-1 correspond au draw, au-dessus j'ai le cas 1 et 2 qui correspondent aux gagnants normaux
{
fichier << "Draw sur ce plateau : " << endl;
plateau.afficherTXT(fichier);
n->pn = -Infini;
n->dn = -Infini;
}
Avec ceci, je détectais aisément le draw forcé mais ça plantait dans le cas du second test cité au-dessus.

-Dans la deuxième partie de l'algorithme (le traitement du noeud), j'ai rajouté le code suivant :
if (pn <= -Infini || dn <= -Infini)
{
dn = -Infini;
pn = -Infini;
}
(l'Infini étant un #define arbitraire mais très grand puisque l'on doit créer un tableau de cette taille)
Ce code est présent à la fois pour les noeuds ET et les noeuds OU, il "harmonise" le résultat de manière à ce qu'on n'ait pas "-infini -1" ou "-infini +2", qui sont des résultats qui font bugger l'algorithme (du moins dans mon implémentation, un fix "inverse" où on garde les résultats mais change leur interprétation est peut-être également envisageable)

Ca semble pas super intuitif ni super pro, mais ça a le mérite de marcher.

Bref, topic résolu.

Ca me semble raisonnable. Pour l'interet general, peux tu expliquer ce qu'est une PNS et pourquoi c'est potentiellement plus interessant qu'un autre algo du meme genre?

(C'est gentil de me préparer à mon oral de stage )
Donc, PNS (Proof Number Search) est un algorithme servant à déterminer la valeur théorique d'un jeu : joueur 1 gagne, joueur 2 gagne, ou nul, en supposant que les deux joueurs ne fassent pas la moindre erreur. Il a par exemple été utilisé pour démontrer que le premier joueur gagne toujours au puissance 4. (en parallèle d'une autre méthode, qui elle utilisait des connaissances spécifiques au jeu pour "jouer parfaitement", ce qui n'est pas toujours possible quand le jeu n'est pas aussi simple que Puissance 4)

L'algorithme fonctionne un peu comme un mini-max : les noeuds max (où on joue notre coup) deviennent des noeuds OU, et les noeuds min deviennent ET.
On descend l'arbre de jeu de la racine jusqu'à la fin (la racine correspond typiquement à la position initiale mais rien n'empêche de lancer l'algorithme en milieu de partie). Chaque noeud possède deux attributs : pn (proof number) et dn (disproof number) qui correspondent au nombre de noeuds à évaluer pour prouver la victoire (resp. la défaite) du joueur.
Les noeuds sont initialisés avec pn = 1 et dn = 1.
Dans le traitement d'un noeud OU, pn reçoit le minimum des pn des autres fils (il suffit qu'un seul fils ait une séquence gagnante forcée pour que le noeud traité soit aussi gagnant) et dn reçoit la somme des dn des fils, et inversement lors d'un noeud ET. (il faut que tous les fils d'un noeud ET soient gagnants pour que celui-ci le soit également)
Lorsqu'on arrive à un noeud terminal, on met pn à 0 et dn à Infini s'il est gagnant, et l'inverse s'il est perdant.
Les valeurs sont remontées jusqu'à ce que la racine vaille 0 ou Infini, auquel cas on connaît le résultat du jeu.

Ici, j'ai rajouté un traitement particulier à chaque noeud visant à gérer le nul, mais là tout de suite j'ai pas de quoi expliquer formellement l'idée derrière. Grosso-modo, l'idée principale est que le nombre -Infini est utilisé comme "signal" de la même manière que 0 et Infini, avec quelques bidouilles parce que l'algo est pas censé utiliser des nombres négatifs à la base.
Je sais que ça fonctionne en tout cas, donc restera plus qu'à formuler joliment la preuve.

Pour la deuxième question : concrètement, plus personne utilise PNS de manière sérieuse. Pourquoi ? Parce qu'il a des besoins ABSURDES en mémoire (on sauvegarde tout l'arbre de jeu, j'ai donc un magnifique tableau de plusieurs millions d'entrées dans mon programme, avec un compteur qui décroit et si on atteint 0, arrêt du programme), donc on a développé des variantes. Il y a notamment PN² qui consiste à faire un PN à deux niveaux, et df-pn qui fait une recherche en profondeur d'abord.
Les deux algorithmes consomment moins de mémoire mais PN² est plus lent, alors que DF-PN est plus rapide. Il est aussi beaucoup plus complexe, c'est pourquoi j'ai préféré rester sur un PNS basique dans cet exemple, étant donné que c'était un peu la première fois que je bossais avec ce genre d'algo, et que le jeu sur lequel je travaille n'est pas ultra-compliqué. (facteur de branchement maximum de 4*T, avec T la taille d'un côté du plateau, donc en 9*9 ça donne 9*4 = 36 coups possibles grand maximum, on est loin des échecs ou du jeu de Go)

P.S. Je pense que ma gestion du draw ne serait pas adaptée à tous les jeux : en effet, ici on sait quand la partie est terminée rien qu'en comptant les pierres sur le plateau. Au Go (où on peut capturer) ou aux échecs (où une partie peut durer 3 coups comme 150) ça ne marcherait sûrement pas parce que le draw est bien plus difficile à "détecter".

P.P.S. Avant d'implémenter PNS j'ai aussi fait un alpha-bêta qui se contente de jouer au jeu (pas de prouver sa valeur théorique). Ca s'est révélé très utile car je réutilise la fonction d'évaluation pour PNS, spécifiquement pour trier les coups. En effet, c'est beaucoup mieux de tester les meilleurs coups en premier puisqu'on a plus de chance de trouver le résultat final. On perd du temps à appeler la fonction d'évaluation (qui est relativement lourde avec plein de conditions partout) mais on en gagne en divisant très fortement le nombre de descentes à effectuer.

P.P.S Oh, un formulaire expiré, ça faisait longtemps.

Pavé César, ceux qui n'ont pas lu...

supposons que l'arbre tienne en memoire. quel est l'interet de PNS par rapport a minmax?