8x8 dammen uitgeanalyseerd door Chinook

Hanco Elenbaas · Post by **Hanco Elenbaas** » Thu Jul 19, 2007 21:03

website De Telegraaf, do 19 jul 2007, 20:48
http://www.telesport.nl/1906286/___Damp ... nbaar.html

Damprogramma "Chinook" onverslaanbaar

door onze denksportmedewerker

AMSTERDAM - Het Canadese damprogramma “Chinook”, dat geprogrammeerd is door dr. Jonathan Schaeffer van de universiteit van Alberta is onverslaanbaar en sterker dan de mens. Het betreft het zogenaamde checkers ( Engels dammen op het 8x8 bord) en volgens de laatste ontwikkelingen is het spel volledig uitgeanalyseerd, aldus een bijdrage van een vooraanstaand wetenschapsblad.

Het Engels dammen – dat alleen in Engelstalige landen gespeeld wordt – heeft andere regels dan het internationaal dammen op het 10x10 bord, zoals dat in Nederland en in vijftig andere landen bekend is. Engels dammen heeft ook haar eigen wereldkampioenschap en deze strijd wordt al jaren betwist tussen de Amerikaan Alexander Moiseev en Ron King van Barbados.

Dammen kent verschillende uitingsvormen, waaronder veel spelsoorten op het kleine 8x8 bord. Naast het checkers bestaat het zogenaamde Russisch dammen, Braziliaans dammen, Italiaans dammen en zelfs turks dammen (in het Midden-Oosten en Turkije).

Er bestaat zelfs een Friese variant, die ruim 300 jaar oud is en het Canadees dammen op een 12x12 bord. Deze verscheidenheid aan spelvormen heeft de professionalisering van de damsport niet gestimuleerd en door het ontbreken van krachtenbundeling zijn kansen blijven liggen.

De sterkste damprogramma’s van het internationale dammen zijn alleen in blitzpartijen een gevaar voor de huidige grootmeesters, maar het duurt nog vele jaren voor een damprogramma probleemloos van een serieuze wereldtopper wint.

In de schaakwereld lag dit anders toen tien jaar geleden het IBM-schaakprogramma “Deep Blue”voor het eerst van de toemalige wereldkampioen Garry Kasparov won.

Hanco Elenbaas · Post by **Hanco Elenbaas** » Thu Jul 19, 2007 21:14

Zie ook Shashki-topic http://www.shashki.com/PNphpBB2-viewtopic-t-976.html geopend door de verontruste wereldkampioen Alex Moisejev.

En (Engels) http://www.cs.potsdam.edu/sigcse07/schaefferTalk.pdf

steenslag · Post by **steenslag** » Thu Jul 19, 2007 23:38

Artikel in Nature: http://www.nature.com/news/2007/070716/ ... 16-13.html

Het Chinook-team heeft een schitterende website gebouwd waar je de databases mag downloaden. En spelen tegen Chinook!

http://www.cs.ualberta.ca/~chinook/solution/

En het heeft slashdot gehaald. http://games.slashdot.org/games/07/07/19/1952211.shtml

*edit* Na een beetje rondsnuffelen lijkt het er op dat Chinook een onverslaanbare database heeft gebouwd- vanuit de beginstand kan het ding altijd minstens een remisestand uit de 10-stukkendatabase bereiken.

Hehe... uit de slashdot-comments:

"The day an automaton is "unbeatable" is the day it's 500ft tall and shoots nuclear rockets from its fingertips. I think I know a relatively easy way to beat this checkers program.
"

Hanco Elenbaas · Post by **Hanco Elenbaas** » Fri Jul 20, 2007 05:55

Nog wat (Engelstalige) links van Alex Moisejev op het Shashkiforum:

http://www.cs.ualberta.ca/~chinook/publ ... ckers.html

http://abcnews.go.com/Technology/story? ... 382&page=1

http://discovermagazine.com/2007/jul/th ... telligence

Jacques PERMAL · Post by **Jacques PERMAL** » Fri Jul 20, 2007 17:58

WASHINGTON (AFP) - Après plus de 18 ans d'efforts, des scientifiques canadiens sont parvenus à programmer la totalité des 500 milliards de milliards de combinaisons possibles du jeu de dames, réalisant une avancée jugée importante en intelligence artificielle.

