Monte-Carlo-fakeresés

Az informatikában a Monte-Carlo-fakeresés (angolul rövidítve: MCTS) egy heurisztikus keresési algoritmus bizonyos típusú döntési folyamatokhoz, leginkább a társasjátékokat játszó szoftverekben használtakhoz. Ebben az összefüggésben az MCTS-t a játékfa megoldására használják.

Az MCTS-t 2016-ban neurális hálózatokkal kombinálták a számítógépes góhoz. Ezt használták más társasjátékokban is, például a sakkban és a sógiban, hiányos információkat tartalmazó játékokban, például a bridzsben és a pókerben, valamint a körökre osztott stratégiai videojátékokban (mint például a Total War: Rome II implementációjában a magas szintű kampány AI-jában). Az MCTS-t önvezető autókban is alkalmazták, például a Tesla Autopilot szoftverben.

Történet

Monte-Carlo-módszer

Az 1940-es évekre nyúlik vissza a Monte-Carlo-módszer, amely véletlenszerű mintavételt alkalmaz olyan determinisztikus problémákra, amelyeket más megközelítéssel nehéz vagy lehetetlen megoldani.^[1] 1987-es PhD disszertációjában Bruce Abramson a szokásos statikus kiértékelési funkció helyett a végére kombinálta a minimax keresést egy véletlenszerű játéklejátszásokon alapuló várható eredmény modellel. Abramson elmondta, hogy a várható eredménymodell "precíznek, pontosnak, könnyen becsülhetőnek, hatékonyan kiszámíthatónak és tartományfüggetlennek bizonyult".^[2] Mélyrehatóan kísérletezett a tic-tac-toe-val, majd az Othello és a sakk gépi kiértékelési funkcióival.

Az ilyen módszereket aztán W. Ertel, J. Schumann és C. Suttner 1989-ben az automatizált tételbizonyítás területén vizsgálta és sikeresen alkalmazta a heurisztikus keresésre, javítva ezzel a nem informált kereső algoritmusok, mint például a szélességi keresés, a mélység keresés vagy az iteratív mélyítés exponenciális keresési idejét.

B. Brügmann 1992-ben alkalmazta először egy goprogramban. 2002-ben Chang és társai a Markov-döntési folyamatok modelljére kidolgozott Adaptive Multi-stage Sampling (AMS) algoritmusukban "adaptív" mintavételi döntésekkel "rekurzív kigurulás és visszalépés" ötletét javasolták. Az AMS volt az első olyan munka, amely a mintavételezett/szimulált (Monte-Carlo-) fák építésénél az UCB-alapú feltárás és kiaknázás ötletét vizsgálta, és ez volt az UCT (Upper Confidence Trees) fő magja.

Monte-Carlo-fakeresés (MCTS)

A legjobb goprogramok értékelése a KGS szerveren 2007 óta. 2006 óta az összes legjobb program a Monte-Carlo-fakeresőt használja.^[3]

Rémi Coulom 2006-ban, ezen elődök által inspirálva, leírta a Monte-Carlo-módszer alkalmazását a játékfakeresésre, és megalkotta a Monte-Carlo-fakeresés nevet, L. Kocsis és Cs. Szepesvári kidolgozta az UCT (Upper Confidence bounds applied to Trees) algoritmust, S. Gelly és társai pedig az UCT-t implementálták MoGo programjukban. A MoGo 2008-ban elérte a dan (mester) szintet 9×9-es góban, és a Fuego program 9×9-es góban erős amatőr játékosok ellen kezdett győzni.

2012 januárjában a Zen program 3:1-re nyert egy 19×19-es táblán játszott gomérkőzésen egy 2 danos amatőr játékos ellen. A Google Deepmind fejlesztette ki az AlphaGo programot, amely 2015 októberében az első olyan számítógépes goprogram lett, amely egy teljes méretű 19x19-es táblán hátrány nélkül legyőzött egy profi gojátékost. 2016 márciusában az AlphaGo tiszteletbeli 9 dan (mester) fokozatot kapott 19×19-es góban, mivel egy ötjátszmás mérkőzésen négy az egyhez arányban legyőzte Lee Sedolt. Az AlphaGo jelentős előrelépést jelent a korábbi goprogramokhoz képest, valamint mérföldkövet jelent a gépi tanulásban, mivel Monte-Carlo-fakeresést használ mesterséges neurális hálózatokkal (egy mély tanulási módszer) a lépésválasztáshoz és az értékhez, így hatékonysága messze felülmúlja a korábbi programokat.

