Gentoo Forums
Gentoo Forums
Gentoo Forums
Quick Search: in
[OFF] Projet : IA pour le jeu de go
View unanswered posts
View posts from last 24 hours

Goto page 1, 2, 3, 4  Next  
Reply to topic    Gentoo Forums Forum Index French
View previous topic :: View next topic  
Author Message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Wed Mar 15, 2006 4:01 pm    Post subject: [OFF] Projet : IA pour le jeu de go Reply with quote

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.
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Enlight
Advocate
Advocate


Joined: 28 Oct 2004
Posts: 3514
Location: Alsace (France)

PostPosted: Wed Mar 15, 2006 4:07 pm    Post subject: Reply with quote

Moi aussi je manque de temps alors :

1) les règles sont vite apprises?
2) tu comptes coder en quoi?
_________________
le "lol" est aux boulets ce que le ";" est au programmeurs
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Wed Mar 15, 2006 4:40 pm    Post subject: Reply with quote

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 :)
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
bong
Apprentice
Apprentice


Joined: 26 Oct 2004
Posts: 276
Location: Brest / Metz

PostPosted: Wed Mar 15, 2006 8:51 pm    Post subject: Reply with quote

Trevoke wrote:
Quelle langage je compte utiliser? Aucune idee. Peut-etre C++


Prolog plutot...
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Wed Mar 15, 2006 8:54 pm    Post subject: Reply with quote

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?
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
bong
Apprentice
Apprentice


Joined: 26 Oct 2004
Posts: 276
Location: Brest / Metz

PostPosted: Wed Mar 15, 2006 9:15 pm    Post subject: Reply with quote

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 :D ) 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
Back to top
View user's profile Send private message
Leander256
l33t
l33t


Joined: 05 Jul 2003
Posts: 894
Location: Singapour

PostPosted: Thu Mar 16, 2006 6:24 am    Post subject: Reply with quote

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 ;)
Back to top
View user's profile Send private message
papedre
Apprentice
Apprentice


Joined: 02 Mar 2005
Posts: 178

PostPosted: Thu Mar 16, 2006 1:14 pm    Post subject: Reply with quote

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/
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Thu Mar 16, 2006 2:07 pm    Post subject: Reply with quote

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 :)

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 :)


[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 :) ]
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
kwenspc
Advocate
Advocate


Joined: 21 Sep 2003
Posts: 4912

PostPosted: Thu Mar 16, 2006 4:07 pm    Post subject: Reply with quote

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).
_________________
membre officieux du SAV Ati GEntoo
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Thu Mar 16, 2006 4:38 pm    Post subject: Reply with quote

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...).
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Tsukusa
Tux's lil' helper
Tux's lil' helper


Joined: 01 Aug 2004
Posts: 133

PostPosted: Thu Mar 16, 2006 5:17 pm    Post subject: Reply with quote

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 ... :roll:
Back to top
View user's profile Send private message
kwenspc
Advocate
Advocate


Joined: 21 Sep 2003
Posts: 4912

PostPosted: Thu Mar 16, 2006 6:31 pm    Post subject: Reply with quote

...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 :?

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.
_________________
membre officieux du SAV Ati GEntoo
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Thu Mar 16, 2006 6:31 pm    Post subject: Reply with quote

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.. :)
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Tsukusa
Tux's lil' helper
Tux's lil' helper


Joined: 01 Aug 2004
Posts: 133

PostPosted: Thu Mar 16, 2006 6:59 pm    Post subject: Reply with quote

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).
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Thu Mar 16, 2006 7:27 pm    Post subject: Reply with quote

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 :)
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
PabOu
Veteran
Veteran


Joined: 11 Feb 2004
Posts: 1073
Location: Hélécine - Belgium

PostPosted: Fri Mar 17, 2006 12:05 pm    Post subject: Re: [OFF] Projet : IA pour le jeu de go Reply with quote

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 ;)
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Fri Mar 17, 2006 1:58 pm    Post subject: Reply with quote

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.
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Tsukusa
Tux's lil' helper
Tux's lil' helper


Joined: 01 Aug 2004
Posts: 133

PostPosted: Fri Mar 17, 2006 2:24 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Fri Mar 17, 2006 2:50 pm    Post subject: Reply with quote

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..
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Fri Mar 17, 2006 3:09 pm    Post subject: Reply with quote

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

Je crois que j'ai trouve ton gars!
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Tsukusa
Tux's lil' helper
Tux's lil' helper


Joined: 01 Aug 2004
Posts: 133

PostPosted: Fri Mar 17, 2006 5:50 pm    Post subject: Reply with quote

En effet c'est lui mais je n'avais pas vu les autres documents... C'est impressionant 8O
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


Joined: 04 Sep 2004
Posts: 4099
Location: NY, NY

PostPosted: Fri Mar 17, 2006 7:52 pm    Post subject: Reply with quote

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.
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Longfield
Guru
Guru


Joined: 17 Mar 2004
Posts: 358
Location: Switzerland, Fribourg (la Glâne, les vrais)

PostPosted: Sat Mar 18, 2006 12:39 pm    Post subject: Reply with quote

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.
_________________
longfield@swissjabber.ch
Cardinal powered !
Back to top
View user's profile Send private message
Tsukusa
Tux's lil' helper
Tux's lil' helper


Joined: 01 Aug 2004
Posts: 133

PostPosted: Sat Mar 18, 2006 4:36 pm    Post subject: Reply with quote

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 :/).
Back to top
View user's profile Send private message
Display posts from previous:   
Reply to topic    Gentoo Forums Forum Index French All times are GMT
Goto page 1, 2, 3, 4  Next
Page 1 of 4

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum