Algorithme Button up !

Modérateur: diplojak

Algorithme Button up !

Message par muzbang » 03 Nov 2019 9:42

Bonjour à tous.

En parcourant un peu le forum a mes heures perdues, je suis tombé sur qq post relatifs à button up, notamment à propos de l'utilisation d'une IA.

cf. dans ce sujethttp://boiteajeux.net/forum/viewtopic.php?f=65&t=17487


diplojak a écrit :
Zed a écrit :Bon, bein, en fait, j’ai écrit un programme qui trouve le meilleur coup à ce jeu étant donné une position initiale (ce n’est pas très dur, l’espace des états est très petit étant donné une position initiale (3^9 en grossière surestimation)). Donc voila, un classement Elo sur ce jeu devient aussi intéressant qu’un classement Elo sur Tic-tac-toe ou sur un jeu de nim.

Bref, un jour des tricheurs pourraient débarquer et pourrir un peu le jeu pour avoir le « meilleur classement en trichant ».

En retirant le classement sur Button Up, tricher perdrait de son intérêt pour ces gens, et éviter de pourrir les parties des gens qui tomberaient dessus.

De mon côté, j’ai décidé d’arrêter d’y jouer, du moins tant que le classement Elo y sera en place.

c'est juste plus facile sur Button Up, mais c'est possible sur à peu près tous les jeux abstraits à 2 de baj. et ça existe déjà, bien que vous ayez tous accepté les CGU qui l'interdisent ;)
les gens qui créent ce genre de programmes sont en général motivés par la programmation elle-même, pas par la victoire ou les points elo, qui leur sert à évaluer la force de leur programme mais qui n'est pas une fin en soi. et ça m'étonnerait que ceux-là perdent leur temps avec Button Up, vu que c'est la première chose qu'on se dit en lisant les règles: rien de plus simple de coder une IA imbattable.

s'il y avait quelque chose à gagner, tout ça serait problématique. ce n'est pas le cas. si quelqu'un est prêt à tricher pour du Elo, grand bien lui fasse!



Pour être tout à fait franc, j'ai développé la dite "application" qui calcule tous les coup du départ.
Comme le dit très justement diplojack, c'est avant tout un défi de programmation et un test du pgm qui m'ont motivés.

Mais je me rend compte au travers des divers messages que cela pourrait être mal pris par certains joueurs.

