bataille navale jeu contre l'ordinateur

buchepot · Le 15/11/2007, à 13:13

Bonjour

J'ai un projet à faire en programmation. Il s'agit de réaliser un jeu de bataille navale en c ou l'on peut jouer contre l'ordinateur.
Cependant j'aimerai savoir s'il y a une mathode pour minimiser le nombre de coup à tirer pour toucher les bateaux. En effet si on minimise le nombre de coup, on devrait maximiser la chance de toucher un bateau. Bien sur on peut toujours appliquer la méthode des diagonales, mais lors d'un jeu déjà avancé, le résultat n'est pas toujours optimal.
Si vous aviez des suggestion elles sont les bien venues.

Merci d'avance

LittleWhite · Le 15/11/2007, à 13:56

Pour la bataille navale je pense qu'on peut faire :

Une recherche aléatoire ( des coups tirés aléatoirement c'est ce que je fait )
Après si un bateau est trouvé on tire sur les cases adjacente
Si une case adjacente est touché on tire dans les cases qui sont adjacente et qui suive la ligne
Une fois qu'on a trouvé des cases vides dans la ligne on recommence a tiré aléatoirement

Ce n'est qu'une suggestion mais ça peut fonctionner

buchepot · Le 15/11/2007, à 14:12

Merci, mais pour réalisé un niveau de jeu difficile au niveau de l'ordinateur, certe il faudra des tirs aléatoires mais (et principalement en fin de jeu) que ces tirs ne soient pas tiré n'importe oà¹.

Je m'explique, il faudrait prévoir (en fonction de la grille de jeu et des bateaux restants) les différents coups à tiré. Le nombre de coup à tiré devra bien sur être le minimum pour pouvoir toucher le plus rapidement un bateau.

LittleWhite · Le 15/11/2007, à 15:14

J'ai une solution mais j'ai envie de me cacher quand j'y pense
Quand tu arrive dans les derniers tu peut faire en sorte que l'ordinateur regarde directement dans la grille des bateau du joueur.
Mais c'est pas vraiment cool comme code
Au sinon je ne voit pas trop comment faire ou il se peut que j'ai mal saisie la question

P.S. au fait il ne faut que l'ordinateur tire deux fois sur la même case. mais ça je pense que c'est logique et que je n'avais pas besoin de le précisé

Martopioche · Le 15/11/2007, à 21:06

Bonjour

J'ai pas vraiment envie de me cramer les neurones après les bouchons mais voila des pistes :

Une fois le jeu avancé, il va falloir optimiser les tirs en fonction des positions possibles. Les bateaux ne peuvent être en diagonale et ne peuvent être côte à côte. Leur nombre en fonction de leur longueur est défini. Donc il faut que tu détermine les longueur existantes, que tu les range par ordre de taille et que tu "tire" de tel manière que tu puisse toucher le plus grand. A chaque fois, quand tu le fini puis l'élimine de la liste.

En claire, l'idée est de faire un tri par longeur puis de faire disparaitre les listes les plus longues, et réorganiser le tout.

LittleWhite · Le 15/11/2007, à 21:49

Jouer et plus facile de faire jouer

Pour reprendre l'idée de Martopioche
On n'a pas besoin de tirer toute les case mais une case sur deux ( car la longueur n'est pas inférieur à 2 )

Je trouve ton idée très bonne Martopioche

Martopioche · Le 16/11/2007, à 00:23

Oui, c'est bien ce que je veux dire, mais j'utiliserai la stratégie suivante :
Au tour t
le navire (de position inconnue) de l'adversaire le plus grand a la taille tMax, le plus petit tMin.
Tu fait la liste des blocs de cases non tirées alignées, rangées par taille de la plus grande à la plus petite.
Tu prend la (ou aléatoirement si il y en a plusieurs, une des) plus grande, de taille T. Tu tire sur une case de position p tel que
p < T (évidemment)
p < tMax, idéalement p = tMax - 1 pour rechercher le plus grand bateau MAIS également p > tMin - 1

De manière générale, tu néglige tout alignement de tMin - 1 cases et tu évite de générer de tels alignements (sauf si 2*tMin >= T >= tMin évidemment) pour minimiser le nombre de tirs.

Voila l'idée générale.

A toi de combiner cette recherche avec l'utilisation des croisements (2 alignements perpendiculaires )

Vive l'algo

doc212 · Le 16/11/2007, à 06:16

moi j'ai une idée mais disons qu'elle demande énormément de calcul de la part de l'ordinateur ... dépendant de la taille de la grille et du nombre de bateaux et de leurs tailles, ça peut prendre bcp de temps pour calculer un coup ...

