IA et Jeu de batailles navales
Jacques Lethuaut
J'ai commencé à créer un jeu de batailles navales, et je me rends compte que
le mode jouer contre l'ordinateur n'est pas très agréable, lorsque je lui
demande juste de tirer sur une position aléatoire.
Je voudrais donc commencer à y mettre un peu d'IA. (je ne suis pas sûr que
ce soit le bon terme d'ailleurs...)
Je suis complètement novice dans le doamine.
Merci à tous ceux qui voudront bien m'aider.
Luc Hermitte
>
> Je suis complčtement novice dans le doamine.
Peut-etre deux facons de faire :
- min-max avec elagage aplha-beta ; bien qu'au prealable il
vaut mieux etudier le probleme en maintenant un liste de
zones possibles/probables
- En jetant un oeil du cote Reinforcement Learning, si tu
veux que ton jeu apprenne a jouer. Ca donne de bons
resultats avec le backgammon, je ne sais pas du tout si
c'est applicable a la bataille navale. C'est juste une idee
en l'air.
- En le programmant en dur... Quel est l'algorithme qui te
fait jouer ?
Un conseil, tu auras peut-etre plus de reponses sur
news://comp.ai.games
Sinon, un site incontournable est celui de Steve Woodcock
-> http://gameai.com/ai.html
Tiens nous (moi) au courant,
Luc Hermitte
Jacques Lethuaut
> - min-max avec elagage aplha-beta ; bien qu'au prealable il
> vaut mieux etudier le probleme en maintenant un liste de
> zones possibles/probables
> - En jetant un oeil du cote Reinforcement Learning, si tu
> veux que ton jeu apprenne a jouer. Ca donne de bons
> resultats avec le backgammon, je ne sais pas du tout si
> c'est applicable a la bataille navale. C'est juste une idee
> en l'air.
> - En le programmant en dur... Quel est l'algorithme qui te
> fait jouer ?
Merci, je vais déjà comprendre le premier point (min-max avec élagage
alpha-beta) : Voir le rapport avec la grille de la bataille navale, puis le
programmer et vous (te) dire si cela marche. J'avais penser à maintenir une
liste de zones possibles, mais je ne vois pas encore comment faire...
C'est en forgeant qu'on devient forgeron.
Benoit ROUSSEAU
questions-reponses?
Luc Hermitte wrote:
> Jacques Lethuaut wrote:
> >
> > Je suis complčtement novice dans le doamine.
> Peut-etre deux facons de faire :
> - min-max avec elagage aplha-beta ; bien qu'au prealable il
> vaut mieux etudier le probleme en maintenant un liste de
> zones possibles/probables
> - En jetant un oeil du cote Reinforcement Learning, si tu
> veux que ton jeu apprenne a jouer. Ca donne de bons
> resultats avec le backgammon, je ne sais pas du tout si
> c'est applicable a la bataille navale. C'est juste une idee
> en l'air.
> - En le programmant en dur... Quel est l'algorithme qui te
> fait jouer ?
>
> Un conseil, tu auras peut-etre plus de reponses sur
> news://comp.ai.games
> Sinon, un site incontournable est celui de Steve Woodcock
> -> http://gameai.com/ai.html
>
> Tiens nous (moi) au courant,
> Luc Hermitte
--
---------------------------------------------------------------------------
Benoit ROUSSEAU rous...@esstin.u-nancy.fr
L'univers et la connerie humaine sont infinies ?
Pour l'univers je n'en suis pas sur... Albert Einstein
Jacques Lethuaut
> L'algorithme de min-max m'implique-t-il pas un jeu de
> questions-reponses?
Pourrais tu expliquer s'il te plait ?
Fabrice Didierjean
>
> Jacques Lethuaut wrote:
> >
> > Je suis complčtement novice dans le doamine.
> Peut-etre deux facons de faire :
> - min-max avec elagage aplha-beta ; bien qu'au prealable il
> vaut mieux etudier le probleme en maintenant un liste de
> zones possibles/probables
Je ne sais pas si Min/Max est applicable a la bataille naval. En effet,
dans le cas de la bataille naval, la position des bateaux n'est pas
connu, il devient donc impossible de donner une note a une position et
donc impossible de determiner si un coup est meilleur qu'un autre.
> - En jetant un oeil du cote Reinforcement Learning, si tu
> veux que ton jeu apprenne a jouer. Ca donne de bons
> resultats avec le backgammon, je ne sais pas du tout si
> c'est applicable a la bataille navale. C'est juste une idee
> en l'air.
Ca ne doit pas etre applicable, pour la meme raison qu'au dessus.
> - En le programmant en dur... Quel est l'algorithme qui te
> fait jouer ?
A mon avis c'est la seule solution. Le jeu etant reelement trop simple
et vraiement trop hazardeux. On ne peut pas vraiement organiser une
strategie gagnante.
> Un conseil, tu auras peut-etre plus de reponses sur
> news://comp.ai.games
> Sinon, un site incontournable est celui de Steve Woodcock
> -> http://gameai.com/ai.html
>
> Tiens nous (moi) au courant,
> Luc Hermitte
--
DIDIERJEAN Fabrice (ICQ:18683553) tel: 04-92-38-77-48
Didierjea...@sophia.inria.fr Bat: Galois - Bur: G33
http://www.inria.fr/cermics/contraintes/personnel/Fabrice.Didierjean/
Jacques Lethuaut
> > - En le programmant en dur... Quel est l'algorithme qui te
> > fait jouer ?
>
> A mon avis c'est la seule solution. Le jeu etant reelement trop simple
> et vraiement trop hazardeux. On ne peut pas vraiement organiser une
> strategie gagnante.
Cela sous entend il qu'à part un random sur les positions, il n'est pas
possible d'établir une statégie ?
Eric POIRIER
Jacques Lethuaut <jac...@dunet.com> a écrit dans le message :
83nuki$efd$1...@jaydee.iway.fr...
Non, cela signifie que le jeu étant peu tactique (pas d'interactions entre
les joueurs) la seule "intelligence" à mettre dedans est de coder ton
raisonnement quand tu y joues.
Par exemple, étant données les règles de positionnement des navires (pas de
cases contigues, pas de navire en diagonale par exemple) et de la
connaissance des coups joués auparavant : E5 ! - Porte-avion coulé ! ... tu
donnes un ensemble de règles au programme pour qu'il élimine les cases
interdites. Tu peux aussi à un moment donné du jeu éliminer toutes les cases
qui ne permettraient pas de positionner les navires qui restent.
Exemple : il ne reste qu'un cuirassé (4 cases chez moi) et le tableau est le
suivant :
_ 1 2 3 4 5 6 7 8 9 10
A X X_ _ X X X _ _ _
B X _ _ _ X X X X X X
.
.
Les cases A8, A9, et A10 peuvent être "tuées" puisque le cuirassé ne peut
pas y être.
Enfin, c'est comme ça que je jouais à la bataille navale ;-)
Eric
Jacques Lethuaut
de
> cases contigues, pas de navire en diagonale par exemple) et de la
> connaissance des coups joués auparavant : E5 ! - Porte-avion coulé ! ...
tu
> donnes un ensemble de règles au programme pour qu'il élimine les cases
> interdites. Tu peux aussi à un moment donné du jeu éliminer toutes les
cases
> qui ne permettraient pas de positionner les navires qui restent.
>
> Exemple : il ne reste qu'un cuirassé (4 cases chez moi) et le tableau est
le
> suivant :
> _ 1 2 3 4 5 6 7 8 9 10
> A X X_ _ X X X _ _ _
> B X _ _ _ X X X X X X
> .
> .
>
> Les cases A8, A9, et A10 peuvent être "tuées" puisque le cuirassé ne peut
> pas y être.
>
> Enfin, c'est comme ça que je jouais à la bataille navale ;-)
>
Je programme ça et je vous tiens au courant rapidement...
Merci
Arthur Meunier
...
Le mieux est de tirer au hasard puis de balayer des champs en laissant des
cases vides ( pas de bateau de côté 1 :) )
ainsi
x x
x x x
x x
tu vois le principe
une fois que l'odi touche un bateau il regarde ce que peut-être ce bateau
==> probabilité, bateaux deja coulés )e tessaye de determiner ca
direction, puis il le coule.
Le programme risue d'être deboussolé si 2 bateaux se touchent mais ca n'est
pas on plus grand chose à faire.
Mon conseil serait de faire un réseaux neuronal, ca donne de la classe au
produit. Comme rétine tu as l'état du jeu ( les dans l'eau qu'il a mis, ses
touchés, ses coules ), je dirais donc 100 cases * 2 neurones binaires = 200
neurones en entrée puis 4 couches de 200 enfin une couche de sortie de 6
neurones pour le coup a jouer.
Luc Hermitte
>
> L'algorithme de min-max m'implique-t-il pas un jeu de
> questions-reponses?
Nullement.
Le min-max s'applique aux jeux qui se jouent a 2 joueurs.
Le principe tout bete de tout jeu consiste a maximiser ses
gains et a minimiser ceux de l'adversaire. Dans le min-max,
on explore jusqu'a une profondeur donnee tout l'arbre de
recherche ("si je joue ca1 et qu'il joue ca2 et que je joue
ensuite ca3, etc") en prenant certaines precautions : on
choisi a chaque noeud la solution soit qui miminise (min),
soit qui maximise (max) le gain du joueur evalué.
L'elagage alpha-beta consiste a ne pas evaluer les feuilles
d'un noeud que l'on sait non ameliorable.
Je peux eventuellement retrouver un petit programme en C++
de ma composition qui deploie un min-max.
Luc Hermitte
Stéphane Dupille
Luc> Benoit ROUSSEAU wrote:
>> L'algorithme de min-max m'implique-t-il pas un jeu de
>> questions-reponses?
Luc> joueurs.
Plus précisemment, min-max s'applique aux jeux à somme nulle,
et à information complète.
Somme nulle signifie que tout gain pour un joueur est
équivalent à une parte pour l'autre joueur, et vice-versa bien sûr, et
ce, dans les mêmes proportions. Je n'ai cependant pas d'exemple de
jeux à somme non nulle en tête (mais ils existent, Mulder les a
rencontrés :)), si quelqu'un en a, je suis preneur...
Information complète signifie que les deux joueurs possèdent
les mêmes informations. Cela exclue les jeux tels que les jeux de
cartes (où l'on ne connaît que son propre jeu, et pas celui de
l'adversaire), et cela inclue les jeux de « plateau » tels que les
dames, les échecs ou encore le jeu de Go.
Ceci dit, il ne doit pas être très compliqué de sortir une
variante de min-max pour des jeux de plus de deux joueurs : il ne doit
pas être compliqué de faire un min-min-max, pour un jeu d'échecs à
trois joueurs (le jeu reste à somme nulle, non seulement entre les
trois joueurs, mais aussi entre moi et mes deu adversaires ensembles,
et reste à information complète).
Luc> Le principe tout bete de tout jeu consiste a maximiser ses gains
Luc> et a minimiser ceux de l'adversaire. Dans le min-max, on explore
Ce principe ne s'applique qu'aux jeux à somme nulle.
Luc> jusqu'a une profondeur donnee tout l'arbre de recherche ("si je
Luc> joue ca1 et qu'il joue ca2 et que je joue ensuite ca3, etc") en
Luc> prenant certaines precautions : on choisi a chaque noeud la
Luc> solution soit qui miminise (min), soit qui maximise (max) le gain
Luc> du joueur evalué.
Une autre précision (du pinaillage même). L'algorithme de base
de min-max oblige à parcourir tout l'arbre (du début à la fin) de
recherche. En pratique, comme ce n'est pas possible, on rajoute une
heuristique d'évaluation de position, pour s'arrêter au bout d'une
profondeur donnée (la profondeur peut d'ailleurs être obtenue par une
autre heuristique).
Tout la difficulté d'implémentation provient du /choix/ de
cette heuristique, car c'est d'elle que vient la /pertinence/ de
l'ensemble.
Luc> L'elagage alpha-beta consiste a ne pas evaluer les feuilles d'un
Luc> noeud que l'on sait non ameliorable.
Tout à fait. Je dirais même plus, on n'élague pas que des
feuilles, mais des branches entières (là c'est vraiment de la sodomie
de mouche :)) .
--
,_,
(o,o) Beat me, whip me, make me use Windows!
( . )
-"-"--------------------------------------------------------- DUST --