Ribbroeken-plaginaat!

Onrust in computerschaakland: het programma Rybka is beschuldigd van plagiaat en de plagiateur Vasik Rajlich veroordeeld tot levenslange schorsing. De wortelbroeken hadden dit natuurlijk al vernomen via Slashdot, maar voor de musici en andere kunstenaars hiero doe ik het hier nog even over. Het leest als een spannend jongensboek: na hardnekkige geruchten gaat een team van dertig internationale specialisten in alle geheim aan de slag. Daarbij wordt de disassembler niet geschuwd. Na een jaar spitten is het bewijs compleet. En dat varieert van het lenen van tabellen en methodes, tot het regelrecht rippen van stukken (open source) code. Hoe ernstig is dit nu? Het is natuurlijk onsportief, en strijdig met de reglementen en statuten. Behalve de geldprijzen heeft ie er zakelijk ook nog financieel geld mee verdiend. Met andermans werk. Alle algoritmes zijn bekend, en de code is (voor een schaakprogrammeur) dus vrij triviaal. Maar het is moeilijk om het in een keer foutloos in te kloppen. En dat moet je dus wel zelf doen.

Een beetje achtergrond.
De eigenlijke methoden en technieken in het computerschaak zijn min of meer publiek domein; en alle schaakengines zullen deze toepassen op de een of andere manier. De basis van een engine is vrijwel altijd alpha-beta-search of een variant daarop. De kern van alpha-beta vormt de evaluatiefunctie. Die probeert een kwantificatie te maken van hoeveel een bepaalde stelling waard is. In het simpelste geval is dat de materiaalwaarde (pion=1, dame=8, koning is oneindig), maar er zijn nog bonuspunten te behalen voor mobiliteit en positie, of strafpunten voor bijvoorbeeld dubbelpionnen. Dat is allemaal prachtig te tunen. Die evaluatie is nodig omdat je de stelling niet veertig zetten diep kunt doorrekenen, daarvoor ontbreekt de rekenkracht. Vrijwel alle engines hebben ook een transpositietabel: een hashtable waarin resultaten van eerdere berekeningen opgeslagen worden.

Geavanceerdere schaakengines hebben ook nog een openingsboek en een eindspelboek aan boord. Dat is handig, omdat je de evaluatie van de openingszetten al precalculated vast hebt liggen, en zodra je in het eindspelenboek terecht komt ligt de evaluatie al vast (winst,verlies of remise). Je hoeft dus minder diep te rekenen.

Het netto effect van het toevoegen van openings en eindspelenboeken is trouwens dat het tunen van de evaluatiefunctie minder belangrijk wordt.

gepost door Wildplasser, beroepsweigeraar op 03-07-2011 om 12:04 | 18 reacties | 2 |

Share|

Doet 'Deep blue' nog iets anders dan die schaakprogramma's, of is deep blue gewoon precies hetzelfde alleen dan met veel meer hardware ertegenaangegooid?

lulde gronk

op 02-07-2011 20:00:56 | # | 0 |

Deep blue was IIRC standaard spul plus heul veul hardware. Ze hadden zelfs de evaluatiefunctie in hardware gebakken, waardoor die effectief maar een instructie (of zo) kostte. De evaluatie was wel machinematig getuned, daar hadden ze een apart voortraject voor met een DEC Alpha. Daar is nog een paper over van Hsu, maar die kan ik even niet vinden.

lulde Wildplasser, beroepsweigeraar

op 02-07-2011 20:53:01 | # | 0 |

hiero

lulde Wildplasser, beroepsweigeraar

op 02-07-2011 20:56:25 | # | 0 |

ik begrijp het niet helemaal. Wát heeft-ie nou gejat? Heeft hij gewoon code gekopieerd en geplakt, waar hij geacht werd om het zelf te doen? Van die openingsboeken?

lulde Horror vacui

op 03-07-2011 14:40:37 | # | 0 |

@horror:
1) Ja.
2) Nee

Hij heeft in wezen twee wetten overschreden: (1) de toernooireglementen, die vereisen dat het een origineel werk is, en dat alle auteurs credit krijgen (2) de (open-source) licenties van crafty en fruit, die copieren en wijzigen toestaan, mits het open-source blijft, credits gegeven worden, en er geen sprake van geldelijk gewin is.

