La règle du jeu est simple : elle est donc facile à programmer: Mais le jeu est complexe. Et concevoir un bon logiciel est beaucoup moins évident Le défi est d'autant plus intéressant à relever ! Pour vous mettre dans le bain, nous vous proposons un « bon petit programme ». A vous de faire mieux, ou de vous rabattre sur les logiciels commercialisés que nous avons testés.
On ne compte plus les logiciels d'Othello. Plus ou moins bons, certes. Il faut dire que le plus récent des grands jeux stratégiques de damier est aussi l'un des plus faciles à programmer... du moins jusqu'à un certain point ! Le jeu lui-même, tel le Phénix de la légende, renaît de ses cendres en 1971 au Japon, après avoir été pratiqué à la fin du XIXe siècle en Grande-Bretagne et en Allemagne sous le nom de Reversi. Il conquiert 20 millions d'adeptes au Japon, atteint les Etats-Unis en 75, commence sa carrière en France en 77, où il se dote d'une fédération en 83. Phénomène nouveau : plus de la moitié des joueurs affiliés programment ! Ils sont même nombreux à avoir découvert Othello par l'intermédiaire d'un programme. Voulez-vous vous lancer dans la programmation d'un « adversaire informatique » ? N'hésitez pas : commencez par Othello ! Les programmeurs chevronnés vous conseilleront de programmer en un langage « récurrent » (dont les sous-programmes font appel à eux-mêmes sans imbrication de boucles), comme le Pascal ou le langage C. C'est vrai, mais le bon vieux Basic, quoique lent, est largement suffisant pour débuter. L'essentiel étant de comprendre comment évaluer une position. Rappelons brièvement le principe du jeu. Le jeu se déroule sur un damier 8x8. Les pions utilisés sont bicolores : noirs d'un côté, blancs de l'autre. L'un des deux joueurs posera des pions côté noir, l'autre côté blanc. A son tour, un joueur doit poser un pion à sa couleur prenant « en tenaille » avec l'un de ses pions déjà posés, un ou plusieurs pions adverses. Ces pions sont retournés. Si un joueur ne peut retourner de pions adverses, il passe son tour. Quand le damier est plein, ou quand aucun joueur ne peut plus jouer, le gagnant est celui qui possède le plus de pions à sa couleur. LE JEU Les deux notions capitales du jeu sont la « mobilité » et l'« évaluation dynamique des coups ». On dit qu'un joueur à une «« bonne mobilité », quand il a un grand nombre de cases où jouer. Pour l'évaluer, rien n'est plus simple, il suffit de les compter. La notion est quantifiable. Elle peut donc être utilisée par le programme. L'expérience montre que la mobilité est un facteur essentiel de la victoire. Un joueur, qu'il soit humain ou programmé, doit tenter d'accroître sa mobilité ou... de réduire celle de son adversaire. Dans cette optique deux stratégies sont actuellement utilisées : occuper le centre de la position des pions (et non forcément celle du plateau de jeu) ou « bétonner », c'est-à-dire occuper uniquement deux bords contigus. Contrairement à une opinion largement répandue, les cases n'ont pas de valeur absolue en soi. En voici un exemple simple. Nous avons emprunté au programmeur suisse Anders Kierulf un tout petit fragment du programme qu'il présente au concours de programmes d'Othello organisé depuis des années par notre confrère y Ordinateur individuel à chaque Sicob. Les notations utilisées (A1, A2 et A3) sont celles du diagramme classique (voir figure 1). 
Figure 1 : position de départ et notation pratiquée à Othello.
L'exemple choisi est celui de l'évaluation « dynamique » de la case A2. En voici la traduction Basic-français : Si A1 est occupé par un pion « micro », alors A2 = 175 Si A1 est occupé par un pion adverse, alors A2 = 0 Si A1 est vide alors : a) si A3 est vide, alors A2 = - 50
b) si A3 est occupé par un pion adverse, alors A2 = -150. Toute une série de tests associe à chaque case jouable sa valeur, compte tenu de son environnement. La fonction d'évaluation doit rassembler tous les éléments qui permettent de juger une position. En l'état actuel des connaissances à Othello/Reversi, c'est une combinaison de la mobilité et de la valeur dynamique des cases jouables. Personne n'est en mesure d'affirmer si la stratégie gagnante consiste à occuper le centre de la configuration de pions ou deux bords contigus. Cela dit, il existe des écoles ou des modes. En France, les joueurs pratiquent de préférence l'occupation du centre, alors qu'en Grande-Bretagne et surtout en Italie, les joueurs « bétonnent ». En terme de programmation, l'une des difficultés est d'empêcher le système d'évaluation d'osciller entre ces deux stratégies. Pour faire vos débuts dans la programmation 6'Othello, vous n'aurez pas à vous pencher sur ces problèmes. Il est même possible de concevoir un programme très honorable qui — à rencontre de la théorie — ne pratique pas l'évaluation dynamique des cases. C'est le cas de celui que nous vous proposons. Réalisé par Emmanuel Lazard, vice-cham-pion de France d'Othello, il est fort court. Si vous êtes débutant, il vous donnera déjà bien du fil à retordre.
Avant de vous mettre au clavier de votre micro, voici quelques-uns de ses secrets. Le listing proposé reprend astucieusement l'idée développée en son temps par le docteur Samuel pour l'un de ses premiers programmes de dames : pourquoi concevoir le damier comme un tableau à deux dimensions (vision de joueur !), alors que l'ordinateur se débrouille mieux et surtout plus vite avec une seule dimension, celle des cases numérotées de 0 à 99 ? Donc pas de cases définies par leurs coordonnées en X et en Y (deux dimensions), mais seulement des numéros. Pour connaître la valeur d'une case voisine, il n'est plus nécessaire d'ajouter ou de retrancher des valeurs à chacune des dimensions en X et Y ; il suffit d'ajouter 1, 9, 10, 11, - 1, -9, - 10, - 11, pour atteindre la case désirée. D'où gain de temps. De plus, à chaque case sont associées deux autres valeurs. La première indique le contenu de la case : vide (0), pion blanc (1) et pion noir (2). Une rangée de cases cernant le damier 8 x 8 a été ajoutée afin que le programme ne continue pas ses tests hors du plateau de jeu. La valeur affectée à chacune de ces cases extérieures de bordure est - 1. Cette bordure explique que le programme teste des cases dont les numéros varient entre 0 et 99 (soit 100 cases) et non entre 1 et 64 (ou 0 et 63). La seconde valeur affectée à chacune des cases est d'ordre tactique. Plus la valeur est grande et plus le programme sera tenté d'y jouer. La figure 2 indique les choix du programmeur. 
Figure 2 : à chaque case du damier est affectée une valeur à laquelle s'ajoute celle des pions à prendre. Les lignes 150 à 220 représentent ces valeurs pour votre microordinateur.
Par exemple, les cases d'angle ont une forte valeur (40) tout simplement parce que le pion qu'on y pose est imprenable. A l'inverse, les cases qui lui sont contiguës ont des valeurs faibles (3, 0 et 3), car elles peuvent servir de « tremplin » à l'adversaire pour s'emparer d'une case d'angle. Ces valeurs peuvent être modifiées (ligne 150 à 220 du listing). Par exemple, vous pouvez essayer d'apprendre à votre programme à « bétonner » en ajoutant 5 ou 10 à toutes les cases des deux premières colonnes et des deux premières rangées. A vous de chercher le meilleur compromis...
Pour compenser l'absence d'évaluation dynamique des cases (grande consommatrice de lignes), l'auteur a eu l'idée d'associer la valeur tactique de chaque case au nombre de pions pris lors de la pose. Voyons comment fonctionne le programme et son système d'évaluation. C'est au programme de jouer. Il teste la valeur du contenu de chaque case dans l'ordre de leur numéro. Dès qu'il rencontre une valeur - 1 , 1 ou 2 (bordure, pion blanc ou noir), il passe à la case suivante, car il n'a ni le droit de jouer sur un pion déjà posé, ni bien sûr hors du plateau de jeu. En revanche, il s'arrête dès qu'il rencontre une case vide et commence une nouvelle série de tests dans huit directions. Il testera le contenu d'une nouvelle colonne, diagonale ou rangée dès qu'il se rendra compte qu'il ne peut pas jouer (case voisine vide ou contenant un pion « ami »). La case testée sera considérée comme jouable si la case voisine, et éventuellement les suivantes dans la même direction, contient des pions adverses, eux-mêmes suivis d'une case contenant un pion ami. Si c'est le programme, il évaluera le coup en respectant les règles suivantes : a) jusqu'au 18e coup : valeur tactique de la case - nombre de pions pris ;
b) après le 18e coup : valeur tactique de la case + nombre de pions pris. Le programme teste ainsi toutes les cases jouables, et joue celle pour laquelle il obtient le meilleur score. Une question ? ... Oui, bien sûr. Pourquoi le programme retranche-t-il le nombre de pions pris dans la première partie du jeu ? Cette manière de procéder permet au programme de réduire le nombre de pions qu'il prend à chaque coup pour s'assurer une meilleure mobilité. Puis, après le 18e coup — et comme le but du jeu est de prendre le plus de pions ! — il s'engage dans la procédure du maximum de prises. UTILISATION DU PROGRAMME Il vous demande en premier lieu si vous prenez les X ou les O. Appuyez sur la lettre du clavier correspondant à votre choix. Comme toujours, pour confirmer votre ordre, vous appuyerez sur la touche RETURN (ou ENTER ou ENTREE). La pose d'un pion s'effectue en entrant une lettre désignant la colonne où vous jouez (puis RETURN), suivi d'un chiffre désignant la rangée (puis RETURN). Important : si vous êtes contraint de passer votre tour, tapez O RETURN O RETURN, au lieu d'indiquer les coordonnées d'une case. Si vous désirez nettoyer l'écran, tapez Z lorsque le programme vous demande de désigner la colonne où vous jouez, l'écran s'effacera, puis affichera à nouveau le plateau de jeu. Jeux & Stratégie n°35
|
