J'ai mis provisoirement le jeu de navigation sous le coude pour ressortir un Mancala que j'avais adapté en Forth pour le ZX81.
Dans les années 80 l'étude de l'Intelligence Artificielle passait inévitablement par l’algorithme MiniMax avec élagage.
http://www.emse.fr/~picard/files/minimax.pdf
L'étude systématique passe par la sauvegarde provisoire de l'état du plateau de jeu et postérieure récupération.
Suivant la profondeur d'analyse la quantité de tableau à mettre en sauvegarde croit rapidement.
Forth s'adapte particulièrement bien à cette manip grâce à sa pile de données -Voir les PUSH et POP du programme.
C'est une version V1 (c'est à dire le moteur principal) auquel il manque encore l'habillage graphique.
COMMENT JOUER
-------------
Vous êtes devant votre plateau de jeu, 6 coupelles devant vous contenant 4 pierres chacune.
La coupelle à votre gauche est la n° 1 la dernière à droite la n° 6.
Idem pour l'ordinateur qui a ses propres coupelles.
A tour de rôle, chaqu'un prendra toutes les pierres dans une de ses coupelles et les sèmera dans les autres coupelles, une par une, dans le sens inverse des aiguilles
d'une montre. Suivant le nombre de pierres, on en mettra donc dans les coupelles adverses.
Si la dernière pierre tombe dans une coupelle qui avait une ou deux pierres, on remporte le gain de la coupelle + cette dernière pierre.
Si la coupelle qui précédait possédait également 1 ou 2 pierres, on les
gagnera également. Et ainsi de suite.
**********************************************
MANCALA - Dominique Contant - Juillet 2013
**********************************************
UTILITAIRES :
------------
Émulateur Dcmoto2013.03.10 de Daniel Coulom
http://dcmoto.free.fr/emulateur/index.html
Compilateur Forth
http://dcmoto.free.fr/programmes/forth-mo5/index.html
Installer FORTH depuis la K7 : FORTH-MO5-MO5.K7
Depuis le Forth installer l’éditeur.
Charger la K7 mancalav1
Depuis le Forth : 1 9 CLOAD MANCA
Une fois chargé, compiler le programme par
1 LOAD
------------------------------------
Code : Tout sélectionner
: TASK ;
HEX
// Routine habituelle de l'ami _sam_, elimine le curseur
CREATE DI 1A50 , 0EB6 , SMUDGE
CREATE EI 1CAF , 0EB6 , SMUDGE
DECIMAL
// quelques définitions utiles
: NOT 0= ;
: 0<> 0= NOT ;
: 0SET 0 SWAP ! ;
// redéfinition de variable (c est plus court)
: VAR 0 VARIABLE ;
//Saisie au clavier : N(UMBER) IN
: NIN 0 48 ." ?" BEGIN 48 - SWAP 10 * + KEY DUP 13 = UNTIL DROP DUP . ;
//mot de définition des array
: DIM <BUILDS 2 * 2 + ALLOT DOES> SWAP 2 * + ;
// array Board Stack - état actuel du jeu
26 DIM B-STA
/Donne adresse début des mouvements à l'intérieur du stack
: M-STA 2 * 0 B-STA 28 + + ;
// définition de différentes adresses dans le stack comme constantes
/ Best Player Value
24 B-STA CONSTANT B-P-V
/Best Computer Value
23 B-STA CONSTANT B-C-V
/Profondeur Analyse
22 B-STA CONSTANT DEPTH
/Meilleur coup
25 B-STA CONSTANT BEST-MOVE
/Number of Possible Move
14 B-STA CONSTANT N-P-M
/Compteur de mouvement
21 B-STA CONSTANT MOVE-COUNT
VAR MAX-DEPTH
VAR MOVE-TO-DO
VAR HOUSE
VAR PTS
/Board Stack Pointer
VAR B-STA-PTR
VAR HAND
/Valeur temporaire
VAR TMP-VA
/variable alignement tableau
12 VARIABLE REF
/ Mini CLS
: CL-TXT 0 0 LOCATE 60 0 DO BL EMIT LOOP 0 0 LOCATE ;
/Les différents messages
: MSG-COMP-W CL-TXT ." J'AI GAGNE " ;
: MSG-PLAY-W CL-TXT ." VOUS AVEZ GAGNE " ;
: MSG-NULL CL-TXT ." MATCH NUL " ;
: MSG-C-N-M CL-TXT ." JE N'AI AUCUN COUP " ;
: MSG-P-N-M CL-TXT ." VOUS N'AVEZ AUCUN COUP " ;
: MSG-ANALYSE CL-TXT ." J'ANALYSE.. " ;
: MSG-COMP-MOVE CL-TXT ." JE JOUE :" ;
: MSG-PLAY-MOVE CL-TXT ." FAITES VOTRE CHOIX ( 1 A 6)" ;
: MSG-DEPTH CL-TXT ." NIVEAU DE DIFFICULTE " ;
: MSG-FIRST-PLAY CL-TXT ." VOULEZ VOUS COMMENCER ? (O/N) " ;
: MSG-?AGAIN CL-TXT ." VOULEZ VOUS JOUER A NOUVEAU ? (O/N) " ;
: MSG-KEY 1 0 LOCATE ." TAPEZ UNE TOUCHE" KEY DROP ;
: MSG-BOARD1 LOCATE ." * * M A N C A L A * *" ;
: MSG-BOARD2 LOCATE ." PTS" ; : MSG-BOARD3 LOCATE ." JOUEUR" ;
: MSG-BOARD4 LOCATE ." ORDINATEUR" ;
/Impression du tableau
: PRINT-BOX REF @ 0 DO 31 0 DO OVER OVER I + LOCATE 42 EMIT LOOP SWAP 1+ SWAP LOOP ;
: PRINT-ONE-HOUSE 3 0 DO 3 0 DO OVER OVER I + LOCATE BL EMIT LOOP SWAP 1+ SWAP LOOP ;
: PRINT-HOUSE 7 1 DO PRINT-ONE-HOUSE SWAP 3 - SWAP 4 + LOOP DROP DROP ;
: PRINT-TXT REF @ DUP 2 + 2 MSG-BOARD2 DUP 2 + 8 MSG-BOARD1 DUP 5 - 2 MSG-BOARD3 9 + 2 MSG-BOARD4 ;
: PRINT-BOARD CLS 8 0 PRINT-BOX SWAP 10 - SWAP 7 + PRINT-HOUSE REF @ 4 + 7 PRINT-HOUSE PRINT-TXT ;
: PRINT-FIGURE 1 - LOCATE DUP 10 < IF BL EMIT ENDIF . ;
: PRINT-STONE 13 B-STA @ REF @ 1 - 3 PRINT-FIGURE 0 B-STA @ REF @ 5 + 3 PRINT-FIGURE 7 1 DO 13 I - B-STA @ REF @ 1 - I 4 * 4 + PRINT-FIGURE I B-STA @ REF @ 5 + I 4 * 4 + PRINT-FIGURE LOOP ;
: ASK-FIRST-PLAY MSG-FIRST-PLAY KEY ;
: ASK-DEPTH MSG-DEPTH NIN MAX-DEPTH ! ;
/Verifie si le choix est cohérent - House non vide et House entre 1 et 6
: LEGAL-MOVE 13 OVER > OVER 6 > AND SWAP B-STA @ 0<> AND ;
: ASK-PLAY-MOVE BEGIN MSG-PLAY-MOVE NIN 6 + DUP MOVE-TO-DO ! LEGAL-MOVE UNTIL ;
/Met dans le Board Stack tous les mouvements possibles
: POSS-MOVE N-P-M 0SET HOUSE @ DUP 6 + SWAP DO I B-STA @ 0<> IF 1 N-P-M +! I N-P-M @ M-STA ! ENDIF LOOP ;
: INIT-STONE 0 0 B-STA ! 0 13 B-STA ! 13 1 DO 4 I B-STA ! LOOP ;
: ?NUMB-MOVE N-P-M @ ;
: PRT-COMP-MOVE MSG-COMP-MOVE BEST-MOVE @ DUP . MOVE-TO-DO ! ;
: GET-PLAY-MOVE 7 HOUSE ! POSS-MOVE ;
: GET-COMP-MOVE 1 HOUSE ! POSS-MOVE ;
: FIX-WIN 0 B-STA @ 13 B-STA @ OVER OVER > IF MSG-COMP-W ELSE OVER OVER < IF MSG-PLAY-W ELSE MSG-NULL ENDIF ENDIF DROP DROP ;
: COMP-BOARD-SCORE 0 B-STA @ 13 B-STA @ - TMP-VA ! ;
: PLAY-BOARD-SCORE 13 B-STA @ 0 B-STA @ - TMP-VA ! ;
: THIS-HOUSE B-STA-PTR @ B-STA ;
: ?SCORE-HOUSE THIS-HOUSE @ DUP 1 > SWAP 4 < AND ;
: PRECED-HOUSE B-STA-PTR -1 OVER +! DUP @ 1 < IF 12 OVER ! ENDIF DROP ;
: NEXT-HOUSE B-STA-PTR 1 OVER +! DUP @ 12 > IF 1 OVER ! ENDIF DROP ;
: SCORE-MOVE BEGIN ?SCORE-HOUSE WHILE THIS-HOUSE DUP @ PTS @ B-STA +! 0SET PRECED-HOUSE REPEAT ;
: INIT-MAXIMIZ 999 B-P-V ! -999 B-C-V ! DEPTH 0SET ;
: DO-MOVE MOVE-TO-DO @ DUP B-STA-PTR ! B-STA DUP @ HAND ! 0SET BEGIN HAND @ 0<> WHILE NEXT-HOUSE 1 THIS-HOUSE +! -1 HAND +! REPEAT SCORE-MOVE ;
: PLAY-MOVE 13 PTS ! DO-MOVE ;
: COMP-MOVE PTS 0SET DO-MOVE ;
/Sauvegarde et récupération du tableau et paramètres
: PUSH-PARAM MOVE-COUNT @ DEPTH @ B-C-V @ B-P-V @ BEST-MOVE @ ;
: PUSH-HOUSE 14 0 DO I B-STA @ LOOP ;
: PUSH-M-STA N-P-M @ 1+ 1 DO I M-STA @ LOOP N-P-M @ ;
: PUSH-BOARD PUSH-PARAM PUSH-HOUSE PUSH-M-STA ;
: POP-M-STA DUP N-P-M ! 1+ DUP 1 DO I OVER SWAP - M-STA SWAP >R ! R> LOOP DROP ;
: POP-HOUSE 14 0 DO 13 I - B-STA ! LOOP ;
: POP-PARAM BEST-MOVE ! B-P-V ! B-C-V ! DEPTH ! MOVE-COUNT ! ;
: POP-BOARD POP-M-STA POP-HOUSE POP-PARAM ;
: (LEAVE) N-P-M @ MOVE-COUNT ! ;
/Mini doit appeler maxi, or maxi n'existe pas encore. créons un faux maximiz
: (MAXIMIZ) CR ;
: LOOP-MIN MOVE-COUNT 0SET BEGIN 1 MOVE-COUNT +! B-P-V @ B-C-V @ > NOT IF (LEAVE) ELSE PUSH-BOARD 1 DEPTH +! MOVE-COUNT @ M-STA @ MOVE-TO-DO ! PLAY-MOVE (MAXIMIZ) POP-BOARD B-P-V @ TMP-VA @ > IF TMP-VA @ B-P-V ! MOVE-COUNT @ M-STA @ BEST-MOVE ! ENDIF ENDIF N-P-M @ MOVE-COUNT @ = UNTIL ;
: ?MAX-DEPTH DEPTH @ MAX-DEPTH @ = ;
: MINIMIZ ?MAX-DEPTH IF COMP-BOARD-SCORE ELSE GET-PLAY-MOVE ?NUMB-MOVE 0= IF COMP-BOARD-SCORE ELSE 999 B-P-V ! LOOP-MIN B-P-V @ TMP-VA ! ENDIF ENDIF ;
: LOOP-MAXIM MOVE-COUNT 0SET BEGIN 1 MOVE-COUNT +! B-C-V @ B-P-V @ < NOT IF (LEAVE) ELSE PUSH-BOARD 1 DEPTH +! MOVE-COUNT @ M-STA @ MOVE-TO-DO ! COMP-MOVE MINIMIZ POP-BOARD TMP-VA @ B-C-V @ > IF TMP-VA @ B-C-V ! MOVE-COUNT @ M-STA @ BEST-MOVE ! ENDIF ENDIF N-P-M @ MOVE-COUNT @ = UNTIL ;
: MAXIMIZ ?MAX-DEPTH IF COMP-BOARD-SCORE ELSE GET-COMP-MOVE ?NUMB-MOVE 0= IF COMP-BOARD-SCORE ELSE -999 B-C-V ! LOOP-MAXIM B-C-V @ TMP-VA ! ENDIF ENDIF ;
: ?END-GAME 0 B-STA @ 13 B-STA @ + 46 > ;
: (PROGRAM-LOOP) BEGIN MSG-ANALYSE GET-COMP-MOVE N-P-M @ 0= IF MSG-C-N-M ELSE INIT-MAXIMIZ MAXIMIZ PRT-COMP-MOVE MSG-KEY COMP-MOVE PRINT-STONE ENDIF GET-PLAY-MOVE N-P-M @ 0= IF MSG-P-N-M ELSE ASK-PLAY-MOVE PLAY-MOVE PRINT-STONE ENDIF ?END-GAME UNTIL ;
/ On met dans (MAXIMIZ) l'adresse de MAXIMIZ et le tour est joué
' MAXIMIZ 2 - ' (MAXIMIZ) !
: MANCALA DI BEGIN INIT-STONE PRINT-BOARD PRINT-STONE ASK-DEPTH ASK-FIRST-PLAY 79 = IF ASK-PLAY-MOVE PLAY-MOVE PRINT-STONE ENDIF (PROGRAM-LOOP) FIX-WIN KEY DROP MSG-?AGAIN KEY 79 = NOT UNTIL EI ;