La création du mois : septembre 2014

Découvrez chaque mois une variante inédite.

Marguerite écossaise

Scottish_daisy

(variante créée le 03/08/2011)

FightClub

Publicités

Petite précision

Pour des raisons que je n’ai pas encore analysées mais que je devine vaguement, certains commentaires  n’apparaissent pas dans la liste des commentaires récents (à droite sur votre écran). [1]

Je signale donc des commentaires déposés récemment (par atto, mogwai et johy) sur les articles suivants :

Le livre d’or de MiGs : https://onlineabalone.wordpress.com/abalone-en-ligne/le-livre-dor-de-migs/

Napoléon et le jeu d’Abalone : https://onlineabalone.wordpress.com/abalone-academy/un-peu-de-theorie/napoleon-et-le-jeu-dabalone/

Cartographie des joueurs : https://onlineabalone.wordpress.com/abalone-en-live/cartographie-des-joueurs/

Cliquez sur les liens pour accéder aux articles et aux commentaires

[1] La raison est simple : il s’agit d’un blog ! Le principe d’un blog est de mettre en avant l’actualité la plus récente. Il se trouve que j’ai quelque peu détourné le menu de sa destination pour en faire une sorte d’encyclopédie d’abalone. De fait seuls les commentaires des articles apparaissent dans les « commentaires récents ». Les commentaires postés dans les pages ont donc de fortes chances de passer quasiment inaperçus. Pour donner une visibilité maximale à votre commentaire, mieux vaut le poster dans un article (même ancien) portant sur le même sujet ou sur un sujet proche. (note du 08/05/2015)

FightClub

Problème de septembre (version simplifiée)

La version précédente semble ne pas avoir convaincu, puisque personne n’a proposé de solution (ce qui ne veut pas dire que personne n’a réfléchi dessus 😉 )

Voici donc une version (beaucoup) plus facile qui je l’espère aura plus de succès.

Ouch!

NIVEAUFACILE
TRAIT : NOIR
OBJECTIF : GAGNER AVEC BLANC EN 3 COUPS (plusieurs solutions possibles)

Ouch-easy

 Une autre approche du problème est possible : jouer Noir et essayer de tenir plus de trois coups. Et là bon courage !

°°°°°°

Vu que pour le moment nous n’avons pas (encore) de technique pour poster des visuels, il n’y a pas d’autre moyen que le codage pour communiquer votre solution. Mais ce n’est pas si compliqué car ULA peut le faire à votre place ! Voici comment :

Onglet Jeu / Adversaire / Humain contre humain
Jouez votre suite de coups dans ULA
Onglet Partie / Sauvegarder sous forme de texte
Récupérez votre fichier texte
Le codage est fait, vous n’avez plus qu’à copier/coller dans votre commentaire  🙂
A partir de là, j’essaie d’en faire un PDF dès que possible.

FightClub

Solutions

°

Accédez à tous les problèmes mensuels.

Le livre d’or de MiGs…

Le livre d’or de MiGs fait un flop : aucun commentaire une semaine après sa publication !
Pourtant, nombreux ont été les joueurs à déplorer la disparition de ce site.
Manque de visibilité de la page ?
A tout hasard, je signale qu’elle est actuellement accessible sur votre droite, dans les LIENS ABALONE.
Son emplacement actuel est : Le jeu en ligne / Le livre d’or de MiGs.
Vous pouvez aussi y accéder par ce lien.

FightClub

Programmation du jeu d’Abalone

(Mise à jour du 13 septembre 2014)

Avertissement : l’article ci-dessous a été, à quelques modifications près, éhontément copié sur un site que je ne nommerai pas, puisque ledit site ne dit mot sur MiGs, et a toujours refusé de donner le lien vers MiGs.


Créer un programme qui joue à Abalone présente un certain nombre de difficultés :
• il n’existe quasiment aucune information théorique sur le jeu ;
• les joueurs forts sont rares ;
• le nombre de coups possibles, dans une position donnée, peut atteindre 148, c’est supérieur au nombre de coups possibles aux échecs. Sans atteindre la complexité combinatoire du jeu de go ou du jeu d’échecs, le nombre de coups possibles est suffisamment élevé pour mettre à mal les algorithmes de force brute habituels.
• le fait que le but du jeu soit progressif (éjection boule après boule) rend difficile la définition d’une fonction d’évaluation continue dans la mise en œuvre de l’algorithme alpha-beta, les programmes pouvant hésiter entre l’éjection d’une bille et un avantage positionnel, ou avoir tendance, comme les débutants, à éjecter des boules le plus tôt possible dans la partie.