Donc si j'ai pu blesser des gens je m'en excuse (je n'ai pas fait tant de partie que cela), et si c'est problématique pour les concours (je pense à l'abp tour auquel je participe) je ne vois aucun souci à être exclu.
Je voyais le concours surtout comme la phase de test ultime, et finalement je n'ai testé mon pgm dans sa version 2.0 que sur 15-20 parties je pense.

Enfin, si besoin je veux bien préciser dans le titre de la partie "je suis une IA" ou qq chose du style dans les parties que je joue (donc que je crée).
Si certains ont aussi fait un pgm, ou veulent se mesurer à la "machine", n'hésitez pas à m'inviter.

AU passage, certains ont réussi à rivaliser (RECIF 15-13). Donc malgré le pgm il y a bien des positions impossibles à gagner (sous réserve que les choix en face soient bons), et aussi quel l'erreur reste humaine (inverser rouge / noir, se tromper de pile, ou encore se rendre compte que le pgm ne fait pas exactement ce qu'il faut à cause d'un mauvais copier coller dans un bout de pgm)

Enfin si j'ai enfreint la charte (dont j'ai du uniquement lire le passage "j'approuve" :boulet: ) je m'en excuse... j'espère éviter d'être banni pour cela... je commence à bien apprécier d'être premium :geek: (surtout qu'il permet de toujours jouer les "noirs" :bieremetal: à button-up)


Sinon, pour discuter sur qq points du jeu et de la prog, car au fond c'est le plus intéressant (pour le féru de combinatoire / programmation que je suis - mais je ne déteste pas pour autant la discussion philosophique qu'il peut y avoir en parallèle) :

--il n'y a que 1680 positions uniques au départ, si on considère toutes les combinaisons possibles de 3 Rouge 3 Noir et 3 Blanc.
Le 3 puissance 9 que j'ai lu ici et là ne contraint pas le nb de R/B/N.
La contrainte 3/3/3 diminue grandement le nombre de combinaisons.

--si on y intègre les permutations, alors cela ne fait que 186 possibilités de position de départ. Donc en soi... avec un peu de patience, elles peuvent se décomposer "à la main"
Par ex la position R-R-R-B-B-B-N-N-N est identique à R-R-B-B-B-N-N-N-R
NB : R=Rouge, N=Noir, B=Blanc, et le - est un séparateur de pile (c'est un détail ici, mais important dans la prog), enfin je ne m'attarde pas sur les notations qui sont compréhensibles je pense, je pourrais y revenir s'il y a des questions plus techniques :mrgreen:

--ce faible nombre est ce qui permet d'avoir un "calculateur" qui créé tous les arbres possibles dans un temps raisonnable (1 min environ sur mon pc pour une position de départ, mais probablement pas optimisé, désolé pour les puriste, j'ai fait ça avec VBA d'excel :porc: )

Voilà donc ce que j'ai fait... un programme qui décompose l'arbre de toutes les possibilités à partir d'une position donnée (départ ou en cours de jeu).

En partant d'une position de départ, cela peut aller jusqu'à un peu plus de 2000 branches (dont certaines sous-branches sont parfois parfaitement identiques)

Ensuite, pour faire un choix en fonction d'une position donnée, je suis parti d'un principe simple de la théorie des jeux, qui est de se dire, si je rend une position X à mon adversaire, il me rendra forcément la pire position.

EN partant des "bouts" de branche (on pourrait appeler cela les "feuilles" :mrgreen: ), c'est à dire de la position avec une seule pile (celle qui permet le calcul des points), on peut remonter en arrière et déterminer si une position fait gagner l'un ou l'autre, et en appliquant la théorie de "mon adversaire me rendra la pire position" aux nœuds sur lesquels il a un choix (donc pas sur les miens, ça peut être un détail, mais ça m'a fait m'arracher qq cheveux pour la prog), on peut remonter jusqu'à la position de départ, et faire le "meilleur" choix selon le stade de la partie :
--décider qui joue premier
--décider quelle position donner à l'adversaire.

Sur mes parties test, il faut noter que parfois (sous l'hypothèse que les 2 joueurs utilisent le même pgm), le sort est joué d'avance. Et finalement le choix qui se fait est celui du "moins pire", c'est à dire ce qui donnera le moins de points à l'adversaire.
Finalement ce choix est exactement le même quand tout n'est pas joué, puisque le calcul est basé sur "mon adversaire me rendra la pire position", donc parmi les positions que je peux lui rendre, je choisi de rendre la position qui lui fait faire le moins bon résultat.

NB : sur ce choix, je reste totalement maître du pgm car je pourrais aussi choisir la position qui potentiellement me donnera le plus de points (le souci étant alors que cela laisse généralement plus de possibilités à l'adversaire - et comme je suis parti du principe qu'il me rendrait la pire position, cette stratégie n'est pas bonne)

Voilà en bref ce que fait mon pgm, il calcule les possibilités, et avec un affichage "rouge / noir" (basé sur un point de stratégie du "pire pile que mon adversaire rendra") sur chaque nœud je vois à qui la position est favorable. Et donc in fine je choisi quelle pile je bouge.

Je dis "bref" mais la première étape avant tout ce dénombrement, ça a été de programmer le jeu en lui même, c'est à dire bouger une pile avec un blanc, transformer les piles, tout en respectant les contraintes notamment pour les déplacements des grosses piles en fin de jeu avec la contrainte de poser un bloc, paramétrer le fait qu'on peu rejouer si le dernier pion est d'une couleur identique à celui sur lequel il est posé...).

Toutefois ce pgm n'est pas tout à fait optimal car le summum aurait été de faire remonter les scores (des feuilles vers le tronc) pour un choix encore plus optimal, et finalement laisser l'IA choisir...
Je ne sais pas si c'est par flemme ou déontologie qui m'ont empêcher d'aller au bout :clown: :boulet: OK je sors :boulet:
muzbang
Premium
Premium
 
Message(s) : 119
Inscription : 01 Sep 2018 22:00
Localisation : Auvergne

Re: Algorithme Button up !

Message par Ambroisie » 03 Nov 2019 10:18

Je ne sais pas si c'est tricher mais, pour les quelques parties de Button up que j'ai faites, j'ai fini par prendre de vrais boutons car je ne réussissais pas à imaginer dans mon pauvre cerveau ce que donnaient les empilements. D'ailleurs mon unique adversaire m'avait avoué l'avoir fait " au début " et je retiens surtout de ce jeu de vraies discussions souvent absentes dans beaucoup des parties auxquelles j'ai pu jouer par ailleurs et où il est parfois vain d'espérer un simple "bonjour" au départ !

Pour moi les échanges qu'on a la chance d'avoir sur certaines parties, quel que soit le jeu, me laissent un souvenir beaucoup plus agréable que le fait d'avoir gagné ou perdu. Il est vrai que je ne suis pas une " vraie joueuse " et que je ne sais même pas précisément ce qu'est un algorithme, je ne vais qu'à mon rythme ... :boulet:
Avatar de l’utilisateur
Ambroisie
 
Message(s) : 2369
Inscription : 19 Fév 2014 19:23
Localisation : Rhône-Alpes-Auvergne

Re: Algorithme Button up !

Message par peyo_fr » 03 Nov 2019 21:03

Ambroisie a écrit :... je ne sais même pas précisément ce qu'est un algorithme, je ne vais qu'à mon rythme ... :boulet:

Mon conseil : restes-y, avec un préfixe en algo-, généralement ça devient plus douloureux ... :boulet:
Avatar de l’utilisateur
peyo_fr
Premium
Premium
 
Message(s) : 2379
Inscription : 27 Fév 2014 0:27
Localisation : Paris/Angers/Arcachon

Re: Algorithme Button up !

Message par muzbang » 03 Nov 2019 22:12

Ambroisie, pour t'aider à comprendre, je vais te donner le premier ex. emple sous forme d'ex. ercice qu'on m'a donné à l'école.

La question était : écrire l'algorithme pour faire cuire un oeuf à la coke :mrgreen:
muzbang
Premium
Premium
 
Message(s) : 119
Inscription : 01 Sep 2018 22:00
Localisation : Auvergne

Re: Algorithme Button up !

Message par Paul Felz » 04 Nov 2019 16:08

Dear Muzbang,

either my french is too bad or your post is too long for me, so I did not quite understand: did you just write this computer programme (which I believe is quite a bit of work), or can you actually give a nice and short description of the optimal move (as, for example, in nim)?
Paul Felz
 
Message(s) : 57
Inscription : 17 Jan 2017 17:38

Re: Algorithme Button up !

Message par jch » 04 Nov 2019 16:30

@Paul,
I think there is no general optimal moves, except trying to promote that your colour is either on top of the other, or still associated with whites for keeping mobility
And of course you try to obtain the opposite for your partner’s colour!
I apply this always for the first move, and often for the second one (when I’m lazy...) then I switch to the boring work of imagining the remaining combinations!
As this is still possible in Button’up, I’m not sure any computer is really helpful if you accept spending time
I'm not sure but I also think that the minimax approach, where you minimize opponent score, is sometime too conservative against real human opponent...and if the risk is minimized, the opportunity for big scores is probably not there simultaneously... I let this to specialists!!
Not the same in games like Tatoo turtles, Tzaar etc where there are too much combinations for (normal) human brains and where using a computer is thus much less fair ;)

@muzbang, some edits:
This is only a personal opinion, and I'm not organizing tournaments anymore (for now...), but in any case, I would prefer that using AI is identified in the title of the game (and then the opponent is aware when choosing the game) and in all cases not used in tournaments and championships... there is no point in "checking the AI" in such games as this is spoiling the results, and the fun, for most players.
I would thus not play if I know I'm playing against an AI during a tournament. I don't know if this can still occur in the ongoing ABP, you already know that I'll prefer to resign than playing against your program.
Avatar de l’utilisateur
jch
 
Message(s) : 2480
Inscription : 24 Juin 2011 19:27
Localisation : Alsace-Lorraine

Re: Algorithme Button up !

Message par muzbang » 05 Nov 2019 2:16

Hey guys,

I forgot that not all are french speaking here :mrgreen:

In short words,

1 ) Yes, i wrote some functions (using text strings) in order to mimic the game moves = take a stack and put butons on the top of the next stacks, respecting the rules, another function to count points, other to check if the player can play again etc.

The ultimate function take a string like this : BR-BN-BR-N-R-N
and give back the string in witch it is transformed (taking into account if it's the 1st, 2nd or 3rd stack with white button).

here this will give
For the 1st with stack : RBN-BBR-N-R-N => this one alow to play again,
for the 2nd : NBR-BN-R-N-BR
For the 3rd : RN-BR-N-BR-BN

2 ) i decomposed all the tree at each step = at each player turn.

So for the previous example
The player that has this position BR-BN-BR-N-R-N
can give back those (you can see that the original 6 stack position can lead to only 3 stacks) :

RBN-BRR-NBN
NRR-BN-NBBR
RN-BR-BN-RBN
NBR-BN-R-N-BR
RN-BR-N-BR-BN

and so on

3)
then going from the "leaves" = the ultimate position (that allow to calculate the score) you go back to the trunk.
At each node, you can define if a choice is better for black or red, based on a rule that whatever i give to my opponent, he will always return back the worse position to/for me.
So the strategic choice at each node is to give the position witch the opponent will have the minus points among all the choices he has.

that works pretty well, but sometimes even with this algorithm, there are no way to win if the opponent do the right choices.


Now if the question is about strategy more like feeling it's quite simple (but i'am far to be an expert :roll: ).
Here is what i feel.
You don't want your opponent to make the last choice (with 2 stack in whitch there are a white button). But you also dont want him to let you 2 stack with one without white (=no choice) etc. The stragegy with 2-3-4-5 stacks are pretty easy to "humanly" play well. So you can see my program like a way to go in a position that will be favorable/analysable from a starting position where you probably think that one or another move don't change the game, that's false. The first move is always the more important.