Az MCTS algoritmust olyan programokban is használták, amelyek más társasjátékokat játszanak (például Hex,^[4] Havannah,^[5] Game of the Amazons,^[6] és Arimaa^[7]), valós idejű videojátékokban (például Ms. Pac-Man^[8][9] és Fable Legends^[10]), és nem determinisztikus játékok (mint például skat,^[11] póker,^[12] Magic: The Gathering,^[13] vagy Settlers of Catan^[14]).

Működési elv

Az MCTS fókuszában a legígéretesebb lépések elemzése áll, a keresési tér véletlenszerű mintavétele alapján bővítve a keresési fát. A Monte-Carlo-fakeresés alkalmazása a játékokban sok kijátszáson, más néven roll-outon alapul. Minden egyes játékmenetben a játékot a legvégéig játsszák véletlenszerű lépések kiválasztásával. Az egyes kijátszások végeredményét ezután a játékfa csomópontjainak súlyozására használjuk, hogy a jövőbeli kijátszások során nagyobb valószínűséggel válasszunk jobb csomópontokat.

A kijátszások használatának legalapvetőbb módja az, hogy az aktuális játékos minden egyes legális lépése után ugyanannyi kijátszást alkalmazunk, majd kiválasztjuk azt a lépést, amelyik a legtöbb győzelemhez vezetett. Ennek az úgynevezett Pure Monte Carlo Game Search (tiszta Monte-Carlo-játékkeresés) módszernek a hatékonysága gyakran nő az idő múlásával, mivel több kijátszást rendelünk azokhoz a lépésekhez, amelyek a korábbi kijátszások szerint gyakran vezettek az aktuális játékos győzelméhez. A Monte-Carlo-fakeresés minden egyes fordulója négy lépésből áll:

• Kiválasztás: Kezdje az R gyökértől, és válassza ki az egymást követő gyermek csomópontokat, amíg el nem éri az L levél csomópontot. A gyökér az aktuális játékállapot, a levél pedig minden olyan csomópont, amelynek potenciális gyermeke van, és amelyről még nem indult el a szimuláció (playout). Az alábbi szekcióban többet mondunk a gyermekcsomópontok kiválasztásának olyan előfeszítési módjáról, amely lehetővé teszi, hogy a játékfa a legígéretesebb lépések felé terjeszkedjen, ami a Monte-Carlo-fakeresés lényege.
• Bővítés: Hacsak L nem döntő módon (pl. győzelem/veszteség/döntetlen) nem fejezi be a játékot bármelyik játékos számára, hozzon létre egy (vagy több) gyermek csomópontot, és ezek közül válassza ki a C csomópontot. A gyermek csomópontok az L által meghatározott játékhelyzetből kiinduló bármely érvényes lépés.
• Szimuláció: Végezzen el egy véletlenszerű lejátszást a C csomópontból. Ezt a lépést néha lejátszásnak (playout) vagy közzétételnek (rollout) is nevezik. A kijátszás lehet olyan egyszerű, mint az egységes véletlenszerű lépések kiválasztása, amíg a játszma el nem dől (például a sakkban a játszma megnyerése, elvesztése vagy döntetlen).
• Visszaterjesztés: Használja a lejátszás eredményét a C-től R-ig tartó útvonal csomópontjaiban lévő információk frissítésére.

Monte-Carlo-fakeresés lépése

