Notion Solveur (niveau avancé).

[Kloug]

Salut,

La réalisation d'un petit jeu peut vite tourner au casse tête, la notion indispensable à savoir, est celle du solver en anglais, ou résolveur en français.

Un solver c'est quoi?

Pour ma part dans un moteur de jeu vidéo, il en existe des tas, le plus simple des solveurs est du genre, plus d'objets "truc" dans la scène, scène suivante, mais plus sérieusement cela peut être un solveur de grille de Sudoku.

Ce genre de solveur étant plutôt complexe et hors de ma portée (humour), je vous propose de voir le résolveur du jeu Tic Tac Toe (jeu de morpion).

Pour notre culture générale...
http://fr.wikipedia.org/wiki/Tic-tac-toe_%28jeu%29

Pour ce faire, le principe de l'intelligence artificielle, réduite à un placement au hasard, d'un pion PC, à l'aide d'un layer (une couche).

X( "Layer" )+((Random(192)/64)*64)
Y( "Layer" )+((Random(192)/64)*64)

Une couche (en vert fluo) permet souvent de réduire les conditions.

Maintenant que l'I.A (niveau très faible) est fiable, comment vérifier la grille du Tic Tac Toe?



Un actif "Rider" se déplace sur les trois horizontales, les trois verticales, les deux diagonales.

Chaque fois que l'actif "Rider" est en collision avec un pion, MMF ajoute plus un à une variable.
La variable a pour valeur trois, victoire pour le joueur ou l'ordinateur.

Voilà une solution "simple", elle confirme deux choses.

1) Cerner, définir correctement le problème.

2) Résoudre le problème avec un solveur réaliste (rapide).

La méthode adaptable a beaucoup de petits jeux est celle du moteur de déplacement autonome, avec comptabilité des collisions.

La mise en pratique (pas du genre facile pour un débutant à cause des variables):
Tic Tac Toe (28 lines).
http://files.getwebb.org/download.php?id=cre63bce

Merci de votre attention.

A+++

[Patrice]

Très interressant, merci pour ta contribution, j'avoue que je suis un peu frustré, l'IA est vraiment très basique.

Si je me souviens bien la seule solution connue pour ce genre d'IA c'est de tester toutes les hypothèses du joueur et de se placer en fonction.

Penses-tu pouvoir apporter une autre approche avec ta méthode pour arriver à une IA plus coriace ?

Merci

[Kloug]

Merci infiniment pour ton message Patrice.

L'I.A de l'exemple existe pour le solveur (moteur de déplacement autonome, comptabilité des collisions).
Avec un I.A plus élaborée, ce genre de solveur devient obsolète.

"Si je me souviens bien la seule solution connue pour ce genre d'I.A c'est de tester toutes les hypothèses du joueur et de se placer en fonction."

Je ne vois effectivement pas d'autres alternatives, pour une I.A toujours victorieuse.

Avec la méthode proposée, il est possible par exemple, d'occuper d'emblée la case centrale une fois sur deux, de contrer parfois le joueur, sans pour autant "klik" coder des centaines de lignes.

Donc oui, il est possible d'obtenir une I.A, un peu plus coriace avec l'exemple proposé, sans passer par une analyse de grille, donc des routines suivant les cases occupées par le joueur.

Je vais essayer de mettre en pratique mes propos, dès que possible.

En attendant pour comparer, il y a celui de Nirl:
http://www.castles-of-britain.com/tictactoe.mfa

Je ne l'ai pas encore regardé en détail, ni testé sérieusement.

[Patrice]

Oui, je connaissais cette source. Je me dis que ça pourrait être super interressant de trouver une IA pour des TicTacToe étendus sur des grilles plus grandes, comme les bons vieux jeux que nous faisions sur les feuilles à carreaux pendant les cours qui n'en finissaient plus...
Tiens nous au courant de tes avancées, c'est très interressant.

[Kloug]

Le solveur (sujet du post) est devenu plus simple (à capter) mais moins rapide.
Réduit avec le mode 2 joueurs à 9 lignes.
http://files.getwebb.org/download.php?id=cre63b58