Tu commences par définir une matrice de même dimensions que la grille. L'idée c'est d'énumérer tous les arrangements possibles des n bateaux adverses dans la grille. Pour chaque arrangement possible, tu balaye chaque case de la grille et si cette case est occupée, tu incrémente de 1 l'élément correspondant de la matrice.

Après avoir fait tous les arrangements possibles (de n bateaux sur la grille) tu tire là oà¹ la matrice a sa valeur maximale. C'est la case oà¹ la probabilité de toucher un bateau est maximale, puisque sur tous les arrangements possibles, c'est la case qui a été le plus de fois occupée.

Ce qui est un peu fastidieux c'est donc d'énumérer tous les arrangements possibles. Cela peut se faire de façon très systématique.

la position de chaque bateau peut être déterminée de manière unique grà¢ce à 3 paramètres: les coordonnées de sa "tête" et son orientation qui ne peut prendre que deux valeurs possibles : verticale (sous sa tête disons) ou horizontale (à droite de sa tête disons).

Tu place ton premier bateau verticalement en (1,1) (ligne, colonne) , puis ton 2ème bateau en (1,2)verticalement, puis ton 3ème bateau en (1,3) verticalement etc... jusqu'au bateau n placé en (1,n)verticalement. On obtient un premier arrangement et on met à jour la matrice.

2ème arrangement, on laisse inchangé les n-1 premiers bateaux et on déplace le dernier bateau disons en (1,n) horizontalement maintenant.

3ème arrangement, on laisse les n-1 premiers bateau et on place le dernier en (1,n+1) verticalement
4ème arrangement, on déplace juste le dernier bateau en (1,n+1)horizontalement

etc... en ne gardant bien sur que les positions possibles pour ce dernier bateau. Une fois qu'on a essayé toutes les positions possibles pour le dernier bateau, on déplace l'avant dernier bateau d'une position et on rebalaye toutes les positions possibles avec le dernier bateau ... etc etc ...

en pseudo code ça donnerait

pour toutes les positions possibles du bateau 1
pour toutes les positions possibles du bateau 2
pour toutes les position possibles du bateau trois
....
pour toutes les positions possibles du bateau n
Mettre à jour la matrice

les "pour toutes les positions possibles" étant imbriquées comme des for....

Evidemment dans l'affirmation "pour toutes les positions possibles" se cachent toutes les contraintes à savoir, pas se placer en diagonale, pas dépasser de la grille, pas de placer sur un autre bateau (et pas se mettre à cà´té d'un autre bateau mais ça j'suis pas sur que c pas permis).

C'est très barbare comme méthode mais ça te trouvera exactement la case qui a la plus grande probabilité d'être occupée.

Evidemment quand tu a déjà de l'information, à savoir tu sais qu'une certaine case est occupée, tu peux écarter tous les arrangements oà¹ cette case est inoccupée...

Mais le nombre d'arrangements reste très élevé (de l'ordre du nombre de cases exposant 2 fois le nombre de bateau, je dirais)

Enfin voilà ...

best_friend_fr · Le 16/11/2007, à 06:58

Salut,

Je pense que doc212 a une bonne idee, mais je ne sauis pas sur que tirer dans la case qui a le plus de chance d'etre occupee est optimal.

Tirer dans une chance qui a moins de chance mais qui fais "decroitre plus les probabilite voisines" peut etre mieux, non?

best_friend_fr · Le 16/11/2007, à 07:05

Maintenant, si tu veux ma strategie (certainement non optimale) de la bataille navale, c'est :
Si il reste a l'adversaire des bateaux dont la taille est comprise entre m(le plus petit) et M (le plus grand), alors, on determine M/m, et on tire tous les km
De cette facon, tu minimise a peu pres les tirs necessaires pour trouver le plus grand, mais tu ne casse pas tes alignements pour trouver le plus petit...

buchepot · Le 16/11/2007, à 07:49

Je voulais tout d'abord remercier tous ceux qui m'ont déjà répondu.

Martopioche à dit
A toi de combiner cette recherche avec l'utilisation des croisements (2 alignements perpendiculaires )

C'est justement le problème que je me pose (en effet ce n'est pas évident car ça ne dépend pas que des lignes de croisement, mais aussi de l'environnement, une mème ligne peut avoir plusieur croisement.)

Pour répondre à doc212, je n'avais pas du tout vu le problème comme ça. Mais je vais suremment essayé car quoi que couteux en calcul il me parait simple en réalisation.

