Othello et fonction d'évaluation

Question

Salut à tous

Dans le cadre de mes études, je fais un peu mumuse avec le jeu othello. J'ai implémenté un joueur, avec un algorithme de recherche de type Negascout. Mon problème, maintenant, c'est la fonction d'évaluation des coups. Je veux dire par là que j'ai beau avoir une fonction de recherche potable, tant que l'évaluation est merdique ça me fera pas avancer pour autant.
Je me suis un peu renseigné au sujet des possibles tactiques de jeu, et le bétonnage m'intéresse bien. Pour l'instant j'ai déjà une fonction qui donne une bonne note aux pièces dites protégées, et j'ai plusieurs tables de valeurs qui varient selon la période de jeu, mais mon joueur est encore très frileux quand on lui parle des cases X et C ( ils les évitent le coquin :-)), et cela est très paralysant pendant certaines phases de jeu, notamment quand le joueur adverse peut ainsi protéger sa ligne, malgré que mon joueur possède les deux coins !
D'autre part la complexité est d'ordre O(n^2), ce qui est très gourmand en temps. Est-ce qu'il existe un algorithme de recherche fonctionnant à moindres frais ? ( Je me suis demandé si je pouvais imaginer un mergesort pour un cas comme celui-ci... ).
Ouais enfin bon, je recherche des idées, car là je suis tout malheureux, je vais pleurer. Allez soyez sympas, quoi ! :-)

Mes questions :
Comment implémenter le bétonnage ?
Comment rendre ma fonction d'évaluation moins gourmande ?

Merci à tous 
Gouigoui

wargre · Answer

de toutes facon Negascout ou alpha-beta c'est tjs la meme chose!

pour l'evaluation:
au debut du jeu => noté de facon forte les piece sur les coté
a la fin du jeu => calcul sur le nombre de piece obtenue.

pour l'algo de recherche tu trouvera pas beaucoup mieux (sauf si tu as un dictionnaire de coup) 

Pour reduire le temps de calcul, il faur reduire la profondeur 

voila j'ai simplement mis ce petit mot pour que tu ne suicides pas tout de suite.

Asrull · Answer

Toi aussi tu bosses sur un othello ? cool.
j'en suis pas encore à l'ia, en gros j'en suis aux balbutiements d'un simple resolver pour traduire les règles du jeu et sur les animations pour retourner un pion. sinon pour la strategie je suis d'accord avec wargre mais en un peut plus fin:

- début de partie placement de pièce fortes,
- dès que tu possède plus de pièces fortes que le joueur humain tu essayes de lui taxer ses pièces fortes (si ya pas moyen tu essayes de placer une pièce forte et si ya pas moyen de faire ça tu lui bouffe des pions)
- dans tous les cas passé la 45 pièce jouée, protéger ses pièces forte chercher un maximum de points
-à la 55 pièce jouée, il ne faut plus que chercher des points

sinon, je suis en galère sur mon resolver. j'arrive pas à trouver une méthode simple et rapide pour déterminer si un joueur a le droit de jouer à une certaine position... et vu que je veux faire changer la tête du pointeur de la souris en fonction de ce pauvre boolean à la c.. ya plutôt intérêt à ce que la méthode soit rapide... si t'as un tuyeau je suis preneur.

Oobaï TaPou !

Asrull · Answer

hu j'ai oublié un truc

il faut systématiquement chercher s'il existe pas un coup qui oblige l'autre à passer son tour ou alors qui ne lui donne qu'une seule position à jouer. Ca se produit de temps en temps et ça fait trés mal. il faut aussi revoir tes propres coup en fonction de ses deux paramètres mais dans le sens inverse. C'est le genre de truc qui fait trés (trés) mal dans ce jeu.

Oobaï TaPou !

cs_GodConan · Answer

GodConan :clown) 

ben si tu veu changer ton curseur rapidement ... il te suffit de calculer les case jouable a l avance ( ca prend pas temp de temp ) et de placer un boolean ( par exemple ) pour chac case jouable tu peu pas faire plus rapide ensuite pour faire reagir ton curseur... ;o)

++

Asrull · Answer

Bourrin, franc et massif, j'adore tes méthodes GodConan.
ouaip je crois bien que je vais faire comme ça. Le plus stupide c'est qu'en regardant l'organisation de mes classes c'est tout simplement la meilleure méthode. C'est peut être parce que je suis lâche sournois et vicieux que je n'y ai pas pensé moi même.

Oobaï TaPou !

wargre · Answer

Pour othello je connais parceque c'est un truc clasique que les profs font faire a tout leur eleve :)   

ca implique que on devait faire une IA seulement correcte (pas nule et pas au top)

Asrull · Answer

...

ben j'aurais bien voulu faire un othello en cours d'autant plus que je suis un gros mordu de ce jeu (me souviens pas m'être incliné d'ailleurs) ... nan au lieu de ça moi j'ai eu droit à un magnifique puissance 4 avec pour seul intérêt qu'il était jouable en réseau avec un serveur qui gérait le classement des joueurs ... J'AIME PAS LES APPLETS MOI !
Oobaï TaPou !

gouigoui · Answer

Merci les gars, je vais réfléchir à tous cela.

Je voulais juste encore savoir si vous connaissiez une fonction d'évaluation, qui évite à mon reversi de péter les plombs et de finir en millieux de partie, si je ne mets pas une fonction qui le stoppe, avec une profondeur de 11, avec un joyeux "timeout, time exceeded !" ( un truc dans le genre) Faut dire qu'il a que 5 secondes le pauvre !

wargre · Answer

le truc normal a faire c'est profondeur 1. Si encore du temps, trie et calcul profondeur 2 en commencant par les coups de niveau 1 les plus avantageux etc etc. bref tu t'arretes au timeout. la profondeur n'est alors pas fixe.

cs_GodConan · Answer

GodConan :clown) 

autrement ;o) sur le site y a pas mal de sample de othello je pense ;o)
enfin au moin 1 le mien ;o) hihi un tres vieu prog que g fait qd j etait petit il ne reste plus qu a y implenter les IA 
;o) 
mes premier jeu etai en java 1.1 ;o) mais bon ca peu donne une idee ;o)... pour les amateur...
++

Othello et fonction d'évaluation

10 réponses

Votre réponse

Discussions similaires