Ez a grafikon egy döntés lépéseit mutatja, minden egyes csomópont a győzelmek és az összes kijátszás arányát mutatja a játékfa adott pontjától a játékos számára, akit a csomópont képvisel. A kiválasztási diagramon a fekete éppen lépni készül. A gyökércsomópont azt mutatja, hogy ebből az állásból eddig 21 kijátszásból 11 győzelem jutott a fehérnek. Ez kiegészíti az alatta lévő három fekete csomópont mentén látható 10/21 fekete győzelmet, amelyek mindegyike egy-egy lehetséges fekete lépést jelent. Megjegyzendő, hogy ez a gráf nem követi az alább ismertetett UCT algoritmust.

Ha a fehér elveszíti a szimulációt, akkor a kiválasztás mentén lévő összes csomópont szimulációs száma növekszik (a nevező), de közülük csak a fekete csomópontok kaptak győzelmet (a számláló). Ha ehelyett a fehér nyer, a kiválasztás mentén lévő összes csomópont továbbra is növeli a szimulációszámát, de közülük csak a fehér csomópontok kapnak győzelmet. Azokban a játékokban, ahol döntetlen is lehetséges, a döntetlen hatására mind a fekete, mind a fehér számlálója 0,5-tel, a nevezője pedig 1-gyel növekszik. Ez biztosítja, hogy a kiválasztás során minden játékos választása az adott játékos számára legígéretesebb lépések felé bővüljön, ami tükrözi minden játékos azon célját, hogy maximalizálja lépésének értékét.

A keresési körök addig ismétlődnek, amíg a lépésre szánt idő tart. Ezután a legtöbb szimulációt (azaz a legnagyobb nevezőt) tartalmazó lépés lesz a végső válasz.

Tiszta Monte-Carlo-játékkeresés

Ez az alapeljárás bármely olyan játékra alkalmazható, amelynek pozíciói szükségszerűen véges számú lépéssel és véges hosszúsággal rendelkeznek. Minden egyes álláshoz meghatározzuk az összes lehetséges lépést: k véletlenszerű játszmát játszunk le a végsőkig, és feljegyezzük a pontszámokat. A legjobb pontszámhoz vezető lépést választjuk ki. A döntetleneket igazságos pénzfeldobással oldjuk a tiszta Monte-Carlo-játékkeresés számos véletlen elemeket tartalmazó játékban erős játékot eredményez, mint például az EinStein würfelt nicht! játékban. Az optimális játékhoz konvergál (ahogy k a végtelen felé közelít) a véletlenszerű fordulósorrenddel rendelkező táblafeltöltő játékokban, például a Hex játékban véletlenszerű fordulósorrenddel.

Feltárás és kiaknázás

A gyermekcsomópontok kiválasztásának fő nehézsége a magas átlagos nyerési aránnyal rendelkező lépések utáni mély változatok kihasználása és a kevés szimulációval rendelkező lépések feltárása közötti egyensúly fenntartása. A játékokban a kihasználás és a felfedezés egyensúlyának megteremtésére szolgáló első képletet, az UCT-t (Upper Confidence Bound 1 fákra alkalmazva) Kocsis Levente és Szepesvári Csaba vezette be. Az UCT az Auer, Cesa-Bianchi és Fischer által levezetett UCB1 képleten és a bizonyíthatóan konvergens AMS (Adaptive Multi-stage Sampling) algoritmuson alapul, amelyet először Chang, Fu, Hu és Marcus alkalmazott többlépcsős döntéshozatali modellekre (konkrétan Markov-döntési folyamatokra). Kocsis és Szepesvári azt javasolják, hogy a játékfa minden egyes csomópontjában azt a lépést válasszuk ki, amelyre a kifejezés ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}}$ a legnagyobb értékkel bír. Ebben a képletben:

• w_i az i-edik lépés után a figyelembe vett csomópont győzelmeinek számát jelöli
• n_i az i-edik lépés után a figyelembe vett csomópontra vonatkozó szimulációk számát jelöli.
• N_i a vizsgált csomópont szülői csomópontja által végrehajtott i-edik lépés utáni szimulációk teljes számát jelöli.
• c a feltárási paraméter elméletileg egyenlő √2-vel; a gyakorlatban általában empirikusan választják meg.

