Discussion :

[georges_jung]

Je souhaite adapter les algorithmes MiniMax et AlphaBeta sur un jeu que m'a proposé un de mes professeurs : le jeu du carré noir et blanc. En effet, il est peu original de l'appliquer sur TicTacToe ou sur Puissance 4.

Le principe du jeu est le suivant :

La situation de départ est un carré de n*n cases blanches ou
noires, avec n une puissance de 2.
Le premier joueur élimine la moitié gauche ou droite du carré. Le second
joueur élimine la moitié basse ou hautedu rectangle restant, et ainsi de suite jusqu'à ce que le second joueur laisse une dernière case. Si elle est blanche,
il a perdu, si elle est noire, il a gagné.
Les cases noires et blanches sont tirées au hasard. Il est intéressant de les tirer avec une probabilité "p" et "1-p" et de voir pour quelle valeur de "p" le jeu passe brusquement d'un équilibre statistique à une victoire presque certaine de l'un des deux joueurs.

J'aurai aimé savoir si quelqu'un avait déjà développé un tel jeu pour me conseiller ou connait un site détaillant un peu plus précisément celui-ci car je n'ai pas encore trouvé de sites traitant du sujet sur internet...

Merci d'avance...

[georges_jung]

Au pire si quelqu'un connaitrait le nom de ce jeu en anglais ca serait sympa...

[jobherzt]

je ne sais pas si tu as tellement besoin d'autres informations sur ce jeu... au pif je dirais :

- la mauvaise nouvelle, c'est qu'il ne semble pas y avoir de vraie strategie, a vue de nez je ne pense pas par exemple que choisir le cote qui contient le plus de case de la "bonne" couleur soit avantageux. donc a priori, en alpha beta, tu n'auras pas beaucoup d'elagage et tu devras aller jusqu'au bout pour en deduire quelque chose.

- la bonne nouvelle c'est que le nombre de coups d'une partie est faible (si n=2^k, alors il faudra k coups pour atteindre la derniere piece). sachant qu'a chaque coup il n'y a que 2 possibilité, le nombre de coups a tester va etre en O(2^k), c'est a dire en gros en O(n). moralité, meme avec un grand nombre de case, ca reste une complexité vachement raisonnable, donc meme avec un minimax un peu bourrin tu devrais t'en sortir a l'aise, tout en ayant suffisamment de cases pour que ton analyse probabiliste aie un sens.

[georges_jung]

Merci de tes nouvelles...

Pour la compléxité, c'est ce que je pensais, il ne faudra pas énormément de coups pour atteindre le résultat...
Cependant, je vais aller demander a mon prof s'il n'existe pas quand meme une heuristique pour ce jeu... Ca m'étonnerai qu'il me donne un coup de main comme ca mais ca ne coute rien d'essayer

[pseudocode]

Au pire si quelqu'un connaitrait le nom de ce jeu en anglais ca serait sympa...

ca m'a tout l'air d'etre une variante du jeu de Marienbad (ou "nim" en anglais)

[mchk0123]

pseudocode je pensais à la même chose.

En tout cas pour ce qui est du jeu de marienbad, dés la configuration de départ et sans autres calculs il existe une formule donnant le vainqueur à coup sur s'il ne fait pas d'erreur (et donc aussi, par corollaire, le meilleur coup à jouer à chaque étape).

Cette formule est à base de décomposition binaire (mais je me rappelles plus exactement comment on fait). Une petite recherche google devrait donner le bon lien.