Discussion :

[snoozeur]

Bonjour,

Je suis en train de faire une IA pour le jeu awalé avec l'algo alpha beta.
L'algo fonctionne bien mais je peine sur la fonction d'évaluation.
Je tiens déjà compte de l'évolution des scores des 2 joueurs et je modifie également l'évaluation en fonction de la position des cailloux (plus ils sont à droite, plus ils ont de la valeur).
Mais je pense qu'il y a encore d'autres moyens pour l'améliorer.

Merci pour votre aide, notemment ol9245 qui m'a proposé la sienne.

[ol9245]

J'ai appris l'awale dans un petit village de la savane africaine. Il n'y avait rien a faire apres le travail. Le village etait si petit qu'il n'y avait meme pas de biere a vendre ! Je passais mon temps libre a jouer avec les instituteurs du village. Sur la base de cette experience, j'ai ecrit une fonction d'evaluation qui marche plutot bien avec un alpha-beta a 7 demi-coups seulement. Dans le temps, je savais quand meme la battre car comme souvent, elle n'est pas excelente en finale, seulement au milieu du jeu.

il y a plusieurs regles d'awale. Celle que je joue est celle des Baoules de Cote d'Ivoire. L'essentiel des regles sont les suivantes : CAMP : 4 graines par case. 6 cases par camp. chaque joueur joue une des cases contenant des graines parmi les 6 de son camp. JEU : on distribue les grains de case en case en tournant dans le sens inverse des aiguilles d'une montre. La case de depart rete vide dans tous les cas (y compris dans le cas ou il y a 12 graines ou plus dans la case jouee). PRISE : on prend quand la case d arrivee est dans le camp adverse et qu'elle contient 2 ou 3 graines apres le coup. si une case est prise, la case precedente devient case d'arrivee et peut etre prise selon la meme regle. on peut ainsi prendre jusqua 4 cases d'affilee. il est interdit de prendre 5 cases d'affilee. il est interdit de vider le camp adverse. si on est sous le coup d'une de ces interdictions, on ne prend rien.

ma fonction d'evaluation est dispo sur demande.
- en turboC des annees 90. (prevoir un peu de travail pour portage)
- je n'autorise la diffusion d'un programme contenant cette fonction qu'a la condition qu'il soit opensource.

l'awale est un jeu de strategie. il consiste a construire des blocages (bloquer les cases vides adverses) et a les tenir jusqua ce que l'adversaire, a court de choix, soit oblige de jouer un coup perdant (passer sur ces cases vides). Tenir un blocage, c'est avoir suffisament de coup d'attente pour que a la fin, l'adversaire n'ait plus d'autre choix que de traverser la case bloquée. Pour savoir si une d ces attaques tient ou ne tient pas, il faut compter le nombre de coups d'attente.

Les vrais joueurs d'awale savent à tout moment qui marche le plus et qui marche le moins. Celui qui marche moins doit défendre. Celui qui marche plus peut attaquer.

le grand secret de ma fonction d'evaluation est de compter ce qu on apelle les marches. Le nombre de marches est le nombre de coups que je peux jouer a l'interieur de mon propre camp 1) sans donner de graine a l'adversaire 2) sans passer par une de MES cases vides bloquee par l'adversaire 3) sans détruire la ase attaquante. Le nombre de marches correspond au nombre de coups d'attente.

Pour chaque case d'attaque, je regarde d'abord si cette case d'attaque a plus de marche que l'adversaie n'en a en défense. Si c'est le cas, je comptabilise le nombre de graines que j'espere capturer si l'adversaire n'arrive pas à contrecarer l'attaque et je compte ces graines au même titre que le gain matériel déja acquis.

Bonne chance, OL

[ol9245]

Voila le code complet avec les executables.
Borland Turbo C++ ecrit en 1992. Awale.zip donc pas mal de travail pour recompiler sur un compilo moderne.

Toute utilisation ou transcription complete ou partielle de ce code doit respecter les normes opensource dont en particulier être distribué avec le code source et la mention des divers contributeurs.

awale.exe joue avec des paramètres par défaut. profondeur de réflexion = 4 coups. (30 secondes de calcul il y a 15 ans, moins d'une seconde aujourd'hui)
awaleinter.exe permet de choisir la profondeur de l'alpha-beta (ca passe jusqu'à 8-10 coups d'avance). Il faut aussi entrer les paramètres d'élagage de l'arbre. alpha=350, elagage=600 marche bien.