A fenti képlet első összetevője a kihasználásnak felel meg; ez magas a magas átlagos nyerési aránnyal rendelkező lépések esetében. A második összetevő a felfedezésnek felel meg; a kevés szimulációval rendelkező lépéseknél magas.

A Monte-Carlo-fakeresés legtöbb modern megvalósítása az UCT valamilyen változatán alapul, amely a Chang és munkatársai által bevezetett AMS szimulációs optimalizálási algoritmusra vezeti vissza az értékfüggvény becslését a véges horizontú Markov döntési folyamatokban (MDP). (2005) in Operations Research. (Az AMS volt az első olyan munka, amely feltárta az UCB-alapú feltárás és kiaknázás ötletét a mintavételezett/szimulált (Monte-Carlo-) fák felépítésében, és ez volt az UCT fő magva.)

Előnyök és hátrányok

Bár bebizonyosodott, hogy a lépések kiértékelése a Monte-Carlo-fakeresésben a minimaxhoz konvergál, a Monte-Carlo-fakeresés alapváltozata csak az úgynevezett "Monte Carlo Perfect" játékokban konvergál. A Monte-Carlo-fakeresés azonban jelentős előnyöket kínál az alfa-béta metszéssel és hasonló, a keresési teret minimalizáló algoritmusokkal szemben.

A tiszta Monte-Carlo-fakeresésnek nincs szüksége explicit kiértékelő függvényre. A keresési tér (azaz a megengedett lépések generálása egy adott pozícióban és a játék végi feltételek) feltárásához elegendő a játék mechanikájának egyszerű végrehajtása. Mint ilyen, a Monte-Carlo-fakeresés alkalmazható olyan játékokban, amelyeknek nincs kidolgozott elmélete, vagy általános játékmenetben.

A Monte-Carlo-fakereső játékfa aszimmetrikusan növekszik, mivel a módszer az ígéretesebb részfákra koncentrál. Így jobb eredményeket ér el, mint a klasszikus algoritmusok a magas elágazási tényezővel rendelkező játékokban.

Hátránya, hogy bizonyos pozíciókban lehetnek olyan lépések, amelyek felületesen erősnek tűnnek, de valójában egy finom játszmavonalon keresztül veszteséghez vezetnek. Az ilyen "csapdaállapotok" alapos elemzést igényelnek a helyes kezeléshez, különösen, ha szakértő játékos ellen játszunk, az MCTS azonban a szelektív csomópontbővítés politikája miatt nem biztos, hogy "látja" az ilyen vonalakat. Úgy vélik, hogy részben ez lehetett az oka annak, hogy az AlphaGo a Lee Sedol elleni negyedik játszmában vereséget szenvedett. Lényegében a keresés megkísérli a kevésbé releváns szekvenciák selejtezését. Bizonyos esetekben egy játszma egy nagyon speciális játszmavonalhoz vezethet, amely jelentős, de a fa metszésekor figyelmen kívül hagyják, és ezért ez az eredmény "kikerül a keresés radarjáról".

Fejlesztések

A keresési idő lerövidítésére az alapvető Monte-Carlo-fakeresési módszer különböző módosításait javasolták. Egyesek szakterület specifikus szakértői tudást használnak, mások nem.

A Monte-Carlo-fakeresés használhat könnyű vagy nehéz lejátszást. A könnyű lejátszások véletlenszerű lépésekből állnak, míg a nehéz lejátszások különböző heurisztikákat alkalmaznak a lépések kiválasztásának befolyásolására. Ezek a heurisztikák felhasználhatják a korábbi kijátszások eredményeit (pl. az utolsó jó válasz heurisztika) vagy az adott játékra vonatkozó szakértői ismereteket. Például sok goprogramban a tábla egy részén található bizonyos kőminták befolyásolják az adott területre való lépés valószínűségét. Paradox módon a szimulációkban való szuboptimális játék néha összességében erősebb játékra késztet egy Monte-Carlo-fakereső programot.