I didn't analyse statistically the possibles choices but most important is probably to see if a position can lead to several replay. Because several replay can lead to more choices of the position you are able to let and with less stack (easier to analyse)
Could be intersting to analyse this :D what is the best first move.

I dont know the NIM language. All was written in VBA and physically represented in excel (stack written in cells and color for each node)


For example the function that says if a move make a replay (rejoue) or not :


Function rejoue(chaine)
Dim tabl() As String
rejoue = 0
nb_p = nb_piles(chaine)
ReDim tabl(nb_p - 1)

For i = 0 To nb_p - 1
tabl(i) = recup_element_n(chaine, i + 1)
Next

j = 1
While (j < nb_p) And (j - 1 < Len(tabl(0)))
If j = Len(tabl(0)) Then If Left(tabl(0), 1) = Left(tabl(j), 1) Then rejoue = 1

If j < nb_p - 1 Then tabl(j) = Right(Left(tabl(0), Len(tabl(0)) - j + 1), 1) & tabl(j)

If j = nb_p - 1 Then

tabl(j) = Left(tabl(0), Len(tabl(0)) - j + 1) & tabl(j)

End If

j = j + 1
Wend



End Function


Not sure if it answer your question :?
muzbang
Premium
Premium
 
Message(s) : 119
Inscription : 01 Sep 2018 22:00
Localisation : Auvergne

