# [OFF] Projet : IA pour le jeu de go

## Trevoke

Pour l'instant, je rassemble des liens..

http://trevoke.ath.cx/Go_bot_project.html

Si vous voulez savoir a quoi ressemble le jeu de go : http://trevoke.ath.cx/go/

Je voudrais cependant savoir s'il y a des personnes qui seraient interessees par ce projet. Je sais que, tout seul, je ne ferai absolument rien -- trop de boulot, pas assez de temps. S'il y a une equipe et qu'on fait tous de la recherche, la communication directe est beaucoup plus sympa et apte a faire naitre des idees...

Je ne sais pas quoi dire pour vendre le principe, si ce n'est que le jeu de go est le probleme d'IA le plus fascinant qui soit (la meilleure IA, en ce moment, est facilement battue par un joueur humain qui a ~1 an d'experience), et que le jeu lui-meme merite le detour.

----------

## Enlight

Moi aussi je manque de temps alors :

1) les règles sont vite apprises?

2) tu comptes coder en quoi?

----------

## Trevoke

Les regles du jeu de go? Il y en a, quoi, 5? Un enfant de 6 ans peut les apprendre.

La complexite du jeu de go? Cosmique.

Les regles du jeu de go sont simple.

1) Deux joueurs, un avec les pierres blanches, un avec les pierres noires. Noir commence, et pour compenser, blanc obtient en general quelques points a la fin de la partie (komi).

2) Chaque joueur pose une pierre a son tour sur une intersection du plateau de jeu (goban). Le rhythme du jeu ne change jamais.

3) Le but du jeu est de controler le plus de territoire possible.

4) Il est possible de capturer les pierres de l'adversaire si elles n'ont plus de libertes. Si une pierre est posee sur le plateau, elle aura 4 liberets (les 4 lignes s'etendant de l'intersection). Sur le cote, 3 libertes, dans un coin, 2 libertes. Si plusieurs pierres sont ensemble, les libertes s'ajoutent (un groupe de deux pierres aura donc 6 libertes, etc etc).

5) Une situation speciale est le ko, qui arrive quand les adversaires peuvent chacun capturer une pierre de l'adversaire (exemple). La regle specifie que l'on ne peut pas faire un mouvement de facon a repeter la position sur le tableau juste avant que l'adversaire ne joue.

Ensuite, il y a beaucoup de subtilites, on y viendra.

Quelle langage je compte utiliser? Aucune idee. Peut-etre C++; je pense que ca dependra de ce qu'on ressort de la recherche, ou alors ca dependra des gens qui sont interesses et de leurs connaissances  :Smile: 

----------

## bong

 *Trevoke wrote:*   

> Quelle langage je compte utiliser? Aucune idee. Peut-etre C++

 

Prolog plutot...

----------

## Trevoke

Je veux bien me taper tout le site sur GNU Prolog, mais tu peux m'expliquer en trois phrases pourquoi c'est une meilleure idee?

----------

## bong

Disons que je ne faisais que mettre sur la voie.