Ik heb in het vonnis nergens iets kunnen vinden over openingsboeken. Misschien valt dat bij een goede evaluatie allemaal wel binen de search-horizon van ~10 ply? Hij heeft trouwens wel meerdere evaluatieconstanten-tabellen, geschakeld door de fase van het spel. (het aantal stukken dat er nog op het bord is)

lulde Wildplasser, beroepsweigeraar

op 03-07-2011 15:04:55 | # | 0 |

[samenzweringsmodus]Men was gewoon bang voor Rybka, want dat is natuurlijk de reden waarom men met reverse engineering begonnen is. Daarna zijn de ontdekte trucjes ingebracht in open source software, en pas daarna onthuld, en kon Rybka aan de schandpaal genageld worden. Niet vertellen dat je 't van mij hebt, hè?[/samenzweringsmodus]

lulde Illuminatus Magnus

op 03-07-2011 17:12:08 | # | 1 |

Het is pas interessant wanneer je de evalutie funtie wel kan blijven doorrekenen, maar ja..

/strategie /loop

lulde Hollywood -part time Britt consultant- !

op 03-07-2011 17:27:57 | # | 0 |

Copy pasta waar de honden geen brood van lusten. Zelfs uncalled functions staan (in dezelfde volgorde) in het Frankenstein script van die zelfgekroonde koning wortel.

lulde zeg maar gewoon Garibaldi

op 03-07-2011 20:09:07 | # | 0 |

Inderdaad, dead code was ook included. Ook de fouten (rare parser, dubbele initialisatie) zijn meegecopieerd. Overduidelijk een smoking gun.

Ik heb even nagezocht: zowel crafty als fruit blijken een openingsboek te hebben. Waarom ze die niet geverifieerd hebben? Misschien dat AB-searcht en evaluatie het makkelijkt te vinden zij: bij een profile springen ze er uit.
Maar het blijft een monnikenwerk om eea boven tafel te krijgen.

lulde Wildplasser, beroepsweigeraar

op 03-07-2011 20:23:55 | # | 0 |

Eh, ik begrijp even niet wat je bedoelt.

/Reetmodus

lulde Ghettoforce

op 03-07-2011 20:43:15 | # | 2 |

Jesses, moeten we allemaal een wortelbroek worden ofzo? Hier dan:
#ifndef __HCI_CORE_H
#define __HCI_CORE_H
#include
/* HCI upper protocols */
#define HCI_PROTO_L2CAP 0
#define HCI_PROTO_SCO 1
/* HCI Core structures */
struct inquiry_data {
bdaddr_t bdaddr;
__u8 pscan_rep_mode;
__u8 pscan_period_mode;
__u8 pscan_mode;
__u8 dev_class[3];
__le16 clock_offset;
__s8 rssi;
__u8 ssp_mode;
};

lulde Valentijn, namens de gehele Nederlandse bevolking

op 03-07-2011 22:27:36 | # | 0 |

Bedankt Valentijn. Het is me nu spontaan in een keer bijna helemaal helder.
Weet je zeker dat die die _u8 dev_class[3] geen [2] moet zijn?

lulde Nick Changez -

op 03-07-2011 22:55:01 | # | 0 |

Het bewijs voor plaginaat lijkt me onontkoombaar.

Toch vraag ik mij het volgende af. Je kopieert de code van programma X en Y en vervolgens wint jouw programma keer op keer van zowel X als Y: The 1st places and World Computer Chess Champion titles awarded to the program Rybka in the 2007, 2008, 2009 and 2010 WCCCs are hereby annulled,.

Dan moet je m.i. toch iets significants verschillend toegevoegd hebben - anders gedragen die algorithmes zich niet meetbaar verschillend.

Of speelden X en Y niet (meer) mee? Waarom niet? Waren ze niet goed genoeg? (Wat de vraag over waarom Rybka dan wel alleen maar interessanter maakt).

lulde marjolein

op 03-07-2011 22:59:06 | # | 2 |

Vasik Rajlich is grootmeester. En behalve programmeren kan ie ook nog goed tunen.

Hij heeft het programma gewoon goed getuned, misschien wel mbv bestaande prof-partijen. Hier wordt je wegwijs gemaakt in de zieleroerselen van een tunende schaakprogrammeur.

