Re: Algorythm...

["Pascal Dupretz" <pascal@xxxxxxxxxxxxxx>]

Bonjour,

Pour Othello, le plateau fait 8x8. Les joueurs sont obligés de 
retourner des
pions de l'adversaire à chaque coup, par encadrement horizontal, 
vertical ou
diagonal (ou inclusif), mais tout ça, j'imagine que tu le sais. Une 
petite
remarque quand même, quand un joueur n'a pas de pion à retourner, il 
passe
son tour. Pour ce qui est d'échafauder des stratégies, Othello fait 
appel à
une logique un peu particulière. L'objectif du jeu est d'avoir le plus 
de
pions de sa couleur à la fin. Pour atteindre cet objectif, le vainqueur 
sera
celui qui retournera le plus de pions dans les derniers coups de la 
partie.
C'est souvent celui qui a réussi à 'conquérir' les bords du plateau et 
les
coins (cases non retournables) qui gagne. Pour y arriver, cela passe 
souvent
par une stratégie de minimisation au début et en milieu de partie,
c'est-à-dire paradoxalement avoir le moins de pions de sa couleur sur le
plateau afin d'offrir un minimum de coups possibles à l'adversaire. Il 
faut
surtout chercher à minimiser les pions de sa couleur situés en bordure 
de
figure (en frontière), car ce cont ceux qui sont le plus rapidement
'retournables'. A chaque fois que l'on retourne un pion de sa couleur, 
il
faut penser aux coups qu'il permettra (ou non) pour l'adversaire. L'un 
des
critères de choix des bons coups, peut donc être ceux qui minimisent le
nombre de pions retournés en frontière. En fait, les vrais bons coups 
sont
ceux qui maximisent le nombre de pions retournés tout en minimisant 
ceux que
l'adversaire pourra retourner en retour. L'une des pistes pour 
construire un
algorithme correct pourrait consister à calculer, pour chaque coup 
possible,
le nombre de pions retournés (np1) et le nombre de coups (nc) possibles
ensuite pour l'adversaire (ou le nombre de pions qu'il pourra retourner 
en
retour np2), et de choisir en définitive le coup qui maximise la 
différence
(np1 - nc) ou (np1 - np2) (ou à un moindre niveau qui minimise 
simplement
'nc'). Essayez donc de faire une partie vous-même en appliquant cette 
règle
contre n'importe quel joueur de base, et vous vous retrouverez souvent 
dans
une très bonne situation au moment d'attaquer les bords et les coins
(souvent la dernière phase du jeu), cases déterminantes pour l'issue de 
la
partie. La stratégie de minimisation a une limite (lim min(x) = 0), 
celle de
se voir retourner tous ses pions et de perdre ainsi la partie car 
n'ayant
plus de pion de sa couleur (il faut y faire attention en s'assurant à 
chaque
fois des pions sûrs). La fin de partie peut être gérée avec la même 
règle
que précédemment ou par un algorithme de calcul systématique qui 
calculera
toutes les issues (en nombre de pions finalement obetnus) et proposera 
le
choix qui maximise le gain. C'est possible car  plus on avance vers la 
fin
de partie, moins il y a de coups possibles à jouer, on réduit donc
"l'explosion exponentielle" liée à ce type d'algorithme.

C'était un peu long, mais j'espère que cela pourra t'être utile.
Pascal

----- Original Message -----
From: "Martin Dufresne" <martindufresne@sympatico.ca>
To: <pistes-l@director-fr.com>
Sent: Saturday, February 15, 2003 7:45 PM
Subject: Algorythm...


> Bonjour a tous!!!
>
> Je cherche a faire le jeux Othello ou reversi..selon l'appellation que
vous
> voulez, mais voila. Quelqu'un saurait-il ou je pourrais trouver un
algorythm
> qui me permettrait de rendre l'adversaire (dans ce cas l'ordinateur),
> capable d'evaluer les possibilites de coups qui lui sont possibles, 
>afin
de
> le rendre un adversaire de taille.
>
> J'ai bien essayer de lui faire faire une telle chose pas calcul brute,
mais
> les possibilites sont incroyable et le calcul devient fou!!! De plus, 
>les
> seules algorythm que jai reussi a trouver sont en C ou en Java.... Ce 
>qui
de
> maide pas vraiment vu que je ne connais pas ces langange :(.
>
> Merci d'avance pour les reponses...
>
> Martin
>
>