	Programmer un jeu intelligent
	#############################

	Continuons avec les casse-tetes (voir l'article sur le problme
des huit reines), mais allons un peu plus loin et tentons de programmer un
jeu! L'utilisateur contre l'ordinateur. La difficult est de concevoir une
stratgie anticipant tous les mouvements possibles de l'adversaire
afin de faire le meilleur choix.

Le surmdiatis jeu du morpion
------------------------------
	Il consiste simplement  aligner trois de vos signes en ligne, en
colonne ou en diagonale sur une grille carre de 3 sur 3. Chaque joueur
cochant une case  tour de role.
	Qui n'a pas vcu quelques moments d'motion pure face  ce
principe simple et pourtant terriblement pigeur? Lorsqu'on perd face 
un adversaire quelconque, on ne l'a jamais vu venir!
	Et pourtant, il faut si peu d'intelligence... le programme que je
vous prsente tient dans un petit TOS de 780 octets! Interface comprise!

Les structures de donnes
-------------------------
	Je le rpte: des donnes bien structures font un programme
facile  mener  terme. Malgr la prsentation en deux dimensions du jeu,
j'ai choisi une structure  une dimension pour les donnes. Les cases sont
numrotes de 1  9. Le tableau 'case' contient des octets ainsi dfinis:
	1: c'est un pion de l'ordinateur
	0: la case est vide
	-1: c'est un pion du joueur.
	Au dmarrage, il est vident que tout le tableau est  zro.
	Ensuite, huit alignements sont possibles, je les ai donc numrots
de 1  8. Pour les verticales 1,2,3; pour les horizontales 4,5,6; pour les
diagonales 7 et 8. A chaque alignement est associ un octet dans le
tableau 'lignes' ainsi dfini:
	(nombre de pions ordinateur) - (nombre de pions joueur)
	Deux valeurs sont intressantes:
	3: cela veut dire 3 pions ordinateur, position gagnante,
	-3: cela veut dire 3 pions joueur, position perdante.
	Pour finir, chaque case est lie  2, 3 ou 4 alignements. Pour
rsumer ces liens, j'ai cr un tableau 'case_ligne' contenant une valeur
binaire dont la structure est explique en figure 1. Ainsi, chaque fois
que je place un pion sur une case, je sais exactement quels alignements je
dois modifier.

Le principe de recherche
------------------------
	En cherchant sur le papier, on peut laborer facilement un
principe de recherche adapt au morpion en tenant compte de certaines
positions cl. Mais j'ai voulu donner un exemple assez gnral de
recherche que l'on pourrait facilement tendre  un morpion de plus grande
taille, voire meme a des jeux genre "Puissance 4" sans grande difficults.
	"PLACER L'ORDINATEUR" c'est:
	1) prendre une case libre
	- si il n'y en a plus aller en 2)
	- sinon, si j'obtiens un alignement, renvoyer "GAGNANT"
	- sinon, "PLACER LE JOUEUR"
		- si joueur "GAGNANT", retour en 1)
		- si joueur "PERDANT", renvoyer "GAGNANT"
		- si "INDECIS", retour en 1)
	2) ici, c'est le cas ou aucun coup gagnant n'est touv
	- si aucun coup indcis n'a t trouv, renvoyer "PERDANT"
	- sinon, renvoyer "INDECIS"


	"PLACER LE JOUEUR" c'est:
	1) prendre une case libre
	- si il n'y en a plus aller en 2)
	- sinon, si j'obtiens un alignement, renvoyer "GAGNANT"
	- sinon, "PLACER L'ORDINATEUR"
		- si ordinateur "GAGNANT", retour en 1)
		- si ordinateur "PERDANT", renvoyer "GAGNANT"
		- si "INDECIS", retour en 1)
	2) ici, c'est le cas ou aucun coup gagnant n'est touv
	- si aucun coup indcis n'a t trouv, renvoyer "PERDANT"
	- sinon, renvoyer "INDECIS"

	Les deux procdures sont symtriques et s'entre-appellent de
