Discussion :

[cLaSic]

Bonjour,

Je voudrai savoir si quelqu'un connais ce jeu que je dois l'implémenter sous prolog dont les règles :
Ça se joue entre deux joueurs, et chacun son tour.
Le jeu et sous forme d'une grille et chaque joueur a le droit de choisir une ligne ou une colonne, et il coche autant de cases qu'il veut (au minimum 1).
Le gagnant c'est celui qui coche la dernière case.

[Trap D]

Non, je ne connais pas mais ça a l'air intéressant. (Ça a un faux air du jeu de Marienbad !).
Tu en es où ?

Tu le fais avec XPCE ?

[cLaSic]

ça sera sur SWI-PROLOG mais j'ai pas encore commencer ...
Avez vous une idée de ce que je dois faire .. ? stratégie gagnante ...

[Trap D]

Il y a des histoires de reste modulo 2 égal à 1 pour gagner si je me souviens bien. Le problème se complique puisque c'est sur ligne et colonne car pour Marienbad c'est uniquement des lignes.

[cLaSic]

Il y a des histoires de reste modulo 2 égal à 1 pour gagner si je me souviens bien. Le problème se complique puisque c'est sur ligne et colonne car pour Marienbad c'est uniquement des lignes.

Est ce que tu peux me donner plus d'informations sur l'histoire de reste modulo 2 égal à 1 ...

[Trap D]

Je parlais du jeu des allumettes, mais je pense que ça doit être pareil pour ton jeu. Tu ferais bien de poser ta question sur le forum algo, là tu trouveras de vrais spécialistes pour t'aider. Tu reviendras sur le forum pour la translation de l'algo en Prolog.
Tape "Jeu de Nim" sur Google.

[timtim2007]

Bonjour,

Je voudrai savoir si quelqu'un connais ce jeu que je dois l'implémenter sous prolog dont les règles :
Ça se joue entre deux joueurs, et chacun son tour.
Le jeu et sous forme d'une grille et chaque joueur a le droit de choisir une ligne ou une colonne, et il coche autant de cases qu'il veut (au minimum 1).
Le gagnant c'est celui qui coche la dernière case.

Et pour résoudre ce problème.Est ce que la meilleur solution c'est de generer pour chaque état du jeux tous les états possibles et ainsi de suite, ou ya un autre moyen plus facile ?

[Trap D]

Même réponse que pour le précédent P.O., il y a peut-être des possibilités trouver des stratégies gagnantes en utilisant les écritures binaires des nombres de cases non cochées dans les lignes (ou colonnes). A étudier, c'est votre problème, ici on ne parle que de Prolog.

[timtim2007]

J'ai écrit un prédicat qui renvoi tous les coups possibles à partir d'un état de la grille ... coupsPossibles(Grille,Coups)

Je ne sais pas comment faire maintenant pour représenter tous ça dans un arbre afin d'appliquer l'algorithme MinMax par exemple ...
http://www.grappa.univ-lille3.fr/~to...le/minmax1.png

[elissa]

salut,
moi aussi j'ai le meme projet que le tien et j'arrive pas à trouver une méthode rapise pour trouver les stratégies gagnates san avoir recours aux algo min max et alpha beta.

sur une grille de 5*5 on trouve 285 facons de jouer avec minmax donc c'est un peu compliqué.

je pense qu'il y'a une autre méthode mais j'arrive pas à la trouver.

on reste en contact si tu trouve ou je trouve quelques choses.

bye,

[pcaboche]

sur une grille de 5*5 on trouve 285 facons de jouer avec minmax donc c'est un peu compliqué.

je pense qu'il y'a une autre méthode mais j'arrive pas à la trouver.