Ce logiciel impossible à battre aux dames, baptisé Chinook, a été conçu par le détenteur de la chaire de sciences informatiques à l'université d'Alberta (Canada), Jonathan Schaeffer, avec une équipe d'informaticiens de cet établissement.

Cette percée fait l'objet d'une étude publiée jeudi dans la revue américaine Science datée du 20 juillet.

Achevé fin avril, Chinook permet de jouer jusqu'à une impasse si son opposant joue parfaitement mais sans jamais pouvoir être battu, explique ce chercheur. "C'est une véritable avancée dans le domaine de l'intelligence artificielle", selon Jaap van den Herik, éditeur de la revue de référence "International Computer Games Journal".

"Nous avons monté la barre de plusieurs échelons dans ce qu'il est possible de faire en matière de technologie informatique et d'intelligence artificielle", a estimé Jonathan Schaeffer.

"Piètre joueur de dames" de son propre aveu, ce scientifique a expliqué avoir créé Chinook pour exploiter les capacités actuelles de traitement et de mémoire des ordinateurs mais aussi pour déterminer le meilleur moyen d'incorporer les principes de l'intelligence artificielle pour jouer aux dames.

Il a recouru à l'expérience des meilleurs joueurs mondiaux pour élaborer ce programme.

Quelque 50 ordinateurs ont été mobilisés en moyenne quotidiennement depuis 1989 pour cette recherche avec dans les moments d'activité maximum plus de 200 ordinateurs fonctionnant à plein régime, précise ce chercheur.

"Nous avons poussé les connaissances actuelles dans l'application de l'intelligence artificielle aux limites extrêmes en remplaçant les connaissances humaines empiriques par des données mathématiques", a précisé Jonathan Schaeffer.

Cet informaticien avait lancé le projet Chinook avec le but initial de gagner le championnat du monde de dames.

En 1990, il a obtenu le droit d'y participer. En 1992, Chinook a perdu en finale mais a gagné en 1994 devenant le premier logiciel à remporter un titre mondial dans tous les jeux objet d'une compétition. Cette victoire sans précédent est inscrite dans le livre Guinness Book des records.

Chinook est resté invaincu au championnat du monde jusqu'à sa mise "à la retraite" en 1997.

Mais Jonanthan Schaeffer souhaitait mettre au point un programme absolument imbattable et s'est remis au travail en 2001 pour atteindre cet objectif, considérant que les capacités des nouveaux ordinateurs s'étaient considérablement accrues.

"Percer toutes les combinaisons du jeu de dames a été mon obsession pendant près de vingt ans et il est très satisfaisant d'y parvenir", a relevé l'informaticien.

Il n'est pas encore question de s'attaquer à toutes les combinaisons du jeu d'échecs dont le nombre astronomique occuperait les ordinateurs d'aujourd'hui les plus puissants pendant plusieurs siècles, selon les scientifiques.

Il existe des programmes spécialisés aux échecs dont le premier est "Deep Blue" qu'a affronté le champion du monde du moment, Garry Kasparov, en 1996. Ce dernier a triomphé, mais pour perdre une année plus tard contre le successeur de Deep Blue, Deeper Blue.

Le poker est la dernière passion de Jonathan Schaeffer. Avec son logiciel de jeu Polaris, il devait affronter deux joueurs professionnels les 24 et 25 juillet à Vancouver (Canada) lors de la conférence annuelle de l'organisation pour la promotion de l'intelligence articielle

Jaap van Galen · Post by **Jaap van Galen** » Fri Jul 20, 2007 20:22

Interessante vraag is wel wat dit nu betekent voor denksporten. Uiteindelijk zal natuurlijk ook ons dammen worden "uitgeanalyseerd". Is dat het einde van een denksport, of zou je kunnen zeggen "die computer kunnen we toch niet evenaren, dus het blijft interessant" ?

Eric van Dusseldorp · Post by **Eric van Dusseldorp** » Fri Jul 20, 2007 20:34

Jaap van Galen wrote:Interessante vraag is wel wat dit nu betekent voor denksporten. Uiteindelijk zal natuurlijk ook ons dammen worden "uitgeanalyseerd". Is dat het einde van een denksport, of zou je kunnen zeggen "die computer kunnen we toch niet evenaren, dus het blijft interessant" ?

Dat laatste.
Denksport is vooral iets tussen mensen.

ildjarn · Post by **ildjarn** » Fri Jul 20, 2007 20:52