manire rcursive. Mais elles finissent toujours par s'arreter soit parce
qu'une position gagnante est trouve, soit parceque plus aucune case n'est
libre (partie nulle).
	Finalement, la procdure principale appelle "PLACER L'ORDINATEUR"
et:
	- si "GAGNANT", on joue ce coup (bien sur...)
	- si "INDECIS" on joue l'une des positions indcise (en fait, la
	dernire rencontre)
	- si "PERDANT" on joue la premire case libre, de toutes faons,
	on est mal barr.

	Sauf qu' l'usage, je ne sais pas si vous arriverez  placer
l'ordinateur dans une position perdante! Meme si vous commencez...

L'utilisation du programme
--------------------------
	La superbe interface entirement sous TOS est limite au strict
minimum. La grille s'affiche sous forme d'un carr de chiffres. Tapez sur
un chiffre du pav numrique pour placer votre croix (le joueur joue avec
les croix en vido inverse). Avant de rejouer, attendez que l'ordinateur
ait plac son pion (un O majuscule en vido inverse). La fin est signale
si la partie est nulle (souvent), si l'ordinateur gagne (a arrive) ou si
vous gagnez ( voir!).
	Un appui sur une touche revient alors au bureau.


Le listing
----------
	Le programme a t mis au point avec ASSEMBLE, n'ayant pas utilis
de macros ni de spcificits de cet assembleur, le texte suivant sera
facilement adaptable  DEVPAC ou autres assembleurs. Il est important que
le programme soit un TOS sinon la souris viendra salir l'cran.

	Le dbut ressemble  tous les dbuts, on rduit notre espace vital
grace  MSHRINK et on initialise notre pile.

	output "MORPION.TOS"

	text

	move.l 4(sp),a5		; basepage
	lea fin(pc),a0
	move.l a0,a7		; ma pile
	sub.l a5,a0		; taille  garder
	move.l a0,-(sp)
	move.l a5,-(sp)
	clr -(sp)
	move #$4a,-(sp)
	trap #1			; mshrink, rduit l'espace.
	add #12,sp

	Ensuite, je fais pointer a4, a5 et a6 sur mes trois tableaux. Ces
trois pointeurs ne bougeront pas de tout le programme. J'affiche le titre
et la question "Voulez vous commencer?" puis j'attends une touche. Selon
cette touche, je saute  "joueur" ou je poursuis sur "reflexion" qui est
la partie de l'ordinateur.

	lea case(pc),a4		; les trois tableaux
	lea lignes(pc),a5
	lea case_ligne(pc),a6

	pea titre(pc)		; pose aussi la question de qui commence
	move #9,-(sp)
	trap #1
	addq.l #6,sp
	move.l #$20002,-(sp)	; attend une touche
	trap #13
	addq.l #4,sp
	move d0,d4		; garde la touche
	moveq #0,d5
	bsr affiche		; premier plateau vide
	moveq #9,d7		; nombre de coups
	cmp.b #"O",d4
	beq.s joueur            ; le joueur commence
	cmp.b #"o",d4
	beq.s joueur

	D7 contient le nombre total de coups; 9 au dpart puis a diminue.
Cette valeur non plus n'est utilise par aucune des procdures suivantes,
ainsi je n'ai pas  sauvegarder ce registre.
	Aprs l'appel  "place_moi", si aucune case n'est conseille (coup
gagnant ou indcis) je choisis de jouer la premire case libre. L'appel 
"remplit_case" me signale si c'est un coup gagnant, ce qui termine la
partie prmaturment.

reflexion:
	subq #1,d7
	bmi.s termine		; c'tait le dernier coup...
	bsr place_moi		; sinon, place l'ordinateur
	move d0,d1		; valeur de retour
	bgt.s .lb0		; positif, c'est un numro de case "GAGNANT"
	bmi.s .lb1		; ngatif, code "PERDANT"
	swap d0			; sinon, "INDECIS"
	beq.s .lb1		; pas d'indecis non plus
	move d0,d1
	bra.s .lb0
.lb1:
	moveq #0,d1
	bsr prochaine_case
