Tu as en effet des règles qui ont je pense tendance à augmenter la difficulté. Cependant on retrouve des problématiques communes.
Le probleme étant qu'un coup qui rapporte peu de points n'est pas forcement moins bien qu'un coup qui rapport beaucoup de points car ça peut amener un autre coup qui rapporte beaucoup de points (et cela le coup suvant ou 10, 20 ou 30 coups plus tard…)
C'est typiquement pour cette raison que s'arrêter sur un graphe non fini donnait de moins bons résultats que de continuer avec un algo glouton.
Sur tes autres pistes :
- Jouer bêtement : Je ne crois pas trop à cette approche mais ça me fait penser qu'il serait intéressant de mettre en place un réseau de neurones pour qu'il apprenne à reconnaître certains patterns de jeu et voir ce qu'il arrive à en apprendre :). L'avantage c'est qu'une fois qu'il est bien entraîné, il sera rapide. J'ai aucune idée de l'efficacité d'une telle approche et encore moins du temps d'apprentissage nécessaire.
- Brute force :) Ça va dépendre de la taille de ta grille mais si une partie fait environ 20 clics et qu'il y a à chaque clics disons 5 possibilités, ça fait déjà un bon paquet :)
- La dernière solution : cf prob du super coup à k+1.
Je ne me souviens plus de la taille de la grille, mais je dirais de l'ordre de ton mode extra large.
J'ai simplifié mon algo pour les explications, c'était un peu plus compliqué que ce que j'ai annoncé mais je ne m'en souviens plus maintenant :). En tout cas, une bonne source d'inspiration à l'époque c'était un papier de recherche. Je me demande si ce n'était pas : "Single-Player Monte-Carlo Tree Search" de Maarten et al.
[^] # Re: Solveur SameGame-like
Posté par Maxime (site web personnel) . En réponse à la dépêche Bubble Crusher 0.9 bêta release. Évalué à 2.
Tu as en effet des règles qui ont je pense tendance à augmenter la difficulté. Cependant on retrouve des problématiques communes.
C'est typiquement pour cette raison que s'arrêter sur un graphe non fini donnait de moins bons résultats que de continuer avec un algo glouton.
Sur tes autres pistes :
- Jouer bêtement : Je ne crois pas trop à cette approche mais ça me fait penser qu'il serait intéressant de mettre en place un réseau de neurones pour qu'il apprenne à reconnaître certains patterns de jeu et voir ce qu'il arrive à en apprendre :). L'avantage c'est qu'une fois qu'il est bien entraîné, il sera rapide. J'ai aucune idée de l'efficacité d'une telle approche et encore moins du temps d'apprentissage nécessaire.
- Brute force :) Ça va dépendre de la taille de ta grille mais si une partie fait environ 20 clics et qu'il y a à chaque clics disons 5 possibilités, ça fait déjà un bon paquet :)
- La dernière solution : cf prob du super coup à k+1.
Je ne me souviens plus de la taille de la grille, mais je dirais de l'ordre de ton mode extra large.
J'ai simplifié mon algo pour les explications, c'était un peu plus compliqué que ce que j'ai annoncé mais je ne m'en souviens plus maintenant :). En tout cas, une bonne source d'inspiration à l'époque c'était un papier de recherche. Je me demande si ce n'était pas : "Single-Player Monte-Carlo Tree Search" de Maarten et al.