Pour répondre à best_friend_fr, cette solution quoi qu valide n'est pas optimal. Cependant elle minimise déjà beaucoup les coups.

Si vous avez d'autres suggestions elles sont les bien venus (je compte faire plusieur niveau de jeu).

best_friend_fr · Le 16/11/2007, à 07:52

Un conseil, quand tu auras developpe ta solution mega geniale optimale et tout, fais la jouer contre une solution aleatoire:D

Tu peux avoir des surprises ;D

jdefaver · Le 16/11/2007, à 08:50

Il me semble qu'avec un algorithme subtil comme celui de martopioche, il y a moyen facilement pour le joueur de trouver une parade infaillible, c'est à dire une configuration qui met les bateaux sur des cases de plus faibles probabilités (genre les sous-marins dans les coins). Il faut donc sans doute ajouter une part d'aléatoire pour déjouer ce piège.

Ca me rappelle le reversi de kde qui jouait toujours de la meme facon (intelligente) mais que je battais systématiquement parce qu'il y avait une configuration qui mettait son algorithme a la masse.

doc212 · Le 16/11/2007, à 08:56

best_friend_fr a écrit :

Salut,
... mais je ne sauis pas sur que tirer dans la case qui a le plus de chance d'etre occupee est optimal.
Tirer dans une chance qui a moins de chance mais qui fais "decroitre plus les probabilite voisines" peut etre mieux, non?

Effectivement c'est vrai que ce n'est sûrement pas la meilleure stratégie à adopter.

Je viens de penser à un truc.

Pour une situation donnée du jeu (çà d avoir la connaissance de l'absence ou la présence de bateau dans certaines cases), on peut calculer par la méthode précédente la distribution de probabilité sur la grille de toucher un bateau.

A cette distribution, on pourrait associer un "score" qui quantifierait la "qualité" de la situation, à savoir par exemple, le nombre de case oà¹ la probabilité de toucher est faible (disons < 20%) + le nombre de cases oà¹ cette probabilité est forte (disons supérieure à 80%).

Au plus ce score est haut, meilleure serait la situation.

Le coup à jouer serait celui mènant à la situation de meilleure qualité. En gros, on balaye toutes les cases jouables et on calcule pour chaque case le score de la situation dans laquelle on arriverait si on jouait cette case.

Exemple: une case a une probabilité p de toucher et q de manquer (avec p+q=1 donc). En supposant qu'elle touche, on obtiendrait une situation dont le score vaudrait S1 et en supposant qu'elle manque, on aurait une situation de score S0. Alors en moyenne, en jouant cette case, on aboutirait à une situation dont le score serait p*S1 + q*S0 (moyenne pondérée des deux scores possibles).

Cette stratégie demande encore plus de calcul bien entendu vu qu'il faut évaluer la probabilité de chaque case une première fois çà d calculer la distribution de probabilité de toucher. Ensuite pour chaque case possible, il faut réévaluer cette distribution dans les deux cas de figures touché ou raté. Une fois que c'est fait, on peut choisir la case à jouer.

Si il y a N cases d'état inconnus, il faudra calculer 2*N+1 fois la distribution.

Bon maintenant, au tour suivant, on pourrait au lieu de recalculer la distribution se contenter de la récupérer vu qu'on l'a déjà calculée normalement. Mais là , ça suppose qu'on l'ait stockée après l'avoir calculée et surtout qu'on l'ait stockée pour les 2*N possibilités, puisqu'à priori, on ne sait pas encore laquelle on va choisir. Il faut donc une espace mémoire de 2*N*N entiers pour pouvoir faire l'économie de calculer une fois la distribution à chaque coup... j'sais pas si ça vaut le coup.

Pour que cette méthode soit applicable, il faut juste voir combien de temps met l'ordi pour calculer tout ça ... C'est son gros avantage à l'ordinateur: pouvoir faire pleins de calculs super rapidement ... il faut savoir l'exploiter.

Sinon un dernière remarque ... cette stratégie est bonne pour "l'exploration" ... c'est à dire, augmenter le nombre de cases à haute probabilité et réduire le nombre de cases improbables... mais à un moment, faut essayer de les toucher les bateaux et pour ça, il faut choisir les cases les plus probables ...

Donc il faut un compromis entre l'exploration et l'exploitation. Etablir une politique de choix entre la case qui mènera vers la situation au plus haut score et la case qui a le plus de chance de toucher. Typiquement, il faudrait beaucoup explorer "au début" et exploiter plutot "vers la fin".

Voilà j'me suis un peu emballé désolé :-)

Martopioche · Le 16/11/2007, à 09:05

doc212 a écrit :

moi j'ai une idée mais disons qu'elle demande énormément de calcul de la part de l'ordinateur ... dépendant de la taille de la grille et du nombre de bateaux et de leurs tailles, ça peut prendre bcp de temps pour calculer un coup ...

Dans tous les cas, c'est vrai au début. Pourtant, les jeux d'échecs font ça. Et c'est pour ça que c'est quasiment impossible de les battre sur une fin de partie car ils ont déjà toutes les combinatoires possibles et adaptent en fonction de ce que tu a pioché.

Du coup, pour les jeux d'échec, la stratégie est d'effectuer ces calculs qu'à partir d'un certain avancement de la partie. Le début se fait en piochant une séquence d'ouverture parmi celles qui ont fait leur preuve.

Ma proposition se place dans un contexte similaire : début de partie assez aléatoire (avec un peu d'optimisation pour éviter les coups inutiles) puis estimation plus sioux. Je pense que c'est la meilleur approche pour éviter que ce soit lourd au début mais efficace quand même.

Dans tous les cas, les méthodes reposent sur une approche différentes rapidement contrables quand on a compris le truc. Les méthodes basées sur les probabilités (tir sur la plus probable) sont tout de suite contrable par un placement le plus improbable. Pour cela, je préfère une approche comme celle que j'ai proposé (certainement pas optimale, zavez vu l'heure de la rédaction ) basée sur une rapidité de quadrillage de la zone de tir.

Après, si tu gère un historique des parties contre les joueurs, un petit coup d'apprentissage à coup de réseaux neuronaux pour déterminer comment joue un joueur particulier

doc212 · Le 16/11/2007, à 09:49

avec un peu de Q-learning et le tour est joué

Le truc de maximiser le score de la situation, ça a rapport avec les algorithmes max min si tu veux faire un peu de recherche sur le sujet.

Le principe c'est de construire un arbre des coups possibles, partir du bas de l'arbre, de la situation ou tu maximises ton profit et minimise celui de ton adversaire et tu remontes l'arbre (en supposant que l'autre fait de même).