.lb0:
	st d0
	move d1,d5
	bsr remplit_case
	move d0,d4		; au cas ou on gagne!
	move.b #"O",d0
	bsr affiche
	tst.b d4
	bne.s je_gagne

	La partie du joueur est plus simple: on demande un appui de touche
(1  9) et on remplit la case correspondante. Aucun test de validit de la
touche n'est ralis. L'appel  "remplit_case" signale si le joueur a
gagn ce qui met galement fin  la partie. Sinon, on retourne sur la
partie "reflexion".

joueur:
	subq #1,d7
	bmi.s termine
	move.l #$20002,-(sp)
	trap #13
	addq.l #4,sp
	sub #'0',d0
	move d0,d1
	sf d0
	move d1,d5
	bsr remplit_case
	move d0,d4
	move.b #"X",d0
	bsr affiche
	tst.b d4
	beq.s reflexion

joueur_gagne:
	lea lui(pc),a0
	bra.s sortie

je_gagne:
	lea moi(pc),a0
	bra.s sortie

termine:
	lea nul(pc),a0

	La sortie affiche une chaine de conclusion (qui gagne ou partie
nulle) puis attend un appui de touche avant de revenir au bureau.

sortie:
	move.l a0,-(sp)
	move #9,-(sp)
	trap #1
	addq.l #6,sp
	move.l #$20002,-(sp)
	trap #13
	addq.l #4,sp
	clr -(sp)
	trap #1

	La procdure "place_moi" recherche la bonne position pour
l'ordinateur. Elle utilise trois registres de donnes:
D2: le numro de la case en cours d'examen.
D3: zro ou numro du dernier coup indcis.
D4: flag indiquant si au moins une place a t trouve ($FF) ou si la
partie se termine ($00)
	Comme les appels sont rcursifs, ces trois valeurs sont
systmatiquement sauves sur la pile au dbut de chaque appel.
	En sortie on obtient dans D0:
	$FFFFFFFF: tous les coups mnent  la perte de la partie.
	$00000000: fin de partie.
	$xxxx0000: coup indcis, xxxx est le numro d'une case possible.
	$0000xxxx: xxxx est le numro de la case menant  un coup gagnant.

	La structure est celle explique plus haut. Remarquez
l'utilisation de "remplit_case" afin de mettre le plateau  jour avant
d'appeler "place_joueur" pour examiner les coups de l'adversaire.
Remarquez galement l'utilisation "vide_case" pour nettoyer le plateau
lorsqu'un coup a t explor.

place_moi:
	movem.l d2-d4,-(sp)
	moveq #0,d2	; la case
	moveq #0,d3	; coup indecis
	moveq #0,d4	; si au moins une place
.encore:
	move d2,d1
	bsr prochaine_case
	move d1,d2
	beq.s .gloups	; si zero, plus de place
	st d4				; on a trouve une place!
	st d0
	bsr remplit_case
	tst.b d0
	beq.s .lb0
	st d0
	move d2,d1
	bsr vide_case
	move d2,d0
	bra.s .fin
.lb0:
	bsr place_joueur
	move d0,d5	; resultat du coup
	st d0
	move d2,d1
	bsr vide_case
	cmp #-1,d5	; est ce que l'adversaire perd?
	bne.s .lb1
	move d2,d0	; si oui c'est qu'on gagne!
	bra.s .fin
.lb1:
	cmp #0,d5
	bne.s .encore
	; *** voir AMELIORATIONS ***
	move d2,d3	; si coup indecis, on conserve la case
	bra.s .encore
.gloups:
	tst d3
	beq.s .lb2
	move d3,d0
	swap d0
	clr d0		; renvoit 0 et l'indecis au dessus
	bra.s .fin
.lb2:
	tst.b d4
	beq.s .lb3
	moveq #-1,d0
	bra.s .fin
.lb3:
	moveq #0,d0
.fin:
	movem.l (sp)+,d2-d4
	rts

	La procdure "place_joueur" est presque la meme que la prcdente.