Hane (ellenfél köveket körülvevő) minták, amelyeket a MoGo program a játék során használ. Fekete és fehér esetében is előnyös, ha követ tesz a középső négyzetre, kivéve a jobb szélső mintát, ahol csak a feketét részesíti előnyben.^[15]

A játékfa építése során a tartományspecifikus ismeretek felhasználhatók egyes változatok kiaknázásának elősegítésére. Az egyik ilyen módszer az egyes gyermekcsomópontok létrehozásakor nem nulla priort rendel a megnyert és a lejátszott szimulációk számához, ami mesterségesen megemelt vagy csökkentett átlagos nyerési arányt eredményez, ami miatt a csomópontot gyakrabban, illetve ritkábban választják ki a kiválasztási lépésben. Egy kapcsolódó, progresszív torzításnak nevezett módszer lényege, hogy az UCB1 képlethez hozzáadunk egy ${\displaystyle {\frac {b_{i}}{n_{i}}}}$ elemet, ahol bi az i-edik lépés heurisztikus pontszáma.^[16]

Az alapvető Monte-Carlo-fakeresés elegendő információt gyűjt össze ahhoz, hogy csak sok kör után találja meg a legígéretesebb lépéseket; addig mozgásai lényegében véletlenszerűek. A RAVE (Rapid Action Value Estimation) használatával a játékok bizonyos osztályaiban ez a felfedező szakasz jelentősen lecsökkenhet.^[17] Ezekben a játékokban a mozdulatsorok permutációi ugyanabba a pozícióba vezetnek. Jellemzően olyan társasjátékok, amelyekben egy mozdulat egy darab vagy egy kő elhelyezésével jár a táblán. Az ilyen játékokban az egyes lépések értékét gyakran csak kis mértékben befolyásolják más lépések.

A RAVE-ben egy adott N csomóponthoz tartozó játékfa Ci gyermekcsomópontjai nemcsak az N csomópontban megkezdett játszmák győzelmi statisztikáit tárolják, hanem az N csomópontban és alatta megkezdett összes játszma győzelmi statisztikáit is, ha azok tartalmazzák az i lépést (akkor is, ha a lépést a fában játszották le, az N csomópont és egy játszma között). Ily módon a fa csomópontjainak tartalmát nemcsak az adott pozícióban azonnal kijátszott lépések befolyásolják, hanem a később kijátszott ugyanilyen lépések is.

RAVE a tic-tac-toe példáján. A piros csomópontokban a RAVE statisztikák a b1-a2-b3 szimuláció után frissülnek.

RAVE alkalmazásakor a kiválasztási lépés kiválasztja azt a csomópontot, amelyre a módosított UCB1 képlet szerint ${\displaystyle (1-\beta (n_{i},{\tilde {n}}_{i})){\frac {w_{i}}{n_{i}}}+\beta (n_{i},{\tilde {n}}_{i}){\frac {{\tilde {w}}_{i}}{{\tilde {n}}_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}}$ a legnagyobb értékkel rendelkezik. Ebben a képletben ${\displaystyle {\tilde {w}}_{i}}$ és ${\displaystyle {\tilde {n}}_{i}}$ az i. lépést tartalmazó nyertes kijátszások számát és az i. lépést tartalmazó összes kijátszás számát jelöli, és a${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ függvénynek közel egynek kell lennie viszonylag kicsi és közel nullának viszonylag nagy ${\displaystyle n_{i}}$ és ${\displaystyle {\tilde {n}}_{i}}$ esetén. A sok formula közül az egyik ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ függvénynek, amelyet D. Silver javasolt, azt mondja, hogy kiegyensúlyozott pozíciókban vehetünk ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})={\frac {{\tilde {n}}_{i}}{n_{i}+{\tilde {n}}_{i}+4b^{2}n_{i}{\tilde {n}}_{i}}}}$, ahol b egy empirikusan választott konstans.

A Monte-Carlo-fakeresésben használt heurisztikák gyakran sok paramétert igényelnek. Vannak automatizált módszerek a paraméterek beállítására a nyerési arány maximalizálása érdekében.