Bon, ici comme les coups qu'un joueur joue n'influence pas le jeu de l'autre, ça n'a plus vraiment de sens et en plus il y a un coté probabiliste qui fourre son nez dans tout ça mais le truc d'associer un score à la situation c'est pas trop trop mal j'pense ...

Et ouais, ça pourrait être pas mal trippant de faire un réseaux de neurones là dedans

j'vais y penser tiens ... :-)

best_friend_fr · Le 16/11/2007, à 20:15

Salut,

Si je ne me trompe pas, les algorithmes max min sont pour les jeux a connaissance parfaite...

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 15/11/2007, à 13:13

bataille navale jeu contre l'ordinateur

#2 Le 15/11/2007, à 13:56

Re : bataille navale jeu contre l'ordinateur

#3 Le 15/11/2007, à 14:12

Re : bataille navale jeu contre l'ordinateur

#4 Le 15/11/2007, à 15:14

Re : bataille navale jeu contre l'ordinateur

#5 Le 15/11/2007, à 21:06

Re : bataille navale jeu contre l'ordinateur

#6 Le 15/11/2007, à 21:49

Re : bataille navale jeu contre l'ordinateur

#7 Le 16/11/2007, à 00:23

Re : bataille navale jeu contre l'ordinateur

#8 Le 16/11/2007, à 06:16

Re : bataille navale jeu contre l'ordinateur

#9 Le 16/11/2007, à 06:58

Re : bataille navale jeu contre l'ordinateur

#10 Le 16/11/2007, à 07:05

Re : bataille navale jeu contre l'ordinateur

#11 Le 16/11/2007, à 07:49

Re : bataille navale jeu contre l'ordinateur

#12 Le 16/11/2007, à 07:52

Re : bataille navale jeu contre l'ordinateur

#13 Le 16/11/2007, à 08:50

Re : bataille navale jeu contre l'ordinateur

#14 Le 16/11/2007, à 08:56

Re : bataille navale jeu contre l'ordinateur

#15 Le 16/11/2007, à 09:05

Re : bataille navale jeu contre l'ordinateur

#16 Le 16/11/2007, à 09:49

Re : bataille navale jeu contre l'ordinateur

#17 Le 16/11/2007, à 20:15

Re : bataille navale jeu contre l'ordinateur

Pied de page des forums