Il y a une différence notable entre vérifier une grille, et analyser une grille, le solveur proposé permet seulement de vérifier l'état d'une grille. Il confirme ou infirme une succession de trois pions.

L'analyse d'une grille se fait afin de jouer, le meilleur coup suivant possible.
Avec un nombre de pions limité (9), une grille 3x3, c'est réalisable avec un petit niveau de programmation.

L'I.A d'un jeu de morpion, 5 pions à aligner, c'est l'analyse d'une grille de grande taille, là à mon humble avis, mise au point d'un algo.

Avec une extension qui permet de comptabiliser les connections, il suffit de contrer le joueur, de marquer le premier point.

http://www.paranoland.com/jeux/flash/2882-morpion-reflexion.html

Dans ce cas on évite soigneusement le plus dur...

Ce genre de jeu est distrayant à deux ou plusieurs, contre une I.A optimisée cela devient vite soulant.

En tous les cas Patrice merci de ton retour, même si l'I.A du Tic Tac Toe, se fait plus coriace, elle ne conviendra pas pour aligner 5 pions.

Edit:

Le Tic Tac Toe de Nirl, fait beaucoup de lignes, en gros d'après le nombre de pions sur la grille et les cases occupées, MMF place le pion PC (meilleur coup possible).
Mon I.A pas terrible laisse au moins un peu d'espoir au joueur de gagner (mdr).

Trois niveaux de difficulté, semblables ou pratiquement semblables, pas de mode 2 joueurs, sinon très belle réalisation pour un Tic Tac Toe.

L'utilisation d'un "vérificateur" ou solveur peut paraître sans intérêt, mais pour un jeu de puzzle, un atomix, un slider, une grille sudoku, etc, il permet de réduire le nombre de lignes.
Par exemple un puzzle fait 100 pièces, répartir une valeur dans une variable (variable différente pour chaque pièce), vérification de la variable de 1 à 100, via un moteur de déplacement autonome et le tour est joué.

Le cas du Tic Tac Toe est particulier, ça change de l'ordinaire (lol).

[Kloug]

Resalut,

Je ne m'excuse pas de double poster, évidemment pour plus de lisibilité et afin d’éclaircir certains points difficiles à comprendre.

Comme constaté plus haut, il existe plusieurs façons de réaliser un solveur, il peut simplement vérifier l'état d'une grille, ou résoudre une problématique.

Sans jouer les pointilleux, vérifier n'est pas résoudre, c'est avec cette nuance qu'un "klik" codeur va mettre en place un solveur, inutile d'utiliser un tank pour pousser une porte, tout dépend des objectifs à atteindre.

Bien sûr, une fois qu'une grille est vérifier, il est possible de la valider, valider n'est pas résoudre une problématique.

C'est aussi avec cette nuance qu'une I.A se conçoit avec le Tic Tac Toe, car certaines I.A sont des résolveurs de quoi semer la confusion chez un "klik" codeur.

Voilà pourquoi mon choix du Tic Tac Toe, merci à mon ami Patrice d'avoir levé un lièvre.

L'extension pathfinding, est une I.A incapable de résoudre la problématique posée par le Tic Tac Toe, l'extension Advanced Game Board (AGBO) a la même incapacité, à savoir jouer le meilleur coup possible.

L'extension pathfinding résout la problématique du chemin le plus court, l'extension AGBO résout la problématique d'une connexion entre actifs.

En gros un solveur "vérificateur" (validation) est adaptable à tous les projets, un solveur "résolveur" est forcément spécifique à une problématique.

Mettre au point une I.A optimisée pour un Tic Tac Toe peut se faire avec un tableau de type booléen, afin de jouer le pion PC (meilleur coup possible).
A mon humble avis cette méthode réduirait considérablement le nombre de lignes, et là plus besoin d'un moteur de déplacement autonome (avantage >> coup suivant instantanément affiché).





Ces deux possibilités de perdre totalisent 5 lignes fastidieuses...

A la place des tuiles, des couches, pourquoi pas?

Mais quel est l'intérêt d'une I.A incapable de perdre?

Tic Tac Toe de Nick (Vérificateur >> Objet tableau).
http://www.clickteam.com/creation_materials/tutorials/download/TicTacToe.mfa