Je ne suis pas un spécialiste de prolog (j'ai pas pris PL/IA en module optionnel cette année   :Very Happy:  ) mais C++ est un langage procédural et cela implique que pour une ia correcte, il faudrait mettre en oeuvre des algorithmes iteratifs plutot lourds.

Avec prolog, tu enonce des predicats (regles que tu connais comme prouvee) et par combinaison de ces predicats te dit si tes propositions sont vraies ou fausses... j'en dirai pas plus pour ne pas risquer de dire des betises..

Allez, deux petits liens pour voir un peu le concept:

http://fr.wikipedia.org/wiki/Prolog

http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/intro.html

----------

## Leander256

Je ne pense pas que le choix de Prolog soit une bonne idée. Il pourrait par exemple aider à déterminer si un coup est valide, mais il ne permettrait pas de calculer la pertinence de celui-ci. Je ne crois pas qu'il soit même capable de gérer correctement la règle 5 énoncée par Trevoke, parce qu'il faudrait pouvoir sauvegarder l'état du plateau de jeu après chaque mouvement pour pouvoir faire une comparaison. Enfin ça ce sont des réminiscences de mes cours d'IA de l'année dernière, peut-être ai-je tort.

Et en ce qui concerne le projet en lui-même, bonne chance  :Wink: 

----------

## papedre

Hum, hum, 

Faire une IA de jeu de go me semble un problème un peu trop compliqué. En effet, comme tu l'as dis, les programmes qui existent ont un niveau assez déplorable. Enfin, jusqu'a ~10 kyu, tu cela est largement suffisant.

L'IA du go est très compliqué car le Goban est grand (19*19), et tu ne déplace pas les piéces (ce qui limite le nombre de combinaison), mais tu peux jouer sur n'importe quelle case libre. 

Ensuite, les bases du jeu se font sur des notions assez abstraites. Ce sont des questions de territoires (pas fermé en plus), et de zones d'influences. Tu as déjà du avoir le problème en jouant, des fois, tu VOIS un point faible, un coup à jouer, mais tu n'est pas capable de prouver pourquoi.

Enfin, les points suivants sont très important : 

  - le Fuseki (debut de partie), pendant lequel on peux quasiment jouer sur tous le plateau, et pendant lequel on divise ces territoires et créer ces zones d'influences (je pense que cette partie la doit etre très dur pour une IA).

  - Les notions de Vie et de Mort (la présence de Vrai et Faux Oeil).

  - Les séquences de coins. 

En plus, pourquoi réinventer la roue, alors que ca existe déjà en libre. Il y a le projet suivant qui fonctionne très bien : http://www.gnu.org/software/gnugo/gnugo.html

Cependant, j'incite tous ceux qui ne connaissent pas ce jeu à aller faire un tour. C'est un jeu passionnant, simple, avec un systeme de handicap qui permet à des personnes de différents niveaux de jouer ensemble. De plus, ce jeu est très influencé par la philosophie asiatique. En effet, le but n'est pas de détruire l'adversaire. Il faut savoir ceder pour ne pas rompre ...etc

A+

PS : j'ai trouvé ca aussi, mais je n'ai pas encore essayé. http://www.hikarunix.org/

----------

## Trevoke

papedre, si tu vas voir mon site, j'ai un forum avec une section go, et j'ai mis un lien vers hikarunix. Je l'ai essaye et il est vraiment tres sympa  :Smile: 

Ceci dit.. Mes idees en ce moment.

Fuseki : dans un premier temps, on peut se limiter a imiter le comportement d'un humain, c'est-a-dire qu'il y a peut-etre 8 ou 9 intersections qui sont une bonne idee au debut : aux environs directs de 4-4. d'un cote ou l'autre du tableau. On pourra rafiner apres (attaque directe, commencer par le milieu, tout un tas de trucs pas commun).

Vie et Mort : la c'est un peu plus complique, mais un vrai oeil est un oeil qu'on ne peut envahir qu'apres avoir encercle le reste du groupe; et je pense qu'avec une petite addition, on peut verifier la presence d'au moins deux yeux (pas la peine de verifier plus).

Sequences de coins : joseki, par exemple, tu veux dire? En effet, c'est deja un peu complique ici; une regle de 'compromis' est peut-etre une bonne idee, mais il faut voir comment implementer ca. Ou alors on peut juste faire un systeme d'IA qui apprend; et ensuite on lui montre les sequences standards.

Je connais Gnugo, mais comme tu as explique toi-meme au debut de ton poste, c'est pas la roue, puisqu'il est ~10k  :Smile: 

[edit : sinon, est-ce qu'il serait possible de melanger prolog et C++ / D ? Utiliser la puissance de Prolog et ensuite verifier avec C++ par exemple.. ? Enfin, je vais lire pour voir ce que Prolog offre  :Smile:  ]

----------

## kwenspc

C'est un problème "hard" l'IA d'un jeux de go. 

En tout cas c'est le truc du moment chez les chercheurs (dans les fac ça devient un classique)

Renseignes sur le mfgo de Davic Fotland. Il a gagné le concours sur ce type d'ia en 2002

(et y a moyen de glaner des infos sur le moteur, quelques indices quoi)

Sinon de la doc sur "Les jeux de Conway", c'est la base pour les jeux. 

Je ne connais pas le problème mais j'imagine que ce type d'IA ne peut se suffir d'un algo min-max amélioré (qui est généralement l'algo le plus prisé sur les petits problèmes à propos des jeux).

----------

## Trevoke

Non, je pense qu'il faut vraiment donner a l'AI une comprehension de base du territoire et de l'influence, du pouvoir d'une pierre...

Exemple : http://canut-ki-in.jeudego.org/simulation_influence/

Ca devrait vous interesser!

Je pense en ce moment essayer de creer une AI qui puisse apprendre; c'est-a-dire qu'elle ne sera pas limitee par mes talents (sauf en programmation...).

----------

## Tsukusa

C'est vrai que c'est compliqué. En tout cas le Prolog exige bien plsu qu'une connaissance en programmation. C'est vraiment de la logique pure et dure. Je ne connais pas beaucoup de chose en IA mise à part quelques bases que j'ai pu lire à droite à gauche mais en tout cas la solution d'une IA qui évolue au cours de ses parties semble la meilleure solution dans le cas du go. 

Enfin celui qui arrive à modéliser une partie entière de go et à en démontrer les mécanismes, bravo :p

J'ai toujours voulu me lancer dans un projet de la sorte sans en prendre le temps. Je ne suis pas non plus super fort pour le moment :/ (que ce soit en go ou en programmation :p). Mais si jamais je peux servir et que je change mes habitudes de fainéants ...   :Rolling Eyes: 

----------

## kwenspc

...faire un algo qui s'améliore partie après partie?

rêvez pas trop hein  :Wink: 

Je dis pas que c'est impossible mais c'est quelque chose de trés compliqué. Une "solution simple" serait une mémoire d'état. dans une bdd tu sauves des états particuliers (les meilleurs états ceux que l'IA n'arrive jamais à "gagner", genre elle a plein de point et après un coup de son adversaire, paf elle perd pas mal. et y a d'autres cas possibles j'imagine dans le go qui puisse déclencher un mecanisme de mémorisation d'état). Ensuite il faut, dans les parties suivantes, qu'elle sache parcourir ses états de manières "intelligentes" c-a-d dire trouver les états qui sont le plus proches de l'état courant. etc...

Après bonjour la lenteur de l'algo... ça ve vitre être exponentiel. 

Une autre solution serait un système expert avec une base de règles qui, à partir du déclenchement de certaines règles, saurait en créer d'autres.

Ce qui est bien c'est que vous pouvez éviter de coder la partie systèmes expert (il y en a de trés bons et opensource donc ça va - genre CLIPS - , parce que là encore c'est coton à coder), mais vous aurez forcément à coder la base de règles... pareil : ça peut trés vite être compliqué, et pour peu que vous ayez des manques dedans vous vous retrouverez avec un truc bancale et sans doute nul sur la plupart des parties   :Confused: 

euh sinon pour le prolog je sais que ça peut être une solution mais alors bonjour la maîtrise du langage et de la logique mathématique derrière. Il faut plusieurs années de pratiques pour être à l'aise avec ce machin.

----------

## Trevoke

Toute aide est la bienvenue, meme s'il ne s'agit que d'idees!

Ceci dit, avec ce thread vous savez ou est mon site, donc c'est pas trop dur de me contacter..  :Smile: 

----------

## Tsukusa

Disons que le Prolog nécessite une forte maîtrise de logique formelle (la base), logique modal, logique temporelle et j'en passe. Mais même avec tout ça, le jeu de go reste très difficile à modéliser en Prolog. Mais je peux demander à quelques connaissances qui s'y connaissent en IA de me dire si le Prolog peut être un bon choix ou trouver les "idées" qui peuvent marcher.

Sinon pour ce qui est de l'évolution de l'IA le parcours d'état était plus ou moins ce que je sous-entendais. Ou alors un système de réseaux neuronnaux mais je ne connais pas suffisament leurs fonctionnements actuellement pour savoir si c'est faisable (ceci dit là aussi je peux toujours me renseigner).

----------

## Trevoke

http://canut-ki-in.jeudego.org/simulation_influence/

Ca a l'air assez interessant aussi.

Et puis oui, savoir quel langage est le plus optimal, c'est une bonne idee  :Smile: 

----------

## PabOu

 *Trevoke wrote:*   

> Si vous voulez savoir a quoi ressemble le jeu de go : http://trevoke.ath.cx/go/

 

Chouette, sauf que tu devrais spécifier utf-8 et pas iso-8859-1 ;)

----------

## Trevoke

PaBou : euh, quoi? Pour le site? C'est pour les accents?

_____________

Voila quelques liens a lire pour une IA qui apprend..

http://www.research.ibm.com/massive/tdl.html

http://www.cs.ualberta.ca/~sutton/RL-FAQ.html

http://www.ecs.soton.ac.uk/~harnad/Papers/Harnad/harnad95.cpnets.html (neural network autossociation).

kwen : on peut toujours commencer par une 'solution simple' mais il faudra de toute facon reecrire le code de zero quand on decide de faire une AI qui va apprendre. Jette un coup d'oeil a TD-gammon (le premier lien), qui est un programme qui a appris a jouer au backgammon tout seul, en jouant contre lui-meme.. 

