IA 2014, TD 23.09

La décision de prendre votre groupe date d'hier. Donc, aujourd'hui nous aurons une séance approximative, la vitesse de croisière c'est pour les semaines à venir.

"Le général qui gagne une bataille a médité, calculé, avant de combattre. Le général qui perd une bataille a fait moins de calculs. Donc, beaucoup de stratégie mène à la victoire, peu de stratégie à la défaite". (Sun Tzu)

"La question stratégique principale qu'il [Stalin] se posait, était, si le nombre de soldats envoyés à la mort certaine était suffisant pour fatiguer l'ennemi..." (Un officier russe en 1945. Personne ne sait ce qu'il est devenu...)


Exercice 1. On reprend l'exercice de la séance TD2 : le jeu de Nim.

Jeu de NIM, sur le site Archimedes-lab Jouons un peu [Variante : "misère" : le dernier perd].

Le jeu est très bien documenté, la stratégie optimale existe (comme vous le savez). Trouver la description mathématique de ce jeu dans le cas le plus général, représentez les états à l'aide de le "somme-nim" (XOR), et construisez, au moins partiellement le graphe d'états / coups. Comment formaliser la différence de base dans la phase finale du jeu entre les versions "dernier gagne", et la version "misère", où le joueur forcé de prendre le dernier jeton perd?

Ce site (dotSphinx) propose la variante "dernier gagne", avec des configurations initiales aléatoires (nombre et hauteurs de piles variables).

Prendre une configuration fixe, simple, par ex.: 1 / 3 / 5 / 7, et codez ce jeu. Ceci n'est qu'une (un peu longue) conditionnelle en cascade.


Exercice 2.

Analysez le premier exercice de la feuille de Grégory – Le jeu d'échecs, une position terminale, gagnante pour les blancs – (c'est une copie locale. Vous avez, bien sûr, l'adresse Moodle également).


Si vous arrivez à analyser le jeu en profondeur 3, vous pourrez aussi élaborer la stratégie complète qui fait gagner les blancs. Un joueur d'échecs parmi vous?... Qui connaît la stratégie : Roi + Tour contre Roi?

Vous trouverez sur le Web un éditeur de positions sur l'échiquier ici ou ici.

(La première application permet aussi de jouer contre l'ordinateur. Le joueur automatique est faible [presque comme moi...], mais utilisable).


On laisse pour l'instant l'autre exercice, car je pense qu'il est utile de travailler un peu sur les vraies techniques implémentables, à savoir les parcours par les arbres.

Exercice 3.

Représentez le problème "stratégique" connu comme Loup-Chèvre-Choux sous forme de graphe (ou d'arborescence rationnelle [infinie, à cause des boucles].

Question générale : Que savez-vous sur le parcours des arbres, en profondeur et en largeur?


Exercice 4. Questions de culture générale.


Solutions (peut-être)

Semaine suivante
Retour à l'index