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 Previous  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 22, 2006 5:29 pm    Post subject: Reply with quote

http://www.maths.nottingham.ac.uk/personal/anw/G13GT1/compch.html
http://mathforum.org/advanced/game.html
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
Nirna
n00b
n00b


Joined: 01 Dec 2005
Posts: 36
Location: France

PostPosted: Thu Mar 23, 2006 11:20 am    Post subject: Reply with quote

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.
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à...



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

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


Joined: 21 Sep 2003
Posts: 4906

PostPosted: Thu Mar 23, 2006 11:28 am    Post subject: Reply with quote

Ahma voilà des précisions sympas 8)
_________________
membre officieux du SAV Ati GEntoo
Back to top
View user's profile Send private message
Mickael
Advocate
Advocate


Joined: 05 Sep 2005
Posts: 2383
Location: ~Belfort! - France - EU

PostPosted: Thu Mar 23, 2006 3:40 pm    Post subject: Reply with quote

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)
_________________
À LIRE : COMMENT POSTER ET OBTENIR DE L'AIDE ?
Qui suis-je ? Bon j'ai relu, comme d'habitude, je suis bon a rien le vendredi
Qui suis-je ? Je ne serai jamais modo
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 23, 2006 6:21 pm    Post subject: Reply with quote

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.
_________________
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 23, 2006 8:18 pm    Post subject: Reply with quote

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 :? ).
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 23, 2006 8:38 pm    Post subject: Reply with quote

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


Joined: 01 Aug 2004
Posts: 1422
Location: Villa Lumierrante, Zonelibre

PostPosted: Thu Mar 23, 2006 8:41 pm    Post subject: Reply with quote

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:
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 24, 2006 12:12 am    Post subject: Reply with quote

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


Joined: 01 Dec 2005
Posts: 36
Location: France

PostPosted: Fri Mar 24, 2006 10:27 am    Post subject: Reply with quote

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

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.


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...
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 24, 2006 1:58 pm    Post subject: Reply with quote

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

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 :)
_________________
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 24, 2006 8:09 pm    Post subject: Reply with quote

http://neuromancer.eecs.umich.edu/cgi-bin/twiki/view/Main/AlgorithmsOfRL
_________________
Votre moment detente
What is the nature of conflict?
Back to top
View user's profile Send private message
fribadeau
Apprentice
Apprentice


Joined: 13 Jul 2003
Posts: 153
Location: Thonon (France)

PostPosted: Tue Mar 28, 2006 12:47 pm    Post subject: Reply with quote

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
Code:
charset=iso-8859-1


dans tes entêtes...
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


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

PostPosted: Tue Mar 28, 2006 1:50 pm    Post subject: Reply with quote

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

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


Joined: 13 Jul 2003
Posts: 153
Location: Thonon (France)

PostPosted: Tue Mar 28, 2006 2:43 pm    Post subject: Reply with quote

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:

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

Bon courrage
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 29, 2006 1:42 pm    Post subject: Reply with quote

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 :)
_________________
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: Wed Mar 29, 2006 2:22 pm    Post subject: Reply with quote

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..
_________________
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: Tue Apr 04, 2006 1:15 pm    Post subject: Reply with quote

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.. ;-) Faut juste rester avec.
_________________
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 Apr 07, 2006 7:46 pm    Post subject: Reply with quote

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


Joined: 04 Feb 2006
Posts: 49

PostPosted: Wed May 10, 2006 12:35 am    Post subject: Reply with quote

Ce projet m'intéresse bien. Oû en sommes-nous ? Est-cce mort ?
Back to top
View user's profile Send private message
Trevoke
Advocate
Advocate


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

PostPosted: Wed May 10, 2006 12:39 pm    Post subject: Reply with quote

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.. :)
_________________
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: Tue May 23, 2006 7:41 pm    Post subject: Reply with quote

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


Joined: 04 Jan 2006
Posts: 10

PostPosted: Sat May 27, 2006 5:50 pm    Post subject: Reply with quote

(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 ;)
_________________
http://forums.gentoo.org/viewtopic-t-465986.html : [wifi] TW-4*3PI sur arch 64bit
Back to top
View user's profile Send private message
Nemerid
Tux's lil' helper
Tux's lil' helper


Joined: 14 Jul 2002
Posts: 90

PostPosted: Sun May 28, 2006 6:48 pm    Post subject: Reply with quote

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

Marc.
Back to top
View user's profile Send private message
Pixys
l33t
l33t


Joined: 23 May 2005
Posts: 669

PostPosted: Wed May 31, 2006 3:01 pm    Post subject: Reply with quote

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 :)
_________________
Funtoo ~core2, lvm2, reiser4
FreeBSD-9, ZFS
ArchLinux
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 Previous  1, 2, 3, 4  Next
Page 3 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