Le probleme encore une fois est que, d'apres ce que je comprends, une solution simple est insuffisante... Vu que les meilleurs bots en ce moment sont ~10k en moyenne, je pense qu'il faut quelque chose de plus sophistique.

----------

## Tsukusa

J'avais lu un résumé de thèse sur le thème du go. Le thésard avait fait une IA qui apprennait au fur et à mesure qu'elle jouait (contre des joueurs ou des IA existantes). Malheureusement après une journée de recherche je n'ai pas réussi à remettre la main dessus :/

Pour ce qui est du langage et autre petites questions soulevées ici, j'attend une réponse d'un de mes professeurs travaillant dans le domaine de l'IA.

----------

## Trevoke

http://sboisse.free.fr/fun/fractal_go.html

Aussi, regarde sur www.alltheweb.com avec ces mots cles : 

"intelligence artificielle" "jeu de go" apprentissage

J'ai trouve 2 pdfs au debut, je ne sais pas si c'est de ceux-la que tu parles..

----------

## Trevoke

*WHOA*

http://www.ai.univ-paris8.fr/~cazenave/papers.html

Je crois que j'ai trouve ton gars!

----------

## Tsukusa

En effet c'est lui mais je n'avais pas vu les autres documents... C'est impressionant   :Shocked: 

----------

## Trevoke

J'en ai pour un bout a tout lire. Je me sens tout con de pas avoir cherche en francais, j'oubliais que les francais sont forts dans ce domaine, meme si on n'entend pas trop parler d'eux.

----------

## Longfield

En ce qui concerne les algorithmes d'apprentissage de type réseaux de neurones comme le propose Tsukusa, je connais un peu ça, j'ai eu un très bon cours à 6 crédits à ce sujet l'an passé : Pattern Classification and Machine Learning

Maitenant, il faut bien voir que ce genre d'algos et généralement utilsé pour classifier des objets (genre dans mon projets, on lui donnait des statistiques sur les cellules prélevées lors d'une biopsie d'un sein, et le classificateur devait donner une réponse s'il y avait cancer du sein ou pas). Donc, on pourrait imaginer de classer les coups possibles en coups bons (positifs) ou mauvais (ne va pas nous faire gagner grand chose).

Le gros problème de ce genre d'algorithmes, c'est qu'il lui faut une base de donnée initiale relativement importante pour l'entrainer à la base. Et dans le cas du jeu de go, c'est là que ça deviendrait cotton : comment évaluer toutes les composantes du jeu (toutes les positions des pions) et ensuite aisément qualifier le coup comme bon ou moins bon en fonction de la suite de la partie ?

Ces algorithmes sont très efficaces et ont l'avantage de pouvoir ensuite quand on a une base de donnée qui s'agrandit de devenir de plus en plus pertinents. Mais dans notre cas, le problème serait justement de constituer cette base de données. Mais enfin, je ne connais pas bien le jeu, donc peut-être que la tâche de construire la base de données pour quelqu'un connaissant mieux le jeu ne serait pas un si gros problème.

----------

## Tsukusa

Bah cette base de données pourrait être énorme dans le cas du jeu de go ... Si l'algorithme n'arrive pas à traiter de grand flot de données ce n'est pas la peine (encore faut il juger la place prise par la BDD comme acceptable...).

Sinon tu as bien de la chance d'avoir eu un cours la dessus, j'aimerais bien faire plus d'IA dans mon école (là c'est plus je fais plein de trucs pas intéressants et ca me laisse pas le temps de faire les trucs intéressants :/).

----------

## kwenspc

Je suis d'accord avec Longfield, il faut en effet une base TRES conséquente et vu les possibilités... je pense que c'est une idée à rejeter. 

(surtout que l'apprentissage d'un réseaux prend enormément de temps selon la taille de la base d'apprentissage, le nombre de neurone dans la couche cachée, le type de technique utilisée (apprentissage puis validation, validation croisée etc...) bref c'est sans doute aller dans un chemin tortueus pour peu de résultat vu le problème)

Trevoke : les meilleurs bot n'ont pas un super niveau et pourtant parmis eux il y en a qui fonctionne par apprentissage d'après ce que j'ai pu voir (bon ok j'ai pas fait un recherche exhaustive). De toute façon si tu veux arriver à un truc sympa qui arrive peut-être au même niveau de ce qui se fait de mieux, il te faudra quelque chose de sophistiqué et de bourrin  :Smile: 

c'est un beau challenge, il y a une forte concurrence en tout cas!

----------

## killerwhile

Le python est actuellement un très bon candidat pour remplacer les langages fonctionnels tel lisp et prolog, car il peut-être lui-même fonctionnel !

A retenir pour développer une IA.

----------

## kwenspc

prolog n'est pas fonctionnel, c'est du déclaratif pur.

lisp est en effet fonctionnel par contre

----------

## killerwhile

 *kwenspc wrote:*   

> prolog n'est pas fonctionnel, c'est du déclaratif pur.

 

Oui en effet, j'ai du avoir une petite confusion du lundi matin.

Sans doute trop de soleil et de neige ce week-end...

----------

## Trevoke

Killerwhale : alors entre le python et le D qui est une sorte d'evolution du C++, tu recommanderais quoi  ?

kwenspc : mais si je cree un programme qui peut jouer contre lui-meme, il pourra peut-etre apprendre tout seul, non?  :Smile: 

----------

## kwenspc

Oui tu peus le faire auto-apprendre comme ça mais c'est une méthode TRES limité, les coups qu'il va tenter seront "inconsistant" dans le sens où, pour éviter qu'il boucle toujours sur les seuls coups qu'il connait, il faut insérer de l'aléa... et on tombe alors sur un pb d'espace. 

T'as vu le nombre de coups possibles et qui ne veulent rien dire? (dans le sens où ils ne suivent aucune stratégie)

C'est calculable mais on tombe dans un espace infini de solution, donc "physiquement" parlant c'est incalculable. 

Donc le mieux pour apprendre c'est forcément avec un bon joueur. L'ordi va tenter de "copier" les stratégies du joueur en les apprenant.

Par contre, pour contrer un coup qu'il ne connait pas il faut utiliser un algorithme de prédiction de coup comme un min-max amélioré et spécifique au go par exemple mais là dessus je doute d'être de bon conseil (qui plus est sur le go, faudra trés vite limiter la descente à 2 ou 3 niveau sinon on retombe sur le même problème : trop de calculs, de solutions possibles...enfin je vous laisse vous renseignez à dessus, si ça se trouve vous pouvez descendre plus bas).