tout retour d'experience sera très apprécié.
OL

[snoozeur]

Merci beaucoup, je vais regarder tout ça.

[ol9245]

Bonne chance.

je reviens sur un détail de ton premier post :

je modifie également l'évaluation en fonction de la position des cailloux (plus ils sont à droite, plus ils ont de la valeur).

A mon humble avis, c'est pas la solution.
1/ la position des graines n'a pas d'importance en soi. ce qui est important, c'est de contrôler les cases vides du camp adverse.
2/ j'ai essayé de multiples pondérations quand j'ai programmé ma fonction d'évaluation mais aucune n'a marché. ma fontion d'évaluation ne tiens compte que du gain matériel.
gain matériel déja acquis = pondétration 100%
gain matériel certain (l'adversaire ne peut pas y échaper) = 100%
gain matériel probable = pondération 90%

le gain matériel probable, c'est le gain que l fonction d'évaluation considère comme certain d'après le calcul des coups d'attente de chaque joueur. Comme ce calcul est simplifié par rapport à l'expertise humaine, il a des failles et donc l'ordi doit préférer les prises absolument certaines aux prises "certaines selon la fonction d'évaluation".

L'absence total d'autre heuristique dans ma fonction d'évaluation fait que mon programme ne sait pas construire sur le très long terme. faire un tas sur la droite par exemple. C'est une stratégie de base, mais je n'ai pas réussi à la lui apprendre. dès que je veux l'inciter à faire des tas, il en fait à tort et à travers.

OL

[ChriGoLioNaDor]

J'arrive un peu après la guerre, mais je suis aussi entrain de m'intéresser à ce genre d'algo.

Tu dis avoir des soucis pour faire une IA ayant une stratégie "assez poussée" (j'entend par là qui va plus loin que "ce coup là me permet de remporter le maxumum de graines", ou "si je joue ça, le prochain tour je suis certain de lui en piquer tant").

Ne serait-il pas envisageable, simplement, de compter, pour chaque cas, le nombre de graines gagnées/perdues, et ce pour x coups.
Tu pourrais obtenir x tableaux (un par coup), qui t'indiquerait combien tu gagnerais et perdrais de graines pour chaque coup que tu joues, selon la réponse de l'adversaire. Après tu pourrais faire une moyenne des gains et pertes réalisées pour chaque coup. Et choisir celui qui a le meilleur potentiel (soit celui qui rapporte le plus en moyenne, celui qui te coute le moins de graine, ou le meilleur rapport gain/perte, selon le style de jeu que tu veux lui donner).

Pour imager, j'aurais cela :
coup1 {-1,-1,-1,-1,3,0}; 2 coups possibles (les -1 indiquent les coups impossibles car pas de graine dans la case): le premier, tu gagnes 3 graines, le second, tu n'en gagnes pas)
coup5-1 {-1,-1,-1,3,6,-1}; dans le premier cas, l'adversaire pourra jouer 2 coups aussi, mais dans tous les cas il te piquera 3 graines minimum, et peut être 6.
coup6-1 {-1,-1,-1,0,0,0}; dans ce deuxième cas, quel que soit ce que jouera l'adversaire, il ne pourra pas te prendre de graine.
etc etc.

On obtient donc, pour le premier coup possible : 3-(3+6)/2=-1.5 de moyenne, et pour le second, 0+(0+0+0)/3=0. On peux donc facilement en déduire qu'il faut mieux ne pas prendre les 3 graines, car je risque de m'en faire prendre plus. Avec ce genre d'étude, sur déjà 4 ou 5 coups, on pourrait avoir de sacrées possibilités (du genre : je me fais prendre 3 graines maintenant, mais je sais que, d'ici 4 tours, je pourrais les récupérer car ce coup va me permettre d'exploiter une faille dans sa défense).

De plus, on peux facilement créer des niveaux de difficulté, selon le nombre de coup étudié : niveau 1, l'ordi prend les graines dès qu'il le peux, et vérifie s'il est soumis à une menace directe (s'il ne joue pas ça, tu lui piques 5 graines le coup suivant); niveau 2, il étudie les impacts de ses coups en fonction de ce que l'adversaire pourra lui faire à son tour; niveau 3, il commence à voir à long terme, pour contrer les attaques qui pourraient se préparer, ...

Cela te semble-t'il réalisable?