Re: Algorithme Button up !

Message par Paul Felz » 05 Nov 2019 17:24

Hi Muzbang,

the tree search algorithm you describe is what I expected to see. Then you observe that some positions are better or worse than others. And you note that your opponent can bring you into a situation where you loose no matter what you do. Hence, I would like to try to understand these situations, and see if I can put my opponent into such a situation.

muzbang a écrit :I dont know the NIM language.


It's not a language but a (very simple) game :clown:. Here are the rules:
  • You start with a few heaps of matches (or coins, or buttons, whatever ...). A standard starting position is four heaps with 7, 5, 3 and 1 match each.
  • When it's your turn, you choose a heap that's not yet emptied and take as many matches as you like, but at least 1.
  • Whoever takes the last match, wins.

This game has a very easy strategy. Write the numbers of matches in each heap as a binary number, then XOR them all together. Call this the "total". If at the beginning of you move, this number is not zero, you have a move that makes it zero. Do it. No matter what the opponent does next, after his move the total is nonzero again. So you can force a win.

But in the standard setup, the total is 0. Hence, if you are the start player, your opponent can force you to loose.

There is another version where you loose if you take the last match :scratch:. The strategy for this one is almost the same as above. But once you reduce to heaps with one match each, you leave an odd number of heaps to your opponent, not an even number.