C'est d'ailleurs cette capacité de prédiction "intelligente" et rapide qui fait qu'un programme comme celui là est bon ou non. Si on attends 1 minute pour un coup médiocre soit...mais si on attends 10 min pour un coup à peine meilleur c'est pas génial. 

Le mieux étant de trouver un bon coup (enfin quelque chose de pas débile quoi) en trsés peu de secondes. et là...   

Mais bon, j'imagine qu'il existe de bien meilleur textes sur le sujet. 

 entre le D et le python je choisirais le python. Le D étant un langage trop peu connu. Si vous voulez rameutez du monde prennez un langage qui a de la "bouteille" comme le python ou le ruby par exemple. 

De toute façon pour les routines algorithmiques demandant le plus de réactivité possible il vous faudra coder ça dans un langage plus à même de vous fournir cette réactivité  (le C?) et vous wrappez par dessus pi c'est bon  :Mr. Green: 

enfin c'est ce que je pense, je me trome peut-être (y a des chances)

----------

## Trevoke

Disons que le D permet d'aller au niveau de la machine (mais la, bon, ca deviendra vite un probleme avec x86 et x86_64 ... ) comme le C ou le C++, donc ca pourra aller vite.

Je ne sais pas a quel point Python est rapide, en fait.. emerge est pas mal vu tout ce qu'il y a d'infos a gerer.

Kwen : oui, en effet. Pour eviter que l'IA ne commence comme un gros boulet, je voudrais aussi preparer une fonction pour pouvoir lire les jeux qu'on lui donne et apprendre de ces jeux (il y a un format standard sur le net, .SGF, qui si ca se trouve veut simplement dire Saved Game File). Ces fichiers prennent tres peu de place sur l'ordinateur, donc c'est pas trop dur d'en ramasser plusieurs.. Et ca donnera un bon debut a l'IA.

----------

## killerwhile

J'ai pas d'expérience en D, mais le python ca avance plutot bien  :Wink: 

En tout cas google lui fait confiance en grande partie.

----------

## Trevoke

Google utilise Python pour le moteur de recherche?

Pas trop etonnant. Portage et moteur de recherche = meme principe...

Intelligence Artificielle = pas le meme principe  :Smile: 

----------

## Tsukusa

l'Intelligence Artificielle, pour certaines méthodes qui devront certainement être utilisées, fait appel à des bases de données (pas forcément relationnelle) et donc il faut bien de la recherche :p.

Mais je pense que l'utilisation d'une couche de C pour tous calculs demandant des optimisations et de la rapidité est nécessaire. Après Python à l'air très bon dans la recherche d'informations (enfin j'aime pas trop la syntaxe de Python moi   :Confused:  ). 

Enfin j'attend toujours une réponse à mes questions envoyés à un de mes professeurs. Et en attendant j'ai trouvé un livre sur l'apprentissage artificiel. 

PS: Bonne idées de lire les parties surtout que ca peut se récupérer en grand nombre sur les serveurs de jeu et de tout niveau ^^.

----------

## Trevoke

http://www.gozillago.net/

Et un lien de plus qui parle, lui, juste de creer un programme qui pourrait jouer au jeu de go en emulant le style d'un joueur particulier. Ceci dit, il y a plusieurs textes interessants au niveau de choisir proprement pour 'pattern selection'.

----------

## Trevoke

Bon; j'ai decide -- cette decision pourra changer dans le futur, comme tout le reste, mais nous allons tout du moins commencer par utiliser Python pour coder.

----------

## killerwhile

Ah, excellente réponse  :Wink: 

Tu ne vas pas le regretter.

Pour google, en réponse un peu tard, oui ils utilisent du python. Pas pour leur base de données, mais pour la gestion des algorithme de ranking.

----------

## Trevoke

Bien, bien.

Alors, euh, je pense que je vais ouvrir une page sourceforge pour le projet, y a quelqu'un qui est doue en HTML? ..  :Smile: 

(note : quand je dis "doue en HTML", je veux juste dire quelqu'un qui peut rendre une page web jolie a voir, quoi...).

----------

## killerwhile

mediawiki ?

c'est pratique et joli  :Wink: 

----------

## Trevoke

<--- Completement inculte quand on en vient a l'art du site web.

En plus il faut un nom pour le projet et je seche a mort.

----------

## killerwhile

1-2 idées : 

* goforit 

* goal(l) 

* gottéron

----------

## killerwhile

ou alors utiliser le g pour gentoo et le o pour quelque chose d'autre

----------

## Trevoke

Quelqu'un m'a propose Go-voke.

C'est un peu pretentieux vu que je pense que je ne serai pas le seul developpeur, mais c'est vrai que c'est sympa comme nom.. facile a lire, dire, utiliser.. Personne d'autre ne le prendra.. Vous en pensez quoi vous?

----------

## killerwhile

oui, ca va bien dans l'idée et comme tu es l'initiateur, je ne trouve pas que c'est tellement prétentieux (pas plus que linux  :Wink: )

----------

## yoyo

Je suis cette "conversation" depuis le départ avec intérêt. Et si mon niveau en programmation ne me permet pas de participer (   :Sad:   ) j'ai un nom qui me vient en lisant :  *killerwhile wrote:*   

> ou alors utiliser le g pour gentoo et le o pour quelque chose d'autre

 

GoG, soit Go on Gentoo. Mais je ne sais pas si le nom est déjà pris.

Sinon, Go-voke est bien également. Et il pourrait y avoir une fonction equi-voke qui équilibrerait les niveaux des joueurs en fonction de leurs précédents résultats.   :Rolling Eyes: 

Mes 0.02 cents.

----------

## Trevoke

*chuckle*

Oui, bon.. Vu que personne ne s'en est plaint (et que les plaintes viennent plus vite que les compliments), j'ai cree le projet sur sourceforge  :Smile: 

Yoyo, le nom est une bonne idee, mais j'espere que ca ne sera pas limite a Gentoo.. Et peut-etre meme (!!) pas seulement developpe sur Gentoo.

http://sourceforge.net/projects/go-voke/

Maintenant il n'y a plus qu'a savoir qui veut m'aider a developper..  :Smile: 

Je pense qu'il va nous falloir

- Python

- C / C++

- Webpage (bon, c'est relativement important quand meme.. heh)

- Recherche

Tout ca peut se recouper evidemment.. 

Et dans le futur, peut-etre meme qu'on voudra une interface graphique (des fois qu'on le developpe en vrai client pour KGS, etc etc..).

Alors.. Qui est avec moi? Yoyo, a propos, ne dis pas que tes connaissances en programmation ne te permettent pas de participer, j'ai l'intention d'apprendre le Python pour ce projet (et peut-etre le LISP dans le futur, d'ailleurs)..  :Smile: 

----------

## sireyessire

 *Trevoke wrote:*   

> 
> 
> Je pense qu'il va nous falloir
> 
> - Python
> ...

 

le C/C++ est plutôt absent de ta page sourceforge. En la lisant (en tout cas en début d'aprem heure fr) l'accent est fortement mis sur plateform independent & Python

un oubli?

----------

## kwenspc

j'imagine de toute façon que le C/C++ viendra après validation de certains algorithme en python, juste pour gagner en performances quoi. 

enfin bref.

Moi si j'ai le temps dans quelques jours je pourrais me joindre au projet, mais sans doute pas à plein temps (j'ai déjà tellement d'autres trucs). Enfin pour aider un chtit poil je dis pas non (si mon aide vaut quelque chose...)

----------

## Trevoke

Presque un oubli.

Le code sera en Python, mais je ne sais pas si on aura besoin de creer des modules pour certaines taches ou non. Si je m'ecoutais, je mettrais C++ et LISP sur la page, juste pour etre sur.. Je peux changer toutes ces infos sur la page de toute facon.

J'ai prefere rester minimaliste, quitte a ajouter quelque chose plus tard.

----------

## Trevoke

http://www.maths.nottingham.ac.uk/personal/anw/G13GT1/compch.html

http://mathforum.org/advanced/game.html

----------

## Nirna

 *kwenspc wrote:*   

> 
> 
> C'est calculable mais on tombe dans un espace infini de solution, donc "physiquement" parlant c'est incalculable. 
> 
> Donc le mieux pour apprendre c'est forcément avec un bon joueur. L'ordi va tenter de "copier" les stratégies du joueur en les apprenant.
> ...

 

Mes deux balles : 

Pour le go, je ne sais pas trop, mais pour les Echecs, la grosse majorité des programmes fait de l'alpha-beta, ou une variante.

Le problème de la profondeur de recherche est bien sûr critique, ainsi que la situation à l'arrêt du calcul.

Il y a des techniques pour éliminer des pans d'arbres (mais je ne connais pas assez pour en causer), ou pour creuser plus en profondeur sur certains scénarios : 

- par exemple, sur une série d'échanges, il faut aller assez loin dans le calcul (en profondeur) pour aboutir à une situation "stabilisée" où l'estimation de la position a un sens.

- sur un coup "positionnel" (sans échanges tactiques), il n'y a pas besoin d'aller très loin, ce sont les critères stratégiques qui prédominent. Bien sûr, en descendant un peu, on peu retomber sur une situation d'échanges.

Un des gros défauts des premiers algos étaient de s'arrêter trop tôt sur les prises : je prend le cavalier adverse, il me reprend le mien avec sa dame... Un cavalier contre un cavalier, c'est équilibré, ça baigne.

Sauf qu'un coup plus loin (non calculé, effet d'horizon), je lui pique sa dame avec mon pion   :Laughing: 

Je suppose, vu le peu que je sais du go, qu'il doit y avoir un même processus de résolution qui doit "aller au plus profond possible" sur des phases tactiques : pour déterminer si un groupe peut être capturé, il doit falloir étudier chaque occupation de cases autour du groupe, et ainsi de suite, jusqu'à obtenir uné évaluation ferme sur le sort du groupe...

Je suppose qu'il doit être relativement simple d'arrêter le calcul (ex : un oeil qui garantit la survie du groupe, pas besoin de calculer...).

Ca permet de ne pas tout calculer (ce qui est impossible, of course), et d'être quand même assez pointu sur ce qui le nécessite...

Bref, l'algo de calcul, c'est déjà une première grosse difficulté.

La deuxième, du moins aux Echecs, et il n'y a pas de raison que ce soit différent au go (je pense que c'est même beaucoup beaucoup plus compliqué), c'est la fonction d'évaluation !

