Discussion :

[kosted]

Bonjour à tous, je suis entrain de réaliser un jeu de plateau et je fais face à une difficulté que je n'arrive pas à surmonter .

En gros, pour implémenter mon plateau, j'ai un tableau à deux dimensions (voir image) et chaque case contient un nombre de pions (0 à max 32). Lorsqu'on récupère les pions d'une case et qu'on se déplace (suivant le sens contraire des aiguilles d'une montre), on dépose un pion par case suivant : par exemple, si je prends les pions de la 00 (donc 3), je vais déposer un pion en 1-0 (qui devient donc 2), un autre en 1-1 (qui devient donc 1) et ainsi de suite. Le dernier pion que je dépose (donc dans l'exemple précédent en 1-2), si il y a 0 pion en 1-2, alors je ne dépose pas le pion en 1-2 mais en 1-3 et j'incrémente 1-3 (5). Si il y a un pion comme c'est le cas sur le schéma, je dépose en 1-2 (qui devient 2), puis je prends les 2 pions et je continue, je dépose un en 1-3 et le dernier en 1-4 (parce que 1-4 n'est pas vide (sinon j'aurais déposé en 1-6 : je me suis trompé j'ai mis 8 sur le schéma au lieu de 6), et 1-4 devient 5) et je continue.

Ce que je veux faire c'est d'arriver, à avoir un algo qui puisse me permettre d'avoir le dernier pion en 0-5 peu importe le nombre de tour que ça peu prendre. Par exemple je sais que en un coup je peux prendre les pions en 1-7, mettre un en 0-7,un autre en 0-6, et le dernier en 0-5 (et je gagne). Cependant, il peut nécessiter plusieurs déplacement avant d'y arriver et c'est cet algo que je n'arrive pas à faire.

Votre aide me serai d'une grande utilité

[tbc92]

J'ai peut-être raté un truc, mais voici mon approche.
Si j'ai bien compris, on a une situation initiale qu'on subit. (dans l'exemple, tu as 3 pions dans la case (0,0) etc etc)

Si tu choisis de commencer par la case (0,0) par exemple, toute la suite de la partie est déterminée. Et effectivement, la partie peut être très longue.
Et idem, quelle que soit la case départ choisie.

Tu dois donc explorer les 16 scénarios en parallèle.
Pour chacune des 16 cases de départ possibles, quelle est la situation après 1 mouvement, après 2 mouvements, etc etc, jusqu'à ce qu'un des 16 scénarios donne le résultat voulu.

[kosted]

J'ai peut-être raté un truc, mais voici mon approche.
Si j'ai bien compris, on a une situation initiale qu'on subit. (dans l'exemple, tu as 3 pions dans la case (0,0) etc etc)

Si tu choisis de commencer par la case (0,0) par exemple, toute la suite de la partie est déterminée. Et effectivement, la partie peut être très longue.
Et idem, quelle que soit la case départ choisie.

Tu dois donc explorer les 16 scénarios en parallèle.
Pour chacune des 16 cases de départ possibles, quelle est la situation après 1 mouvement, après 2 mouvements, etc etc, jusqu'à ce qu'un des 16 scénarios donne le résultat voulu.

Oui mais le problème qui se pose, est que je ne sais pas comment calculer ces déplacements. En gros, je n'arrive pas à imaginer, un algo qui puisse me permettre de me déplacer en faisant ce que j'ai décrit oralement et que tu as dis.

[picodev]

Bonjour,

Je pars du principe qu'il y a 32 pions sur le plateau.
Dans un premier temps je te propose de numéroter les cases. Par exemple on peut partir sur

Code :

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

1
2
num(line, col) = |col   , if line=0
                 |15-col, if line=1

Cela te donne comme numérotation :

0	1	2	3	4	5	6	7
15	14	13	12	11	10	9	8

Si les déplacements se font dans le sens antihoraire, la case suivante est donnée par next(n)=(n+15) modulo 16 et la précédente parprev(n)=(n+1) modulo 16. Cette représentation et ces formules sont facilement généralisables pour des plateaux de longueur quelconque.

Il te suffit d'avoir peu de primitives pour construire les algos ensuite.

[Flodelarab]

Bonjour

Reprenons le formalisme de Picodev.

La question est de remplir la case numéro 5 avec le dernier pion.

J'aurais tendance à remonter le courant en partant de la solution.
Si on veut le dernier en 5 c'est qu'il y avait 1 dans 6 ou 2 dans 7 ou 3 dans 8.... etc.
Tu peux construire un arbre qui donne toutes les positions gagnantes.
Et tant que les situations gagnantes trouvées ne correspondent pas à ta situation initiale, l'arbre pousse.

L'algo s'arrête quand il a trouvé ou quand le temps imparti est écoulé.

[tbc92]

Bonjour

Reprenons le formalisme de Picodev.

La question est de remplir la case numéro 5 avec le dernier pion.

J'aurais tendance à remonter le courant en partant de la solution.
Si on veut le dernier en 5 c'est qu'il y avait 1 dans 6 ou 2 dans 7 ou 3 dans 8.... etc.
Tu peux construire un arbre qui donne toutes les positions gagnantes.
Et tant que les situations gagnantes trouvées ne correspondent pas à ta situation initiale, l'arbre pousse.

L'algo s'arrête quand il a trouvé ou quand le temps imparti est écoulé.

Ca marche, mais c'est inapplicable.
Si on parcours l'arbre 'dans le sens chronologique de déroulement de la partie', on a 16 arbres à parcourir, et chaque arbre a une seule branche ( c'est essentiel comme information)
Et kosted nous demande de l'aide pour cet exercice que je considère comme très simple.

Si on déroule l'arbre dans l'autre sens, comme tu le proposes, en partant de la situation finale, alors on a un arbre qui est exponentiel, avec tout ce que ça sous-entend en difficulté d'implémentation.