Concepts mis en oeuvre par les programmes :

Les premiers programmes jouant à Abalone utilisaient essentiellement dans leur évaluation des positions les concepts suivants :
• connectivité (cohésion des groupes de billes) ;
• nombre de billes de chaque joueur ;
• une valeur théorique de la position des billes (les bords sont désavantageux, le centre est crucial).
Les programmes les plus récents qui jouent à Abalone mettent en œuvre un ou plusieurs des concepts suivants dans l’évaluation d’une position :
• nombre de sumitos possible, et type de sumitos comme leur influence sur le centre ou pas, la poussée vers le bord (l’idée nouvelle de MLA dans ce domaine) ;
• nombre de menaces d’éjections de billes ;
• évaluation géométrique de la position (l’idée nouvelle d’Aba-Pro dans ce domaine, l’utilisation du centre de masse respectif des groupes de billes de chaque joueur) ;
• la phase du jeu en cours et le type de position (ouverture, milieu de jeu, fin de partie, position type standard, gros avantage positionnel pour l’un des camps, etc.) ;
• nombre de groupes de billes, nombre de billes par groupe (utilisé, notamment, par Nacre).

Programmes qui jouent à Abalone :

Les trois meilleurs programmes d’Abalone étaient en 2006 : MLA, Aba-Pro et Nacre. Ces trois programmes sont issus des travaux de recherche fondamentale dans le domaine de la théorie des jeux effectués par leurs auteurs.
• My Lovely Abalone (MLA), conçu par David Malek (France) : son développement a débuté fin 2003 ; MLA n’est parvenu à battre Aba-Pro que fin 2005. Au début de son développement MLA intégrait une évaluation de la position très similaire à Aba-Pro. MLA a battu Aba-Pro en réfutant l’évaluation de dangerosité de la position d’Aba-Pro, en intégrant le dynamisme d’une position au travers de l’utilisation du nombre de sumitos comme critère complémentaire. La disponibilité d’Aba-Pro pour tester MLA a été cruciale, les programmeurs de MLA ont pu ainsi utiliser certaines des faiblesses d’Aba-Pro pour le vaincre.
• Aba-Pro, conçu par Tino Werner (Autriche) : sans conteste la première avancée significative dans le domaine. Redoutable programme, meilleur du monde de 2002 à 2005. Aba-Pro est remarquable par sa maîtrise de la combinatoire (le programme choisit ou non d’explorer les coups suivants en fonction d’une évaluation de la dangerosité de la position) et sa fonction d’évaluation (par utilisation d’une combinaison des centres de masse des groupes de billes des adversaires). Aba-Pro intègre également la prise en compte des phases de jeu (ouverture, milieu de jeu, fin de partie). Aba-Pro repose sur la maîtrise de la théorie des graphes, et d’heuristiques spécifiques au jeu d’Abalone. Aba-Pro était le sujet de thèse de ses auteurs à l’Institut de génie logiciel de l’Université Technologique de Graz (Autriche).
• Nacre, conçu par Peer Sommerlund (Danemark) : un programme fort, opposant malheureux d’Aba-Pro en 2003. Nacre utilisait, en 2003, un réseau de neurones, domaine de connaissance où Nacre a au moins égalé l’état de l’art.

Ce classement est établi selon la blitz ladder list officielle des programmeurs d’Abalone publiée sur le groupe Yahoo de programmation du jeu d’Abalone (la ladder list consiste à estimer la valeur de moteurs en leur donnant une seconde par coup).

Aba-Pro et Nacre se sont, de plus, rencontrés plusieurs fois et Aba-Pro a triomphé. MLA a été reconnu meilleur par l’auteur d’Aba-Pro qui disposait d’une copie de MLA pour valider la défaite d’Aba-Pro.

Le code source de ces trois programmes n’est pas libre et n’est pas distribué. Seul Aba-Pro est disponible en téléchargement.

En 2011 est apparu un sérieux concurrent à ces trois programmes : ULA (Uncle Lolo’s Abalone), conçu par Laurent Pagli (France). Toutefois, aucune rencontre officielle n’a eu lieu entre ce challenger et ses trois rivaux.

Il existe d’autres programmes d’Abalone, qui ne résistent pas aux trois anciens cités plus haut, notamment :
• Abbalone 3D, Macintosh
• Jens Thiele Abalone, interface de jeu par courrier électronique
• Olivier Thill : Abalot
• Peter Tax Abalone, Macintosh
• Random Software : Abalone 1.2
Les codes sources de Abalot et Peter Tax Abalone sont disponibles sur Internet.