Déjà aux échecs, ce n'est pas simple : c'est un joyeux mélange entre une composante matérielle (chaque pièce a une valeur, et la somme des valeurs des pièces de chaque camp fournit une première estimation. Assez simple en première approche à mettre en oeuvre), et une composante positionnelle (et là, le foutoir commence : bonus pour un roi bien abrité, pour des pièces actives, ou qui occupent des positions stratégiques, en fonction du type de position (ouvertes ou fermées), la valeur initiale des pièces peut évoluer...))

Ce qui fait que maintenant les programmes d'échecs battent 99% des (forts) joueurs, c'est surtout l'amélioration de cette fonction d'évaluation. 

J'ai l'impression qu'au go, la "valeur" d'une position est beaucoup plus subtile à estimer.

Quels sont les éléments qui font qu'un joueur trouve sa position correcte, ou encore que le joueur va vouloir mettre en place sur le go-ban (!?) pour arriver à un truc qui le satisfasse ?

Et là, manifestement, c'est le gros hic...

----------

## kwenspc

Ahma voilà des précisions sympas   :Cool: 

----------

## Mickael

Salut Trevoke et tout le monde,

j'apporte mes 2 cents, voici un lien qui catalogue des jeux de go, sous différentes OS, il y en a même sous licence GNU et sous linux/unix.

Si cela peux vous aider.

Voilà.

http://www.britgo.org/gopcres/gopcres1.html

et le wiki avec ses liens bien sur.

Edit : j'ai quelques articles sur ce jeu : domaines de plublication: math, IA. (si cela vous intéresse : mp)

----------

## Trevoke

Nirna : j'avais une bonne reponse preparee mais X a crashe et j'en ai profite pour faire un eix-sync + migration vers X modulaire. Enfin bon, bref, j'ai oublie presque tout ce que j'ai dit... Alors je vais faire un resume moins zouli.