Seules les valeurs renvoyes ont t simplifies. En effet, autant pour
l'ordinateur il me faut exactement le coup  jouer puisque c'est le
programme qui joue, autant pour l'humain dont j'inspecte les possibles
mouvements, l'information gagnant/perdant me suffit.
	On obtient alors dans D0 les valeurs suivantes:
	$FFFFFFFF: l'humain perd  tous les coups.
	$00000000: coup indcis ou fin de partie.
	$00000001: l'humain dispose d'un coup gagnant.

place_joueur:
	movem.l d2-d4,-(sp)
	moveq #0,d2	; la case
	moveq #0,d3	; coup indecis
	moveq #0,d4	; si au moins une place
.encore:
	move d2,d1
	bsr prochaine_case
	move d1,d2
	beq.s .gloups	; si zero, plus de place
	st d4				; une place au moins
	sf d0
	bsr remplit_case
	tst.b d0
	beq.s .lb0
	sf d0
	move d2,d1
	bsr vide_case
	moveq #1,d0
	bra.s .fin
.lb0:
	bsr place_moi
	move d0,d5	; resultat du coup
	sf d0
	move d2,d1
	bsr vide_case
	cmp #-1,d5	; est ce que l'adversaire perd?
	bne.s .lb1
	moveq #1,d0	; si oui c'est qu'on gagne!
	bra.s .fin
.lb1:
	cmp #0,d5
	bne.s .encore
	move d2,d3	; si coup indecis, on conserve la case
	bra.s .encore
.gloups:
	tst d3
	beq.s .lb2
	moveq #0,d0
	bra.s .fin
.lb2:
	tst.b d4
	beq.s .lb3
	moveq #-1,d0
	bra.s .fin
.lb3:
	moveq #0,d0
.fin:
	movem.l (sp)+,d2-d4
	rts

	La procdure "prochaine_case" utilise D1 en entre comme en
sortie. En entre, D1 reprsente le numro de case ou l'on est. En sortie
il reprsente le numro de la case libre suivante. La valeur 0 signifie
qu'il n'y a plus de case libre au del de la position actuelle.

prochaine_case:
	addq #1,d1
	cmp #10,d1
	beq.s .gloups
	tst.b -1(a4,d1)
	bne.s prochaine_case
	rts	; renvoit d1
.gloups:
	moveq #0,d1
	rts

	La procdure "remplit_case" se charge de placer un pion et de
modifier tous les tableaux en consquence. En entre, D0 reprsente soit
$00 soit $FF pour signaler qu'il s'agit d'un pion du joueur ou d'un pion
de l'ordinateur. D1 de son cot reprsente le numro de case  remplir.
	Le tableau "case" point par a4 est mis  jour et le tableau
"case_ligne" point par a6 nous donne le masque de bits indiquant les
alignements modifis par ce nouveau pion. On parcourt ce masque du bit7 au
bit0 et ds qu'un "1" est rencontr, on modifie l'alignement
correspondant.
	Vous remarquez que les traitements diffrent selon le joueur: pour