Tic Tac Toe d'Andos (Vérificateur >> AGBO).
http://files.getwebb.org/download.php?id=cre63apx

Quand je fais un exemple cela découle d'un travail de fond, d'une synthèse, histoire de rendre accessible au plus grand nombre une notion.
Ceci n'est hélas pas toujours possible, je donne alors un "mode d'emploi".

Là, il y a un résolveur (une partie) afin de gérer les plans sur une map iso.
http://clickmoteur.blogspot.fr/2011/01/gestion-des-plans-un-classique.html

Mes exemples utilisent rarement une extension car la majorité sont compatibles avec TGF2.
http://clickmoteur.blogspot.fr/2012/10/klik-examples-for-tgf-mmf.html

Au risque de le répéter, avec TGF, MMF, tout ne peut pas se résoudre à grand coup de programmation, puisque la colonne vertébrale est l'éditeur de scène, la problématique du Tic Tac Toe confirme cette évidence.

Contrer systématiquement le joueur à l'aide d'un solveur "vérificateur" (inconvénient >> affichage du coup suivant plus lent), me semble la meilleure option car elle fera peu de lignes, mais on obtient aussi une I.A optimisée, bref à moins de mettre une pincée de "débilité" le joueur n'a aucune chance de gagner, j'ai peut être eu la main lourde dans mon exemple (mdr).

En espérant que mes explications ne sont pas trop "roxor".

A+++

[Kloug]

Salut,

Après un travail sur l'I.A du Tic Tac Toe, voici les avancées.

La solution théorique passe par le principe de la table de Karnaugh, un tableau à deux dimensions avec des valeurs booléennes.

La mise en pratique afin de contrer le joueur, au lieu de jouer le meilleur coup possible, s'avère difficile.

Trois solveurs sont nécessaires (dans l'ordre).

Le solveur "vérificateur" validation d'une grille (3 pions alignés, joueur ou PC).

Le solveur "marqueur" marquer un point (2 pions PC alignés >> ajouter un pion PC).

Le solveur "contreur" deux pions joueur alignés, contrer avec un pion PC.

La problématique est de vérifier chaque horizontale, chaque verticale, chaque diagonale, une par une.

Voici deux solveurs "contreur-marqueur" pour tests, normalement séparés.
http://files.getwebb.org/download.php?id=cre63aj8

Avec trois solveurs, il semble possible de faire une I.A (potable) Tic Tac Toe avec TGF, en moins de 100 lignes.

Voilà la mise en pratique (3 solveurs, 60 lignes):
http://files.getwebb.org/download.php?id=cre63aj1

Il est possible de rendre l'I.A invincible (Draw ou Win), à mon humble avis >> aucun intérêt.

A+

[Patrice]

Très impressionnant, je suis bluffé. Tu penses qu'il serait possible une partie sur 2 de faire commencer l'IA en premier, je pense que ça doit un peu corser le gameplay sans le rendre injouable.

Bravo

[Capitaine_Caverne]

Merci Kloug super intéressant ça tombe bien je suis sur un jeux de puzzle je fait pouvoir l 'utile avec quelle que petit modif 

[Kloug]

Salut,

Merci pour vos messages.

Désolé, je me la pète en combinant trois solveurs, ce qui n'est évidemment pas le but recherché.

Faire commencer le PC en premier n'est pas très difficile, avec une autre scène, des compteurs globaux...

Nirl fait aussi commencer le joueur en premier, il n'avait qu'un seul niveau de difficulté avec une I.A "meilleur coup possible".
Laisser le PC commencer en premier, contrer le joueur, c'est au minimum un résultat nul, en clair la même chose qu'une I.A "meilleur coup possible".

Le souci, est donc le peu de marge de manœuvre qu'offre le jeu.

Un jeu certes captivant à étudier, certainement pas à jouer, cela m'a permis de comprendre qu'il est plus judicieux de contrer le joueur, plutôt que d'anticiper ses coups, avec une I.A Tic Tac Toe, car cela représente moins de lignes.

Le truc à retenir avec TGF MMF, c'est qu'il est possible, sans être un super codeur, de mettre au point rapidement un petit système afin de vérifier l'état d'une grille ou autre.

A+