De meeste diffs in het verslag hebben trouwens betrekking op Rybka-1.0. Dat was kennelijk een regelrechte rip-off, met wat obfuscatie. Of ie daarna nog iets substantieels heeft toegevoegd is mij onduidelijk. Da afstand tussen Rybka en de concurrentie is 100-150 ELO-punten, en dat vind ik veel voor alleen een beetje tunen. ELO rating is aan de bovenkant van het spectrum weinig betrouwbaar, omdat er daar minder tegenstanders zijn. Misschien dat je met wat extra corner cases net voldoende kunt winnen, kweeniet.

lulde Wildplasser, beroepsweigeraar

op 03-07-2011 23:32:52 | # | 0 |

@Nick Changez: nee. Kwa alignment wordt er bij "__u8 dev_class[2]" toch een padding byte toegevoegd.

lulde Wildplasser, beroepsweigeraar

op 03-07-2011 23:44:13 | # | 0 |

Da afstand tussen Rybka en de concurrentie is 100-150 ELO-punten, en dat vind ik veel voor alleen een beetje tunen.

Dat dus. Met name omdat je alleen maar in rating kunt stijgen als je wint van een spelert met een hogere ranking. En de hoeveelheid vooruitgang díe je dan boekt schaalt omgekeerd evenredig met de hoogte van je eigen ranking. Het is een beetje als met versnellen tot de lichtsnelheid: hoe dichter je er bij komt hoe onevenredig meer energie je er in moet stoppen om er nóg dichter bij te komen.

lulde marjolein

op 03-07-2011 23:45:26 | # | 1 |

Dat is een kwestie van aging. Na verloop van tijd tellen oude resultaten minder mee, en heeft de beste spelert de hoogste reeting. Ik dacht dat je bij 100 ELO verschil een winstkans van 10:80 hebt ofzo.

Maar het kan goed dat ie ook nog andere dingen heeft geoptimaliseerd hier en daar een cache-prefetch, of een hogere locality-of-reference kan wel 10% meer Nps winst opleveren. Een andere CPU slurpert is trouwens de move-generator; misschien dat daar ook nog iets te besparen valt. (ik ben de move-generator nauwelijks tegengekomen in de verslagen).
En nog een andere mogelijkheid is verbeterd parallelisme.

lulde Wildplasser, beroepsweigeraar

op 03-07-2011 23:57:23 | # | 0 |

@Marjo: Verbeteringen in volgende versies: hier B3 (pag 22 ev) . Hij heeft de alpha-beta -variant gewijzigd naar MTD(f), en wat aanpassingen aan de hashtables verricht. Dat laatste zou er op kunnen wijzen dat ie de hashtable hergebruikt bij de volgende zet, en tijdens pondering.
Men heeft doorgaans de neiging de hashtables na iedere zet te ruimen, omdat de alpha-beta estimates afhangen van de startpositie, en de boekhouding heel tricky wordt (het resico is dat er bij hergebruik teveel gepruned wordt, en er dus varianten verworpen worden). Maar als het lukt levert het bijna 1+1 ply winst op, goed voor 100 ELO.

*wortelbroek in de wasmachine doet*

lulde Wildplasser, beroepsweigeraar

op 04-07-2011 13:48:21 | # | 1 |

Om te kunnen reageren moet je ingelogd zijn.

Inloggen en Registreren

Nu op Retecool Goldmember

Wrong Cops

Mortuarium Everest

WAT zegt u over orka's?

Zo, en dan nu even 40 miljard bij elkaar sprokkelen.

Stelling van de dag

15-05-2012: Volkert van der Graaf moet gewoon vrijkomen na twee derde van zijn straf, 68 reactie(s), voor, tegen.

09-05-2012: Maar wat vindt U dan?, 43 reactie(s), voor, tegen.

18-04-2012: Oproep tot boycot door Tweede Kamer van TV programma is prima, 29 reactie(s), voor, tegen.

17-04-2012: Olifanten doodschieten is prima, 39 reactie(s), voor, tegen.

28-02-2012: Journalistiek is oorlog?, 107 reactie(s), voor, tegen.

Nu in het forum

Welkom in Rotterdam!

Populistisch taalgebruik en insluipers

Afschaffen onbelaste reiskostenvergoeding.

Spamhoer wil aandacht? Spamhoer krijgt aandacht.

Ribbroeken-plaginaat!