John van der Wiel heeft ooit gezegd (geen directe quote, maar het was zoiets) : "Laat die schaakcomputer alsjeblieft winnen van de wereldkampioen, dan kunnen we tenminste weer gewoon gezellig gaan schaken".

Jaap van Galen · Post by **Jaap van Galen** » Fri Jul 20, 2007 21:35

Eric van Dusseldorp wrote:
Jaap van Galen wrote:Interessante vraag is wel wat dit nu betekent voor denksporten. Uiteindelijk zal natuurlijk ook ons dammen worden "uitgeanalyseerd". Is dat het einde van een denksport, of zou je kunnen zeggen "die computer kunnen we toch niet evenaren, dus het blijft interessant" ?
Dat laatste.
Denksport is vooral iets tussen mensen.

Toch zal het invloed hebben. Ik kan me zoiets voorstellen bij het feit dat zeker bepaalde "ver weg" varianten zoals in de Keller door de computer verloren worden verklaard. De vraag zal zijn hoe snel, na hoeveel zetten, bepaalde varianten al als verloren kunnen worden "gezien" en wat de invloed zal zijn op het dammen. Zeker interessant wordt die vraag als de grenzen wat scherper worden, zoals b.v. bij een Delftse 6-4.

Jaap van Galen · Post by **Jaap van Galen** » Fri Jul 20, 2007 21:57

De volkskrant, 20-07-2007: wrote:

Jaap van den Herik, geen onbekende, heeft het toch over de doodsteek. Wij dammers moeten blijkbaar allemaal een kleinzoon krijgen om straks nog enig plezier te houden.

Bert Zwart · Post by **Bert Zwart** » Sun Jul 22, 2007 16:31

Alles wat een begin heeft, heeft een eind. Soms kan een einde ook mooi zijn. Mijn felicitaties aan het Chinook team.

Hoe de damwereld verder moet is vrij simpel. Als versie N is uitgeanalyseerd, ga je gewoon verder met versie N+1.

Jaap van Galen · Post by **Jaap van Galen** » Sun Jul 22, 2007 22:35

Alan Perlis wrote:Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it.

Bert Zwart wrote:Alles wat een begin heeft, heeft een eind. Soms kan een einde ook mooi zijn. Mijn felicitaties aan het Chinook team.
Hoe de damwereld verder moet is vrij simpel. Als versie N is uitgeanalyseerd, ga je gewoon verder met versie N+1.

Inderdaad, maar hopelijk slaan die checker-players 1 stap over en gaan ze direct naar versie N+2, ofwel lekker 10x10 spelen, dat zou mooi zijn.
Overigens een mooie quote van Alan Perlis.

Eric van Dusseldorp · Post by **Eric van Dusseldorp** » Mon Jul 23, 2007 08:22

Jaap van Galen wrote: Inderdaad, maar hopelijk slaan die checker-players 1 stap over en gaan ze direct naar versie N+2, ofwel lekker 10x10 spelen, dat zou mooi zijn.

En als het niet teveel gevraagd is, graag volgens de internationale regels.

Rein Halbersma · Post by **Rein Halbersma** » Fri Jul 27, 2007 23:25

Bert Zwart wrote:Alles wat een begin heeft, heeft een eind. Soms kan een einde ook mooi zijn. Mijn felicitaties aan het Chinook team.

Hoe de damwereld verder moet is vrij simpel. Als versie N is uitgeanalyseerd, ga je gewoon verder met versie N+1.

Voor wie anderhalf uur wil doden met wat nuttigers dan de Gouden Kooi, de Tour de France of andere banale bezigheden, hier is de presentatie die Jonathan Schaeffer hield over het Chinook project:

http://www.cs.ualberta.ca/~chinook/news/media.html

PDF en mp3 downloaden en tegelijk afspelen. Diepe buiging voor deze geweldige prestatie.

Bert Zwart · Post by **Bert Zwart** » Sun Jul 29, 2007 16:07

Eric van Dusseldorp wrote:
Jaap van Galen wrote: Inderdaad, maar hopelijk slaan die checker-players 1 stap over en gaan ze direct naar versie N+2, ofwel lekker 10x10 spelen, dat zou mooi zijn.
En als het niet teveel gevraagd is, graag volgens de internationale regels.

Hebben we nog twintig jaar, of minder?