Oui, il y a moyen de réduire le nombre de possibilités à explorer (c'est beaucoup trop long de les explorer toutes). Voici un exemple:

Dans votre jeu, à chaque tour on remplit autant de cases que l'on veut sur une même ligne ou une même colonne. On ne sait pas ce que va jouer l'adversaire hormis le fait qu'il peut, au maximum, remplir une ligne ou une colonne entière (à condition que la ligne/colonne ne sont pas déjà remplie).

Dans un premier temps, considérons que le seul coup autorisé (pour nous comme pour l'adversaire) soit de remplir une ligne entirèrement. Comptons le nombre de lignes non complètement remplies. Si ce nombre est impair, on gagne (puisqu'on commence à jouer, lorsqu'il ne restera qu'une seule ligne ce sera à nous de jouer et donc on gagne). Si ce nombre est pair, on perd.

Par la suite on appelera cette propriété la "parité" (de ligne ou de colonne), qui désigne le fait que le nombre de lignes (respectivement, de colonnes) non complètement remplies soit pair ou impair.

Imaginons maintenant que l'on s'autorise à ne laisser qu'une seule case vide sur une ligne. En procédant ainsi, on ne modifie pas la parité. Par contre, si par la suite l'adversaire décide de remplir la case restante, la parité sera modifiée. De cette façon, on incite l'adversaire à modifier la parité à notre avantage.

Laisser plus d'une case vide sur une ligne n'a que très peu d'intérêt: on laisserait alors à l'adversaire la possibilité de modifier la parité à son avantage.

On s'autorise donc 2 types de coups:

• soit remplir complètement une ligne/une colonne (l'adversaire ne peut plus jouer cette ligne/colonne)
• soit ne laisser qu'une seule case sur une ligne/colonne (l'adversaire n'a plus que la possibilité de remplir complètement la ligne/colonne)

De cette façon, on réduit considérablement le nombre de possibilités en éliminant de nombreux coups qui n'apportent pratiquement rien d'un point de vue stratégique (afin de n'explorer que les solutions potentiellement intéressantes).

Le plus dur reste de définir une stratégie en fonction des parités ligne/colonne, des lignes/colonnes ne contenant qu'une case libre, etc.

[bbbenja]

J'ai le même projet que vous et je me suis servi de ces réponses pour créer l'algo minimax or celui ci ne marche que pour une grille 3x3. Dès qu'on dépasse, j'obtient un "Out of global stack". Y'a t'il une solution pour réduire le nombre de noeud de l'arbre?

Merci de votre aide..

[clinic]

le jeu de nim est un problème np-complet ... c'est gourmand peu importe l'implementation ...

j'ai eu à proposer une ia pour ce jeu en projet d'étude, mais je l'avais fait en cpp.
J'utilise une modelisation par graphe, avec un graphe des coup possible, l'objectif pour l'ia etant de rester dans le noyau du graphe ( imbattable sauf si le joueur connait lui aussi le noyau )

mais j'avais aussi une complexité trop importante pour les grilles 5*5 ... heureusement je faisait un unique calcul du graphe et de son noyau que je sauvegardais en binaire dans un fichier. ( 5 heure de calcul sur un core 2 duo en code multithreadé ... )

Je serai bien curieux de voir ce qu'on peut faire en prolog pour ce probleme du jeu de nim :-)

[info_0]

Bonsoir !
Je dois résoudre le problème du minmax, cela fait plusieurs jour que je suis dessus, mais je n'avance pas, donc si quelqu'un voulait y jeté un coup d'oeil, je serais reconnaissante.
J'ai essayé de coder une fonction qui va renvoyer le min des listes les plus profondes et reconstruire la liste pour la renvoyer.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
minsouliste([L|R],P):-is_list(L),!,minsouliste(L,P1),minsouliste(R,P2),conc([P1],[P2],P).
minsouliste(L,P):-minimum([L,P1),conc([P1],[],P).
minsouliste([X],[X]).
minsouliste([],[]):-!.
 
minsouliste([[[2,3,5],[3,0,2]],[2,3,9]],R).
R->[[2,0],2]

mais mon code renvoie un false !!!
Bonne soirée !

[Trap D]

Bonjour
Tu n'étais pas loin de la solution, mais il faut deux prédicats, un pour traiter les listes dont les éléments sont des listes et l'autre, une liste plate.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
% lorsque la liste est vide le résultat l'est aussi !
minsousliste([], []).
 
% Il faut tester le premier élément
% Si c'est une liste, tous les autres élélments 
% sont aussi des listes
% on appelle donc minsousliste sur chacun des éléments
% et on concatène les résultats
minsousliste([H|T], [MH | MT]) :-
	is_list(H), !,
	minsousliste(H, MH),
	minsousliste(T, MT).
 
% ici on est certain que H n'est pas une liste
% on recherche le minimum d'une liste
minsousliste([H | T], M) :-
	% T reste de la liste à étudier
	% H le premier élément donc le plus petit au départ
	% M résultat final
	minimum(T, H, M).
 
% lorsque la liste est vide, on unifie le résultat
% final, M, avec le plus petit en cours
minimum([], M, M).
 
% Si H est plus grand, on continue en gardant le plus petit M
minimum([H | T1], M, MF) :-
	H >= M, !,
	minimum(T1, M, MF).
 
% Sinon, on continue en gardant H.
minimum([H | T1], _M, MF) :-
	minimum(T1, H, MF).

[info_0]

merci bcp!!!

[info_0]

En fait, il y a encore un petit souci, dans ce cas par exemple:

minsousliste([[1,[2,5]]],R).
ERROR: '.'/2: Type error: `[]' expected, found `[5]' ("x" must hold one character)
Exception: (9) mini([[2, 5]], 1, _G444) ?

ce qui doit renvoyer normalement:
[[1,2]]

donc j'ai essayé des trucs mais ça renvoie à chaque des erreurs
donc s'il vous plait si vous jetiez un cout d'oeil ceci sera sympa.
bonne soirrée.

[Trap D]

Eh oui, cette liste "[[1,[2,5]]]" n'a pas le même format que la liste précédente "[[[2,3,5],[3,0,2]],[2,3,9]]" où tous les éléments d'une liste étaient de même type, donc mon code ne peut pas fonctionner avec "[[1,[2,5]]]".

% Il faut tester le premier élément
% Si c'est une liste, tous les autres éléments
% sont aussi des listes

Je vais regarder, mais si tu trouves entre temps, n'hésite pas à poster.

[Trap D]

Bon, finalement, j'ai eu le temps de le faire, mais pas de le commenter

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
minsouliste([], []).
 
minsouliste([H|T], [MH | MT]) :-
	is_list(H), !,
	minsouliste(H, MH),
	minsouliste(T, MT).
 
minsouliste([H|T], MH) :-
	minsouliste1(T, H, MH).
 
 
minsouliste1([H | T], MHC, [MH2 | [MH1]]) :-
	is_list(H), !,
	minsouliste(H, MH1),
	minsouliste1(T, MHC, MH2).
 
minsouliste1([H | T], MHC, MH) :-
	H < MHC, !,
	minsouliste1(T, H, MH).
 
minsouliste1([_H | T], MHC, MH) :-
	minsouliste1(T, MHC, MH).
 
minsouliste1([], MH, MH).

Normalement ça devrait couvrir tous les cas, mais tout n'est pas testé

[info_0]

Bonsoir,
j'ai un peu modifié le code pour qu'il ne me fasse plus quelques erreurs, mais il me reste un tel que :
4 ?- minsouliste([2, [0, 1], [8, 2], 4], R).
R = [2, 0, 2|4].

alors que ça doit renvoyer R = [2, 0, 2,4]., je n'ai pas réussis à la corrigée.
Voilà le code avec les modifs :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
conc([], L, L).
conc([X | L], M, [X | N]) :- conc(L, M, N).
minsouliste([], []).
minsouliste([H|T], [MH | MT]) :-is_list(H), !,minsouliste(H, MH),minsouliste(T, MT).
minsouliste([H|T], MH) :-minsouliste1(T, H, MH).
 
minsouliste1([H | T], MHC, R1) :-is_list(H), !,minsouliste(H, MH1),conc([MHC],[MH1],R),minsouliste(T, MH2),conc(R,MH2,R1).
minsouliste1([H | T], MHC, MH) :-H < MHC, !,minsouliste1(T, H, MH).
minsouliste1([_H | T], MHC, MH) :-minsouliste1(T, MHC, MH).
minsouliste1([], MH, MH).

Si vous pouvez encore m'aider svp, ça serait génial.
Bonne soirée