So here is my question: Is there some similarly simple strategy for button-up?
Paul Felz
 
Message(s) : 57
Inscription : 17 Jan 2017 17:38

Re: Algorithme Button up !

Message par muzbang » 05 Nov 2019 19:18

Ok i think i see the game you're speaking of.
But in button up i think its way more complex.

And as i said, for the moment i didn't analyse the starting (or the intermediate) positions (that could be a great chalenge). And would be the only way to say what are the good moves (without using algorith, just using statistics that says says a move is better over another)

The only thing i'am sure is that in the starting position, if the 2 players have the algorithm, you know the result without playing (that's quite logic.... algorithm just apply a formulae and applying the formulae 2 times to the same situation give the same result)

I'll try to take screenshots (when back home) to make it more understandable ;)
muzbang
Premium
Premium
 
Message(s) : 119
Inscription : 01 Sep 2018 22:00
Localisation : Auvergne

Re: Algorithme Button up !

Message par muzbang » 05 Nov 2019 20:24

here is an example of the "end" of a tree. I start there cause this will make it easier to understantd.

Image


The algorithm says that you have the position RBN-BRR-NBN to play

you can return those 3 posistions:
NBRR-RBNBN
RNBN-BRRBN
NRBN-NBBRR

The 1st will let the red player win cause he will choose the option to win 5 points (-5 for black player)
The 2nd let the red win 1 point or 10 if he want to finish the game fastly :mrgreen:
the 3rd... will lead to a draw or +9 for black he the red make a missclick.

The 1 option is red cause red has the choice of ending with +4 or -5 (i reverse the numbers here cause the algorithm is based on a black view :bieremetal: )
option 2 is red cause the 2 options makes the red win
option 3 is black cause red can't win (best is draw)

If you go back the fist string (that should not be red sorry for the mistake :geek: )
It's black cause it's the position where the black plays, and he can choose 2 red options or a black option (that is draw in fact). SO he chose black.


If you zoom out and go to trunk of the tree :

Image

Hum there is another bug (big text strings with 9 / 0)
the decomposition of the tree is the player turn in each column.
and going right = playing and letting a position to next player.
1st, 3rd, 5th column is black player turn, 2nd, 4th etc are red