l'ordinateur on ajoute 1 et on vrifie si le total est 3 (coup gagnant),
pour le joueur humain on soustrait 1 et on vrifie si le total vaut -3
(coup gagnant pour l'humain).
	Dans le cas d'un coup gagnant, D0 contient $FF au retour, $00
sinon.

remplit_case:
	tst.b d0
	beq.s .joueur
	move.b #1,-1(a4,d1)	; moi dans cette case
	move.b -1(a6,d1),d1
	moveq #7,d0
.lb0:
	btst d0,d1
	beq.s .lb1
	addq.b #1,0(a5,d0)
	cmp.b #3,0(a5,d0)
	bne.s .lb1
	swap d0
	st d0
	swap d0
.lb1:
	dbf d0,.lb0
	swap d0
	rts
.joueur:
	move.b #-1,-1(a4,d1)
	move.b -1(a6,d1),d1
	moveq #7,d0
.lb2:
	btst d0,d1
	beq.s .lb3
	subq.b #1,0(a5,d0)
	cmp.b #-3,0(a5,d0)
	bne.s .lb3
	swap d0
	st d0
	swap d0
.lb3:
	dbf d0,.lb2
	swap d0
	rts

	La procdure "vide_case" est le retour en arrire de la procdure
prcdente. Les memes paramtres sont pris en entre et les calculs sont
inverss: on soustrait pour l'ordinateur et on ajoute pour le joueur
humain. Aucun test d'alignement n'est ralis (c'est pas en enlevant un
pion qu'on gagne!).

vide_case:
	clr.b -1(a4,d1)
	move.b -1(a6,d1),d1	; masque
	tst.b d0
	beq.s .joueur
	moveq #7,d0
.lb0:
	btst d0,d1
	beq.s .lb1
	subq.b #1,0(a5,d0)
.lb1:
	dbf d0,.lb0
	rts
.joueur:
	moveq #7,d0
.lb2:
	btst d0,d1
	beq.s .lb3
	addq.b #1,0(a5,d0)
.lb3:
	dbf d0,.lb2
	rts

	La procdure "affiche" place un nouveau pion et affiche le nouveau
plateau. En entre D5 reprsente le numro de la case, si il vaut 0 cela
correspond au premier affichage sans pion du dbut de partie. DO quant 
lui contient le code ASCII du caractre  afficher (X ou O).
	Remarque: chaque position est prcde de la squence "ESC q" qui
passe en vido normale. Lorsque j'ajoute un pion, je la transforme en "ESC
p" qui passe en vido inverse. Ainsi, c'est plus joli.

affiche:
	lea plateau(pc),a0
	move.l a0,-(sp)
	tst d5
	beq.s .lb0
	moveq #0,d1
	move.b .offset-1(pc,d5),d1	; offset
	move.b #'p',0(a0,d1)
	move.b d0,1(a0,d1)
.lb0:
	move #9,-(sp)
	trap #1
	addq.l #6,sp
	rts
.offset: dc.b 3,6,9,14,17,20,25,28,31
	even

	data
case_ligne: dc.b 73,10,140,17,210,20,161,34,100
titre: dc.b 27,"EMorpion",13,10
	dc.b "Voulez-vous commencer (O/N) ?",13,10,0
plateau: dc.b 27,"E",27
			dc.b "q1",27,"q2",27,"q3",13,10
			dc.b 27,"q4",27,"q5",27,"q6",13,10
			dc.b 27,"q7",27,"q8",27,"q9",27,"q",13,10,10,0
moi: dc.b "Je gagne!",0
lui: dc.b "Vous gagnez!",0
nul: dc.b "Partie nulle.",0

	even

	bss

case: ds.b 9
lignes: ds.b 8
	even
	ds.l 100
fin:

	end

Amliorations
-------------
	Elles viendront de la meilleure gestion des coups indcis. En
effet, ils ne se valent pas tous. Certains ne mnent qu' des parties
nulles alors que dans d'autres, une petite baisse d'attention du joueur
humain peut conduire  une partie gagnante. Il faudrait alors "noter"
chaque coup indcis selon les possibilits qu'il offre et choisir le
meilleur.
	Voici en deux lignes une amlioration spcifique au MORPION. On
sait que la case centrale est plus importante que les autres car c'est la
seule participant  quatre alignements. Si parmis les coups indcis, la
case 5 est possible, alors je la prfre aux autres.
	Dans la procdure "place_moi",  l'endroit marqu "voir
amliorations", ajoutez ceci:
	cmp #5,d3	; la case 5 dja possible?
	beq.s .encore	; si case centrale possible, on la prefere!
	Vous verrez que le programme n'est plus seulement dfensif mais
qu'il gagne en agressivit.

Conclusion
----------
	Je suis dsol pour les programmeurs en GFA dont je ne suis pas
spcialiste. J'ai bien essay de m'y mettre, mais je n'arrivais pas 
rcuprer mes valeurs de tableaux au sein d'une procdure ou fonction. Les
tableaux devenaient des variables locales toutes  zro... Si quelqu'un
peut m'expliquer!
	J'espre vous avoir donn envie de programmer quelques systmes
simples de rflexion et de prise de dcision. Voyez qu'il n'est pas
ncessaire de monopoliser des mgas de RAM pour que l'adversaire-machine
devienne intelligent.
	A vos bits!

	Guillaume Tello
	gtello@wanadoo.fr
