Revue 1994 - pagina 112

rechthoekig bord bestaande uit zeven kolommen van elk zes posities hoog. Om de beurt gooien de spelers van boven af een schijf van de eigen kleur in een kolom. Degene die het eerst horizontaal, verticaal of diagonaal vier schijven aaneengesloten op een rij heeft, wint. Op de middelbare school heeft Victor Allis toen een programma voor Vier op een Rij geschreven. In de loop van zijn studie Informatica aan de Vrije Universiteit heeft hij dat programma regelmatig verbeterd en is hij in 1 988 er op afgestudeerd. In zijn scriptie toont hij onder meer aan dat er bij Vier op een Rij voor de speler die begint een winnende strategie bestaat, dat wil zeggen dat die speler altijd kan winnen. Het computerprogramma dat gebaseerd is op die strategie en dat heeft meegedaan op de Computer Olympiade van 1989 won glansrijk. Het spel is toen van de lijst van toegelaten spelen geschrapt omdat de aardigheid eraf was. Op 23 september promoveerde Victor aan de Rijksuniversiteit Limburg op het proefschrift getiteld 'Searching for Solutions in Games and Artificial Intelligence'. "Vooruitgang in de Kunstmatige Intelligentie wordt gehinderd door een aantal obstakels, dat wil zeggen dingen waarvan nog niet goed duidelijk is hoe ze moeten worden aangepakt", zegt Victor. Een voorbeeld van zo'n obstakel is het feit dat een mens bij het begrijpen van natuurlijke taal altijd gebruikt maakt van allerlei niet uitgesproken achtergrondkennis. Een programma zal alleen een natuurlijke taal goed kunnen begrijpen als het op de een of andere manier ook over die achtergrondkennis beschikt. Met opzet beperkt hij zich bij zijn onderzoek tot situaties waar dit obstakel zich niet voordoet. Bij denkspelen hebben we te maken met een precies gedefinieerde zaak waarbij vage achtergrondkennis

42

geen rol lijkt te spelen. We kunnen ons dan dus concentreren op andere problemen. Toch doen er zich ook hier allerlei moeilijkheden voor. Het vinden van oplossingen voor die moeilijkheden is de uitdaging in het onderzoek. Omdat er door anderen in de wereld aan programma's wordt gewerkt voor bekende spelen als schaken, dammen, enzovoort heeft hij een aantal minder bekende spelen bestudeerd. Tijdens zijn onderzoek heeft hij winnende strategieën voor Qubic en Go-Moku gevonden. Sinds 1991 doet Qubic dan ook niet meer mee bij de Olympiade en in 1992 werd Co-Moku geschrapt. Voor Awari heeft hij samen met IVlaarten van der Meulen een programma geschreven dat bijna altijd van menselijke tegenstanders wint, maar voor dat spel is nog geen altijd winnende strategie gemaakt. Bij het ontwikkelen van een winnende strategie probeert hij strategische regels op te stellen door goed te kijken hoe ervaren menselijke spelers een spel spelen. Bij Vier op een Rij vond hij negen van zulke regels en kon hij ook laten zien dat in allerlei stellingen, waaronder de beginstelling, het gebruik van die regels altijd tot winst zou moeten leiden. In zijn proefschrift gaat hij deels ook op die manier te werk. Verder beschrijft hij twee nieuwe zoek-strategieën. De kunst is namelijk om het aantal mogelijkheden dat door de computer moet worden bekeken zo sterk mogelijk terug te brengen. Die zoek-strategieën zijn ook elders binnen de Kunstmatige Intelligentie bruikbaar.

Europese Kampioenschap Programmeren Op 1 2 november vindt op de Vrije Universiteit het Europees kampioenschap programmeren (EKP) voor universiteiten plaats. Dit kampioenschap is één van de zestien voorronden van het door de ACM in Amerika georganiseerde wereldkampioenschap. Microsoft is sponsor van deze programmeerwedstrijden. De eerste plaats op het Europees kampioenschap geeft recht op deelname aan het WK programmeren. In de voorgaande jaren is het EKP georganiseerd door de Technische Universiteit Eindhoven (1988, 1989, 1990), Rijksuniversiteit Cent (België; 1 991, 1 992) en Swansea (Wales; 1993). Nederlandse teams hebben sinds hun eerste deelname in 1985 altijd een zeer behoorlijk resultaat neergezet. Sinds 1986 heeft minimaal één Nederlands team bij de eerste twee gezeten. De afgelopen twee jaar waren zelfs de eerste vier teams uit Nederland afkomstig. Op het WK zijn de resultaten zeer redelijk geweest. Regelmatig is een team bij de eerste tien geëindigd, met als hoogtepunten een tweede (Vrije Universiteit 1991) en twee vijfde plaatsen (Vrije Universiteit 1994; Technische Universiteit Eindhoven 1990). Nog nooit heeft een team uit een andere Europees land deze resultaten overtroffen.

Nadere informatie: email <acm@cs.vu.nl>, tel. 020 - 444 7739 of fax 020 - 444 7653. 4

Benoemingen Prof.dr A.S. Tanenbaum, hoogleraar Informatica aan de faculteit, is benoemd tot lid van de Koninklijke Nederlandse Akademie van Wetenschappen bij de afdeling Natuurkunde.

vrije Universiteit

amsterdam

Revue

Deze tekst is geautomatiseerd gemaakt en kan nog fouten bevatten. Digibron werkt voortdurend aan correctie. Klik voor het origineel door naar de pdf. Voor opmerkingen, vragen, informatie: contact.

Op Digibron -en alle daarin opgenomen content- is het databankrecht van toepassing. Gebruiksvoorwaarden. Data protection law applies to Digibron and the content of this database. Terms of use.

Printen