Les meilleurs joueurs d’Abalone parviennent à triompher de l’ensemble de ces programmes, les trois meilleurs cités plus haut compris.

Programmes et connaissance du jeu :

Lorsqu’on débute à Abalone émerge rapidement la certitude que le centre du tablier est primordial. Il en est de même pour la connectivité des billes (elles doivent être regroupées et présenter une forte cohésion). Contrairement aux jeux les plus anciens comme le jeu d’échecs, les programmes d’Abalone ont été créés avant que le jeu ne soit véritablement analysé de manière approfondie.

Depuis l’apparition d’Aba-Pro, la connaissance du jeu a progressé. Plusieurs catégories de positions ont été isolées, notamment la position de witch ring (cas où les billes d’un des deux adversaires se trouvent entourées par les billes adverses).

°

Abalone_witch_ring

witch ring, par François Haffner

°

Nacre participe activement depuis 2005, à l’analyse des positions de fin de partie, notamment la constitution de prisons (cas où une bille se trouve isolée au bord du tablier de jeu, sans possibilité de reconnexion rapide avec ses camarades de la même couleur) ou encore à la comparaison entre l’avantage matériel (le nombre de billes de supériorité) et la position.

MLA a mis en évidence une pratique des plus forts joueurs : l’avantage positionnel est parfois aussi important que l’avantage matériel. MLA peut ainsi abandonner une ou plusieurs billes en début de partie pour obtenir un avantage positionnel déterminant.

En combinant Nacre, MLA et l’expérience de l’un des plus forts joueurs, les travaux menés en 2006 sur ces sujets ont isolé des positions où l’avantage positionnel ne parvient pas à compenser un trop gros déficit matériel (le nombre de billes est insuffisant pour parvenir à gagner). Ci-dessous, un exemple de position de witch ring où l’avantage positionnel ne permet pas de compenser le désavantage numérique.

Globalement, les programmes contribuent à améliorer sensiblement le niveau de jeu, en proposant un adversaire toujours disponible et capable de battre un joueur fort. Leur capacité de calcul tactique (prévision des coups à l’avance) entraîne également les joueurs aux aspects combinatoires du jeu.

Gramgroum

Tournoi off-line

Je constate en lisant les commentaires sur l’article Abalone World Championship que les participants à cette discussion ont pratiquement tous (peut-être même tous) exprimé leur envie d’une rencontre en live autour d’abalone. Je suis partant aussi.

Evidemment, un tel projet pose un tas de problèmes et de questions. Les trois premières qui me viennent à l’esprit sont les suivantes : Qui s’y colle pour l’organisation ?  Où ? Quand ? (et puis plein d’autres questions, mais il faut bien commencer la réflexion quelque part)

Ma région (l’Alsace) est très jolie, mais un peu excentrée ; il y a quelques années, Gaz-Gaz avait lancé sur le forum Aceboard un appel pour une rencontre des joueurs off-line. On s’était retrouvés à deux, à Colmar.  🙂  Le moment a été très sympa, mais au regard de cette expérience, je ne suis pas sûr d’être le mieux placé géographiquement.

Gramgroum

Abalone, un jeu « olympique »

The-School-of-Athens_abalone

L’École d’Athènes, par Raphaël

(cliquez sur l’image pour l’agrandir)

°°°°°°

Cette version non censurée de L’École d’Athènes (fresque du peintre italien Raphaël dont la version officielle date de 1509-1510) vient alimenter une théorie controversée selon laquelle Abalone aurait été révélé aux hommes par les dieux de l’Olympe. Raphaël semblait penser que ce jeu divin était connu au moins depuis l’Antiquité grecque, puisqu’au premier plan on y voit Héraclite d’Ephèse (au centre), et Euclide ou Archimède (à droite) jouer à abalone.
On notera néanmoins que l’académisme dominait à la fois la pensée Antique et celle de la Renaissance, puisque les personnages représentés jouent exclusivement en Standard, la Marguerite belge étant alors considérée comme une variante décadente, jouée uniquement par les Barbares.

Si cette théorie se voyait un jour confirmée par des faits historiques incontestables, l’invention présumée d’abalone par deux de  nos contemporains s’avèrerait n’être qu’une vaste supercherie : ils auraient tout au plus redécouvert un jeu tombé dans l’oubli, et s’en seraient de manière illégitime attribué la paternité ! Mais pour le moment nous n’avons que des suspicions (la présence d’abalone aux « Mind Sports Olympiad » semble témoigner du caractère « olympien » de ce jeu) mais aucune preuve. Affaire à suivre…

FightClub