A Monte-Carlo-fában végzett keresést egyszerre több szál vagy folyamat is végrehajthatja. Párhuzamos végrehajtásának számos alapvetően eltérő módszere létezik:^[18]

• Levélpárhuzamosítás, azaz sok játék párhuzamos végrehajtása a játékfa egy leveléből.
• Gyökérpárhuzamosítás, azaz független játékfák párhuzamos felépítése és a lépés végrehajtása az összes ilyen fa gyökérszintű ágai alapján..
• Fapárhuzamosítás, azaz ugyanazon játékfa párhuzamos építése, az adatok egyidejű írástól való védelme akár egy, globális mutexszel, akár több mutexszel, akár nem blokkoló szinkronizálással.

Jegyzetek

1. Nicholas (1949. december 7.). „The monte carlo method”. Journal of the American Statistical Association 44 (247), 335–341. o. DOI:10.1080/01621459.1949.10483310. PMID 18139350. 
2. Abramson, Bruce. The Expected-Outcome Model of Two-Player Games. Technical report, Department of Computer Science, Columbia University (1987). Hozzáférés ideje: 2013. december 23. 
3. Sensei's Library: KGSBotRatings. (Hozzáférés: 2012. május 3.)
4. Broderick Arneson (2009. június 1.). „MoHex Wins Hex Tournament”. ICGA Journal 32 (2), 114–116. o. DOI:10.3233/ICG-2009-32218. 
5. Timo Ewalds. Playing and Solving Havannah. Master's thesis, University of Alberta (2011) 
6. Richard J. Lorentz. Amazons Discover Monte-Carlo, Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings, H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.), Springer, 13–24. o. (2008). ISBN 978-3-540-87607-6 
7. Tomáš Kozelek. Methods of MCTS and the game Arimaa. Master's thesis, Charles University in Prague (2009) 
8. Xiaocong Gan (2011. december 1.). „Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man”. ICGA Journal 34 (4), 209–222. o. DOI:10.3233/ICG-2011-34404. 
9. Tom Pepels (2014. szeptember 1.). „Real-Time Monte Carlo Tree Search in Ms Pac-Man”. IEEE Transactions on Computational Intelligence and AI in Games 6 (3), 245–257. o. DOI:10.1109/tciaig.2013.2291577. 
10. Mountain: Tactical Planning and Real-time MCTS in Fable Legends, 2015 [2019. június 8-i dátummal az eredetiből archiválva]. (Hozzáférés: 2019. június 8.) „.. we implemented a simulation based approach, which involved modelling the game play and using MCTS to search the potential plan space. Overall this worked well, ...”
11. Michael Buro. Improving State Evaluation, Inference, and Search in Trick-Based Card Games, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009, Craig Boutilier (ed.), 1407–1413. o. (2009) 
12. Jonathan Rubin (2011. április 1.). „Computer poker: A review”. Artificial Intelligence 175 (5–6), 958–987. o. DOI:10.1016/j.artint.2010.12.005. 
13. C.D. Ward. Monte Carlo Search Applied to Card Selection in Magic: The Gathering, CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press (2009) 
14. István Szita.szerk.: Jaap Van Den Herik: Monte-Carlo Tree Search in Settlers of Catan, Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. Springer, 21–32. o. (2010). ISBN 978-3-642-12992-6 
15. Sylvain Gelly. Modification of UCT with Patterns in Monte Carlo Go. Technical report, INRIA (2006. november 1.) 
16. G.M.J.B. Chaslot (2008). „Progressive Strategies for Monte-Carlo Tree Search”. New Mathematics and Natural Computation 4 (3), 343–359. o. DOI:10.1142/s1793005708001094. 
17. Gelly, Sylvain. Combining Online and Offline Knowledge in UCT, Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007, Zoubin Ghahramani (ed.), ACM, 273–280. o. (2007). ISBN 978-1-59593-793-3 
18. Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik. Parallel Monte-Carlo Tree Search, Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings, H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.), Springer, 60–71. o. (2008). ISBN 978-3-540-87607-6 

Fordítás

Ez a szócikk részben vagy egészben a Monte Carlo tree search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.