All the strategy of the fist plays are determined by the leaves (that give the points results), just getting backward (as explained before) from end to start give the best strategy.
muzbang
Premium
Premium
 
Message(s) : 119
Inscription : 01 Sep 2018 22:00
Localisation : Auvergne

Re: Algorithme Button up !

Message par Paul Felz » 05 Nov 2019 20:33

That's a great programming job :salut: ! And you are right, finding optimal positions without walking through the whole tree, that's a real challenge!
Paul Felz
 
Message(s) : 57
Inscription : 17 Jan 2017 17:38

Re: Algorithme Button up !

Message par RECIF » 10 Nov 2019 22:14

Hello Muzbang :)

Quelques réflexions après toutes ces lectures:

1) bravo de reconnaître, déjà!
2) je n'y connais rien du tout, juste entendu des discussions concernant la programmation, donc je ne peux apprécier pleinement; mais félicitations pour avoir su concevoir une telle application !
3) cela doit être aisé de pouvoir effectuer le même travail de prog. à Khitan, par exemple. Mais à la Guerre des Moutons, bien plus complexe, non?
4) si tu as besoin d'un cobaye pour affiner ton programme, je suis volontaire! En échange, tu me laisses gagner à Tzolk'in :wink:
5) Est-ce de la triche? Peu évident...

Le plus important est de se souvenir que les ordis, prog.,comme les véhicules sont des outils/aides dont il ne faut pas être dépendant! :twisted:

Marcher, ou courir, et surtout utiliser ses petites cellules grises pour apprendre et mémoriser est vital!
RECIF
 
Message(s) : 290
Inscription : 06 Nov 2012 22:41
Localisation : A la "frontière" entre la Belgique et la France!

Re: Algorithme Button up !

Message par muzbang » 10 Nov 2019 22:36

En fait je pense que tu as fait le cobaye au moins 1 fois :roll:
et je crois aussi que tu es celui qui a marqué le plus de points !

Enfin, la programmation c'est bien pour les jeux avec des limites (limites de mouvements, limite de combinaisons, pas d'aléa etc)
Comme c'est dit dans un des sujets que j'ai pu lire, c'est surtout aidant pour les jeux "abstraits"
donc les tzolkin' guerre des moutons et autres, il n'y a pas grand chose à programmer ;)
ce sont d'ailleurs les jeux que je privilégies sur BAJ... et pour lesquel je n'ai pas d'appli
Sauf Alchimistes, pour lequel j'ai fait un truc tout bateau qui me dit les possibilités de potion quand je donne 2 éléments avec des inconnues (et les répartition en proba de + / neutre / -), mais là c'est plus par flemme qu'autre chose car en général ce sont des combinaisons 2x4 ou 4x4 qui se font en 5 minutes à la main

button up, c'est juste une erreur de parcours :geek:
je suis tombé sur une vidéo règle (le nom me parlait car vu sur BAJ)... j'ai testé qq parties en mode instinct (d’où les défaites que j'ai :clown: ), et je me suis dit quand même ça doit pas être compliqué à programmer.
J'y ai passé quelques soirées ;) mais pas mécontent du résultat.
Malgré qq bugs trouvés en route et un changement radical de la prog après m’être rendu compte que ma première implémentation était complètement ingérable tant d'un point de vue chrono que de l'ergonomie du pgm.
La seconde idée s'est avérée beaucoup plus efficace et utilisable.... en partant simplement de fonctions qui "mimait" le jeu tour / tour, ce qui était ensuite plus simple pour décomposer un arbre

Par contre je ne te laisserai pas gagner à Tzolk'in. SI tu gagnes, ce sera juste parce que tu as été meilleur :mrgreen:
muzbang
Premium
Premium
 
Message(s) : 119
Inscription : 01 Sep 2018 22:00
Localisation : Auvergne


Retour vers Button Up!

Qui est en ligne ?

Utilisateur(s) parcourant ce forum : Aucun utilisateur inscrit et 0 invité(s)

cron