Tu apportes d'excellents points. Il n'y a aucune valeur pour chaque pierre (1 point, c'est la meme pour toutes les pierres), mais la valeur positionnelle est enorme.

Un groupe de pierre peut valoir enormement au niveau positionnel; ceci dit, savoir si l'on peut sauver un groupe de pierres est relativement facile a compter, je pense (faut regarder les libertes et voir si elles disparaitront plus vite qu'on ne peut s'echapper ou pas).

Pour ton gros hic, et oui! le jeu de go n'est pas un jeu purement logique.. Il y a une bonne dose d'intuition qui y entre, et en effet, au niveau des ordis, oups.

----------

## Tsukusa

Intuition mais aussi de stratégies à long terme :p.

Et puis il n'est pas rare dans une partie de go de parfois se laisser prendre une zone pour en assurer une autre plus grande. Enfin pleins de concessions ou le meilleur coup c'est justement de pas faire le meilleur coup... (en tout cas du point de vue logique).

En tout cas je pense que la partie de l'IA la plus facile à aborder dans le jeu de go, c'est la fin de parti où on protège ses territoires. C'est la plus logique des trois et une approche traditionnelle je pense serait suffisante (bases de données de fin de partie sauf que là au lieu de prendre le go-ban en entier, il vaudrait sans doute mieux travailler sur des "motifs" plus ou moins fréquents).

En tout cas bon courage pour ton projet Trevoke. J'aurais bien aimé y participer mais je suis encore plus mauvais en intelligence artificielle que je le suis en programmation (manque de pratique   :Confused:  ).

----------

## Trevoke

Merci tsukusa.. Je pense que tu as raison, la fin de partie sera la plus simple a programmer (d'ailleurs dans un des bouquins que j'ai achete y a carrement un pseudo-code algo pour calculer la valeur du territoire qu'on se dispute, ca risque d'etre utile..).

Ceci dit, ne vous decouragez pas, hein, je n'y connais encore pas grand-chose en IA et encore moins en Python, mais j'apprends, parce que j'ai envie de faire ca.. Donc vous avez tous aussi plein de temps pour vous ameliorer si vous avez envie de m'aider  :Smile: 

----------

## marvin rouge

 *Tsukusa wrote:*   

> En tout cas je pense que la partie de l'IA la plus facile à aborder dans le jeu de go, c'est la fin de parti où on protège ses territoires. C'est la plus logique des trois et une approche traditionnelle je pense serait suffisante (bases de données de fin de partie sauf que là au lieu de prendre le go-ban en entier, il vaudrait sans doute mieux travailler sur des "motifs" plus ou moins fréquents).

 Je plussoie, la fin de partie est assez "combinatoire", un programme devrait pouvoir s'en tirer mieux qu'un humain (sauf si on commence à introduire des ko, peut-être). Il s'agit "juste" de maximiser le nombre de points, et donc de déterminer l'ordre dans lequel on finit les frontières. Enfin, quand je dis "juste" ...

Par contre, pour faire "comprendre" la notion d'influence d'une pierre, et la notion de zone d'influence (avec plusieurs pierres, et les coupes...) ... outch.

bon courage   :Wink: 

----------

## Tsukusa

Trevoke je voudrais bien mais avant de vouloir faire une IA sur le jeu de go en Python même sans connaître le Python et les bases de l'IA, il faudrait quand même que j'ai un bon niveau au jeu de go pour en comprendre les principes fondamentaux et bien plus en fait.

Enfin ... Je crois que d'ici à ce que je puisse rejoindre le projet, il se sera écoulé quelques mois.

----------

## Nirna

 *Trevoke wrote:*   

> Nirna : j'avais une bonne reponse preparee mais X a crashe et j'en ai profite pour faire un eix-sync + migration vers X modulaire. Enfin bon, bref, j'ai oublie presque tout ce que j'ai dit... Alors je vais faire un resume moins zouli.
> 
> Tu apportes d'excellents points. Il n'y a aucune valeur pour chaque pierre (1 point, c'est la meme pour toutes les pierres), mais la valeur positionnelle est enorme.
> 
> Un groupe de pierre peut valoir enormement au niveau positionnel; ceci dit, savoir si l'on peut sauver un groupe de pierres est relativement facile a compter, je pense (faut regarder les libertes et voir si elles disparaitront plus vite qu'on ne peut s'echapper ou pas).
> ...

 

Je suppose que tu as jeté un coup d'oeil au projet GNUGo, mais il y a un point intéressant sur les algos de générations des coups  http://www.gnu.org/software/gnugo/gnugo_6.html#SEC67

En survolant rapidement, il semble qu'ils aient adopté plusieurs moteurs de générations de coups, qui en fonction de leur spécificité proposent des coups et un motif.

Ca a l'air assez élégant comme approche, et en tout cas, ça lève un peu la complexité : l'algo "sauver un groupe de pierre" a l'air faisable rapidement...

Par contre, sur le gros hic : ça semble vouloir dire aussi que l'approche calculatoire des Echecs (de type alpha-béta) n'a pas l'air trop possible.

Il n'y aurait qu'une petite partie (probablement la capture, donc sur une toute petite partie du go-ban) où l'on aurait ce type d'algo.

Sur la globalité du go-ban, il faut trouver autre chose, et surtout l'IA qui va fédérer le tout et déterminer THE move...

----------

## Trevoke

L'avantage de gnugo est qu'ils ont identifie les problemes pour nous; ce qui revient a dire qu'on sait ou preparer les poids (les variables dont les valeurs devraient aider a decider), ce qui est gentil  :Smile: 

J'ai peut-etre tort mais j'ai l'impression qu'avec une IA qui apprend, ces algorithmes ne sont pas necessaires (enfin, on verra).

Merci quand meme pour le lien, c'est une bonne garantie qu'on avancera (relativement) vite  :Smile: 

----------

## Trevoke

http://neuromancer.eecs.umich.edu/cgi-bin/twiki/view/Main/AlgorithmsOfRL

----------

## fribadeau

 *PabOu wrote:*   

> Chouette, sauf que tu devrais spécifier utf-8 et pas iso-8859-1 

 

 *Trevoke wrote:*   

> PaBou : euh, quoi? Pour le site? C'est pour les accents?

 

Oui.

Tes pages sont sauvegardées (il me semble) en UTF-8 et tu indiques 

```
charset=iso-8859-1
```

dans tes entêtes...

----------

## Trevoke

C'est pas exactement comme si c'est moi qui avais cree le DGS, vous savez..  :Smile: 

En parcourant SF, j'ai trouve ce projet : http://sourceforge.net/projects/olego

OO Learning Evaluation Go. Je vais le joindre pour son projet d'abord, je pense, et ensuite, quand le sien sera pret (ou quand on pourra s'en servir, tout d'abord), je m'en servirai comme base pour mon projet (un peu plus complet). ... A moins qu'on ne decide de travailler tous les deux dessus. On dirait que je vais coder en C++  :Smile: 

----------

## fribadeau

 *Trevoke wrote:*   

> C'est pas exactement comme si c'est moi qui avais cree le DGS, vous savez.. 

 

C'est pas toi ? Ben alors, ch'suis déçu...   :Twisted Evil: 

Mais pour ton jeu, j'vais d'abord apprendre à jouer un peu, pis j'reviendrai voir...

Bon courrage

----------

## Trevoke

www.dragongoserver.net c'est le serveur officiel. Je voulais juste en faire un petit ou je puisse jouer avec mes copains, donc j'ai pris le code de sourceforge  :Smile: 

----------

## Trevoke

Si on pouvait considerer une intuition, ca serait sympa. Disons.. Une approximation de la situation du goban sans faire d'essais pour des placements potentiels -- et le meilleur mouvement pour prendre plus de territoire. L'equilibre, de l'autre cote, viendrait du meilleur mouvement local : ou est-ce que j'ai joue en dernier, ou est-ce que l'adversaire a joue en dernier? Regarder le goban avec un rayon d'environ trois pierres de ces mouvements pour essayer de voir ce qui se passe.. Et evidemment, s'il y a des grands groupes, il faut les considerer aussi, avec leurs libertes..

----------

## Trevoke

En passant, un des projets sur sourceforge, go-kashiki, est fait par des russes et ca fait 5 ans qu'ils travaillent dessus; donc c'est pas pour demain, ce projet..  :Wink:  Faut juste rester avec.

----------

## Trevoke

http://www.goban.demon.co.uk/go/shimada/intro.html

"mathematics of go" -- une traduction de quelques endroits. Le chapitre 6 est "problemes dans la composition des regles du jeu de go" -- tres interessant, donc.

----------

## laurentp

Ce projet m'intéresse bien. Oû en sommes-nous ? Est-cce mort ?

----------

## Trevoke

Non, ce n'est pas mort, mais c'est en pause parce que je n'ai pas les connaissances necessaires pour avancer plus loin que le stage de preparation. Il faut que je m'ameliore au go et que je m'ameliore en programmation..  :Smile: 

----------

## Trevoke

Une nouvelle idee (enfin.. nouvelle pour moi en tout cas) serait de faire une representation graphique du goban pour l'ordinateur et ensuite d'analyser cela, puisque le jeu de go est un jeu qui est en grande partie un jeu de reconnaissance de formes (pattern recognition).. Ca pourrait marcher et etre tres different de ce qu'on a en ce moment, je pense.. ?

----------

## victorf

(je m'en excuse d'avance, je n'ai pas lu tout le topic)

Je me souviens avoir eu un échange de mail à propos d'IA avec un certain Tristan Cazenave de Paris 8, qui est je crois spécialiste de l'IA au Go, ou quelque chose du genre.

Je vous laisse apprécier ses papiers : http://www.ai.univ-paris8.fr/~cazenave/papers.html en espérant que vous y trouverez qqchose d'intéressant pour ce projet titanesque  :Wink: 

----------

## Nemerid

Je peux éventuellement proposer mon aide. J'ai des connaissances de programmation en python, mais si c'est possible, je préfère donner mon aide sur la partie qui concerne le jeu de go. (Je suis environ 5ème kyu).

A savoir surtout que la programmation ne peux en aucun cas se baser sur l'apprentissage d'un autre joueur ou sur la combinatoire. La grosse différence avec le jeu d'echec cité avant est que le jeu de go n'est pas seulement un jeu tactique, mais surtout un jeu stratégique. (Qui prend en compte l'ensemble du goban).

Donc meme si une forme ou une séquence de coups peut paraitre la meilleure dans de nombreuses parties, elle sera peut-être pas très bonne dans une autre partie. Le fuseki (l'ouverture d'une partie de go) est sans doute une partie très complexe à modéliser.

Même un professionnel du jeu de go qui passe sa vie à y jouer et à étudier ne comprend finalement qu'à la fin de sa carrière, 10% des capacités que lui offre le jeu. La difficulté réside essentiellement dans le fait qu'on doit modéliser une intelligence sur des concepts qu'on a nous même déjà beaucoup de mal à saisir.

Il y a aussi la règle du ko qui pose de nombreuses complications dans les possibilités (tactique et stratégique). Il est bien sur évident qu'il faut plusieurs alogirhtmes (reconnaissance de formes, combinatoire, joseki enregistrés dans une bdd, notions d'influence, moyo, territoire, etc...) mais le plus dur est de savoir lequel alogithme choisir tout en supposant que tous marchent parfaitement.

C'est là toute la difficulté du jeu et ce qui explique par exemple, que je puisse gagner contre gnugo en lui offrant par exemple 8 pierres d'avance sur un goban de 19x19.

Si vous avez des questions sur le jeu et si je peux apporter ma contribution en tant que passionné du go et en meme temps gentooiste, n'hésitez pas  :Smile: 

Marc.

----------

## Pixys

A tout hasard un petit lien vers un manuel d'apprentissage python: http://www.cifen.ulg.ac.be/inforef/swi/python.htm

on l'utilisait en 1ère année de fac de sciences (en France) d'après nos prof, en suivant le manuel, on peut apprendre le python en 1 week-end... je t'avourai que je n'ai jamais essayé (c'est peut-être pour ça que j'ai pas validé le module d'info).

Mais je suppose que tu as déjà des ressources à ta dispositions  :Smile: 

----------

## pathfinder

j ai lu que les 2 premieres pages

mais il existe un code open source de reseau neuronal qui apprend a partir de bases de donnees.

il utilise soit des algos d evolution pour trouver une solution de facon assez robuste (un mini de fonction) mais lente mais une fois qu il en a trouve une il peut utiliser les gradients conjugues pour converger rapidement vers la solution tout en restant dans le meme sous espace.

en gros ca combine une methode lente mais robuste (meme si on va souvent vers un temps treeess long de recherche puisqu il faut augmenter les populations, les generations et les mutations) avec une methode qui est tres rapide une fois qu elle sait a partir de quelle solution initiale partir.

ce code j arrive pas a le trouver, je tarderai pas, mais il est en C/C++. je peux expliquer les idees des algos utilises si vous voulez.

le python  c est pas mal, mais vu quel ecode est en open source et qu il faut surtout pouvoir lui infiltrer la lecture de parties/mouvements, en pus des sgf que trevoke a mentionnee, je crois que c est un bon debut.

ou en tout cas a mettre sur la page en link.

je vous le file incessament sous peu... j arrive ñas a trouver et je pouvais pas attendre de dire ceci.

edit: ca yest j ai lu la totalite du topic   :p

bon le mini de la fonction c est le maxi de la fonction opposee.

et je parle de la fonction d evaluation qui est toujours assez problematique.

cependant marc a apporte quelque chose de tres pertinent:

si un humain ne peut pas connaître la totalité des possibiltés du go, si a la fin on ne connait que 10%, comment modéliser le bon comportement?

ca a l'air négatif, en effet, mais dans un premier temps, j'ai envie de dire que plus on est vieux, plus on domine le go.

les authentiques specialistes sont les "sages" japonais (on a envie de dire ca meme s il y a des exceptions).

on ne pourrait donc jamais dépasser le modèle par la connaissance de celui qui en sait le plus.

je ne sais pas. je crois pas.

en realite, justement, plus la bdd est grande, plus le PC sera expérimenté. mais comme dit Marc notre facon de jouer sera toujours la même et contemplera tout le temps les mêmes mouvements. ce qui peut vouloir dire que ce modèle pourrait représenter les limites de notre capacité à raisonner. La capacité humaine à être abstrait et à raisonner.

a long terme, on serait donc tous battus simplement par la machine, mais celle-ci ne serait qu un poil meilleure que le meilleur joueur qu elle ait rencontré ou que l ensemble des joueurs rencontrés.

il y a bien les mutations pour essayer de epcplorer de nouvelles voies, mais alors, completement au hasard, et ca aussi l humain sait le faire.

c est en tout cas bien complexe.

et si des russes, il y a 5 ans, sont dessus, ca risque d etre long.  :Razz:  mais passsionant.

bon courage et faut pas abandonner.

moi cote go j ai jamais joue, cote pythonm, rien, cote C/C++ je suis pas une fleche, page web non plus. mais niveau explications de certaines choses je peux peut etre aider. traductions aussi. voila

----------

## pathfinder

voila:

www.cimne.com/purple

c est le nom du code dont je vous ai parle. il doit y avoir des trucs interessants (sinon tout)

c est en opensource.

----------

## Trevoke

Ca a l'air tres sympa. Plus je m'ameliore au go, plus j'en apprends plus je suis epate. Une chose est claire, une IA pour le jeu de go en fait c'est pas un bon point de depart, faut commencer par une IA pour tic-tac-toe et s'habituer aux idees et au style de programmation comme ca  :Smile: 

Je me suis attele au projet pour revolutionner l'IA en fait, et je m'y connais pas assez pour faire ca..  :Smile: 

Je le garde toujours en tete, mais je dois devenir bien meilleur au go avant de pouvoir meme commencer esperer m'y atteler.

----------

## Nemerid

Trevoke, tu joues sur quel serveur et avec quel pseudonyme. Peut-être aurions nous l'occasion de faire une partie entre gentooistes ?  :Smile: 

----------

## Trevoke

Je joue avec le pseudo Trevoke sur KGS (mais je n'y suis quasiment jamais), http://www.dragongoserver.net et http://trevoke.ath.cx/go/

J'ai d'ailleurs deja recupere niin sur mon petit serveur de go!

 :Smile: 

----------

## dworkin_dambre

salut à tous, bon, je me presente, dworkin, (alias Perro sur KGS), et avec un ami on a commencé à travaillé sur un proejet de ce type en C++.

Bon, les taches sont partagés, il est bon en prog, et je suis doué au Go (enfin, tout est relatif...)

donc il serait peut etre interessant de faire equipe commune ^^

voilavoila ^^

----------

## Trevoke

J'ai quasiment completement lache l'affaire parce que tout seul c'etait beaucoup trop dur -- et j'avais vraiment envie de m'ameliorer au go. Maintenant je comprends un peu mieux les principes et ca ne me derangerait pas de reprendre  :Smile: 

----------

## dworkin_dambre

 :Smile: 

Bon, voila une bonne chose. Le mieu serait que tu me cobtact sur MSN ou sur KGS, qu'on puisse discuter en direct.

Sinon, on a besoin de toute personne motivé!

D'autre programmeur sont pret à s'attaquer à l'algorithme le plus dur de tout les temps (peut etre est ce exagéré, mais c sans doute un des plus interessants)?

----------

## nemo13

bonjour,

je suis tombé sur cette page

A+

----------

## anigel

Bonsoir,

Il semble que ce projet parte maintenant vers des horizons plus "larges" que celui de la seule distribution Gentoo. On envisage de dé-stickyser, ou la visibilité du post demeure encore importante ?

----------

## Trevoke

Et bien, les deux, mon capitaine.. C'est important qu'il soit en vue, mais je ne peux pas demander a garder le sticky de facon sommaire... :/

----------

## Magic Banana

J'invite toutes les personnes intéressées par ce projet (ou par l'informatique théorique en général) à lire le dernier numéro de "Pour La Science" (Avril 2007). En couverture : L'ordinateur maître de Go.

L'article associé est un modèle de clarté. La première moitié est consacré aux approches traditionnelles (Min-Max et ses optimisations, en particulier Alpha-Beta) et explique bien pourquoi ces algorithmes ont énormément de mal à tenir tête aux joueurs de Go (explosion combinatoire de l'arbre des coups possibles, nécessité d'une vision à long terme, difficulté à évaluer une position de jeu). La seconde partie explique comment une approche probabiliste (évaluation par simulation Monte-Carlo) semble être nettement plus porteuse d'avenir. En fin d'article les auteurs mettent en avant leurs derniers travaux consistant à "desuniformiser" la distribution de probabilité grâce à une connaissance experte du jeu.

Si vous deviez vous lancer pour de bon dans la conception d'un nouvel algorithme de Go, c'est très certainement cette dernière approche hybride que vous devriez choisir.

L'article est très abordable et des encadrés fournissent les détails à celui ou celle qui souhaiterait comprendre les détails des algorithmes. En fin d'article se trouvent des références vers des articles plus pointus concernant la dernière approche.

En plus dans ce même numéro se trouve un autre article d'informatique théorique tout aussi passionnant. Il concerne la résolution du problème de l'ange de John Conway (à qui l'on doit aussi le célèbre jeu de la vie).

Comment ? ... Non, je ne travaille pas pour ce journal. Pourquoi ?  :Laughing: 

----------

## SanKuKai

Je ne sais pas si ce thread est tombé en désuétude (dernier post datant de plus d'un an) mais le programme MoGo a vaincu le 22 mars un professionnel de Go (5 dan) sur une partie en 9x9.

Y'a pas mal de documents intéressant sur le site du projet notamment la thèse de Sylvain Gelly.

Voilou, c'était la résurrection du jour.  :Smile: 

----------

## Magic Banana

À mon tour de faire une résurrection. À l’occasion du 24e congrès annuel du jeu de "Go", qui s’est déroulé à Portland dans l’Oregon, du 2 au 10 août, le nouveau supercalculateur néerlandais Huygens a eu raison d’un joueur professionnel de Go dans le cadre d’un affrontement officiel avec un handicap de 9 pierres.

----------

## Trevoke

Bon, euh, j'y etais - il faut aussi dire que sur un temps limite d'une heure, le professionnel a utilise 15 minutes et mogo en a utilise 50.. De plus, le professionnel a ensuite estime la force du programme a environ 3d (3eme dan), c'est-a-dire que le pro n'etait pas vraiment serieux et il a juste joue un jeu d'evaluation.

Et puis, si, malheureusement, ce projet est tombe en desuetude :/

----------

