Mechanizm kółek i krzyżyków Matchbox Educable
Matchbox Educable Noughts and Crosses Engine (czasami nazywany Machine Educable Noughts and Crosses Engine lub MENACE ) był mechanicznym komputerem wykonanym z 304 pudełek zapałek zaprojektowanych i zbudowanych przez badacza sztucznej inteligencji Donalda Michie w 1961 roku. Został zaprojektowany do gry z ludzkimi przeciwnikami w grach kółko i krzyżyk (kółko i krzyżyk), odwracając ruch dla dowolnego stanu gry i udoskonala swoją strategię poprzez uczenie się przez wzmacnianie .
Michie nie miał łatwo dostępnego komputera, więc obejść to ograniczenie, budując go z pudełek zapałek. Pudełka zapałek używane przez Michie reprezentowały jeden możliwy układ siatki w kółko i krzyżyk. Kiedy komputer grał po raz pierwszy, losowo wybierał ruchy w oparciu o bieżący układ. Rozgrywając więcej gier, poprzez pętlę wzmacniającą, dyskwalifikował strategie, które prowadziły do przegrywania gier, i uzupełniał strategie, które prowadziły do wygrywania gier. Michie zorganizował turniej przeciwko MENACE w 1961 roku, podczas którego eksperymentował z różnymi debiutami.
Po dziewiczym turnieju MENACE przeciwko Michie zademonstrował skuteczną sztuczną inteligencję w swojej strategii. Eseje Michiego na temat inicjalizacji wagi MENACE i algorytmu BOXES używanego przez MENACE stały się popularne w dziedzinie badań informatycznych. Michie został uhonorowany za swój wkład w badania nad uczeniem maszynowym i dwukrotnie zlecono mu zaprogramowanie symulacji MENACE na prawdziwym komputerze.
Pochodzenie
Donald Michie (1923–2007) był członkiem zespołu rozszyfrowującego niemiecki kod tuńczyka podczas II wojny światowej . Piętnaście lat później chciał jeszcze bardziej wykazać się matematycznymi i obliczeniowymi zdolnościami za pomocą wczesnej konwolucyjnej sieci neuronowej . Ponieważ nie można było uzyskać sprzętu komputerowego do takich zastosowań, a Michie nie miał łatwo dostępnego komputera, zdecydował się pokazać i zademonstrować sztuczną inteligencję w bardziej ezoterycznym formacie i skonstruował funkcjonalny komputer mechaniczny z pudełek zapałek i koralików.
MENACE powstało w wyniku zakładu z kolegą informatykiem, który postulował, że taka maszyna jest niemożliwa. Michie podjął się zadania zebrania i zdefiniowania każdego pudełka zapałek jako „zabawnego projektu”, który później przekształcił się w narzędzie demonstracyjne. Michie ukończył swój esej na temat MENACE w 1963 r., „Experiments on the mechanization of game-learning”, a także esej na temat algorytmu BOXES, napisany z RA Chambers i zbudował jednostkę badawczą AI na Hope Park Square w Edynburgu w Szkocji .
MENACE „nauczyło się”, grając coraz większe mecze w kółko i krzyżyk. Za każdym razem wyeliminowałoby to przegraną strategię polegającą na konfiskacie przez gracza koralików odpowiadających każdemu ruchowi. Wzmacniał wygrywające strategie, czyniąc ruchy bardziej prawdopodobnymi, dostarczając dodatkowe koraliki. Była to jedna z najwcześniejszych wersji Reinforcement Loop , schematycznego algorytmu zapętlania algorytmu, porzucania nieudanych strategii, aż pozostaną tylko zwycięskie. Ten model zaczyna się całkowicie losowo i stopniowo się uczy.
Kompozycja
MENACE powstało z 304 pudełek zapałek sklejonych ze sobą w układzie przypominającym komodę. Każde pudełko miało numer kodu, który został wpisany do wykresu. Ten wykres zawierał rysunki siatek gry w kółko i krzyżyk z różnymi konfiguracjami X, O i pustych kwadratów, odpowiadających wszystkim możliwym permutacjom, przez które gra mogła przejść w miarę postępów. Po usunięciu zduplikowanych układów (tych, które były po prostu obrotami lub lustrzanymi odbiciami innych konfiguracji), MENACE użył 304 permutacji w swoim wykresie, a tym samym tyle pudełek zapałek.
Każda pojedyncza taca pudełka zapałek zawierała kolekcję kolorowych koralików. Każdy kolor reprezentował ruch na kwadracie na siatce gry, więc pudełka zapałek z układami, w których pozycje na siatce były już zajęte, nie miałyby koralików dla tej pozycji. Dodatkowo z przodu tacy znajdowały się dwie dodatkowe karty w kształcie litery „V”, przy czym czubek litery „V” wskazywał przód pudełka zapałek. Michie i jego zespół zajmujący się sztuczną inteligencją nazwali algorytm MENACE „Boxes”, na cześć urządzenia użytego w maszynie. Pierwszy etap „Pudełka” działał w pięciu fazach, z których każda ustanawiała definicję i precedens dla zasad algorytm w stosunku do gry.
Operacja
MENACE grał jako pierwszy, jako O, ponieważ wszystkie pudełka zapałek reprezentowały permutacje istotne tylko dla gracza „X”. Aby odzyskać ruch wybrany przez MENACE, przeciwnik lub operator zlokalizował pudełko zapałek, które pasowało do aktualnego stanu gry, jego obrotu lub lustrzanego odbicia. Na przykład na początku gry byłoby to pudełko zapałek dla pustej siatki. Taca byłaby wyjmowana i lekko potrząsana, aby przesuwać koraliki. Następnie koralik, który zwinął się w punkt w kształcie litery „V” z przodu tacy, był ruchem, który wybrał MENACE. Jego kolor był następnie używany jako pozycja do gry, a po uwzględnieniu wszelkich potrzebnych obrotów lub przewrotów w oparciu o stosunek wybranej konfiguracji pudełka zapałek do bieżącej siatki, O zostałoby umieszczone na tym kwadracie. Następnie gracz wykonał swój ruch, zlokalizował nowy stan, wybrał nowy ruch i tak dalej, aż do zakończenia gry.
Kiedy gra się skończyła, gracz-człowiek obserwował wynik gry. Podczas gry każde pudełko zapałek, które zostało użyte w turze MENACE, miało swoją tackę z powrotem uchyloną, a użyty koralik był odłożony na bok, tak aby wybór ruchów MENACE i stany gry, do których należały, były rejestrowane. Michie opisał swój system wzmacniania za pomocą „nagrody” i „kary”. Po zakończeniu gry, gdyby MENACE wygrało, otrzymałoby „nagrodę” za zwycięstwo. Usunięte koraliki pokazywały sekwencję zwycięskich ruchów. Zostały one zwrócone do odpowiednich tac, łatwe do zidentyfikowania, ponieważ były lekko otwarte, a także trzy dodatkowe koraliki tego samego koloru. W ten sposób w przyszłych grach MENACE z większym prawdopodobieństwem powtórzy te zwycięskie ruchy, wzmacniając zwycięskie strategie. Jeśli przegrał, usunięte koraliki nie zostały zwrócone, co „karało” ZAGROŻENIE i oznaczało, że w przyszłości będzie mniej prawdopodobne, a ostatecznie niemożliwe, jeśli ten kolor zniknie, aby powtórzyć ruchy, które powodują przegraną. Jeśli gra zakończyła się remisem, do każdego pudełka dodawano jeden dodatkowy koralik.
Wyniki w praktyce
Optymalna strategia
Kółko i krzyżyk ma dobrze znaną optymalną strategię. Gracz musi umieścić swój symbol w taki sposób, aby uniemożliwić drugiemu graczowi dojście do dowolnego rzędu, jednocześnie samemu układając rząd. Jeśli jednak obaj gracze zastosują tę strategię, gra zawsze kończy się remisem. Jeśli gracz będący człowiekiem jest zaznajomiony z optymalną strategią, a MENACE może się jej szybko nauczyć, wtedy gry ostatecznie zakończą się tylko remisami. Prawdopodobieństwo wygranej przez komputer szybko wzrasta, gdy komputer gra przeciwko losowo grającemu przeciwnikowi.
Grając z graczem stosującym optymalną strategię, szanse na remis rosną do 100%. W oficjalnym turnieju Donalda Michiego przeciwko MENACE w 1961 roku zastosował optymalną strategię, a on i komputer zaczęli regularnie remisować po dwudziestu grach. Turniej Michie miał następujące kamienie milowe: Michie zaczął od konsekwentnego otwierania z „Wariantem 0”, środkowym kwadratem. W 15 grach MENACE porzucił wszystkie otwarcia inne niż narożne. W wieku nieco ponad 20 lat Michie zaczął konsekwentnie używać „Wariantu 1”, prawego dolnego kwadratu. W wieku 60 lat wrócił do wariantu 0. Gdy zbliżał się do 80 gier, przeniósł się do „wariantu 2”, górnego środka. Na 110 przeszedł do „Wariantu 3”, w prawym górnym rogu. W wieku 135 lat przeszedł do „Wariantu 4”, środkowo-prawego. W wieku 190 wrócił do wariantu 1, a w wieku 210 wrócił do wariantu 0.
Trend zmian koralików w pudełkach „2” wygląda następująco:
| Wariant | Dopasuj numer | Zmiana koralików w polu „2”. |
|---|---|---|
| Wariant 0 | 0 | 0 |
| Wariant 1 | 20 | -5 |
| Wariant 0 | 60 | 5 |
| Wariant 2 | 70 | 10 |
| Wariant 3 | 110 | 20 |
| Wariant 4 | 135 | 25 |
| Wariant 1 | 190 | 100 |
| Wariant 0 | 210 | 120 |
Korelacja
W zależności od strategii zastosowanej przez gracza, MENACE tworzy inny trend na wykresach punktowych wygranych. Użycie losowego zwrotu gracza będącego człowiekiem skutkuje prawie idealnym pozytywnym trendem. Gra z optymalną strategią zwraca nieco wolniejszy wzrost. Wzmocnienie nie tworzy idealnego standardu zwycięstw; algorytm będzie wyciągał losowe niepewne wnioski za każdym razem. Po j -tej rundzie korelacja gry bliskiej perfekcji wygląda następująco:
Gdzie V i to wynik (+1 to wygrana, 0 to remis, a -1 to przegrana), a D to współczynnik rozpadu (średnia przeszłych wartości wygranych i przegranych). Poniżej M n to mnożnik dla n -tej rundy gry.
| Wynik | Wzmocnienie |
|---|---|
| Wygrał | |
| Rysować | |
| Zaginiony |
Dziedzictwo
MENACE Donalda Michiego udowodniło, że komputer może „uczyć się” na błędach i sukcesach, aby stać się dobrym w wykonywaniu zadania. Wykorzystał to, co stało się podstawowymi zasadami w dziedzinie uczenia maszynowego, zanim zostały one odpowiednio sformułowane. Na przykład połączenie sposobu, w jaki MENACE rozpoczyna się od równej liczby rodzajów koralików w każdym pudełku zapałek, a następnie ich losowego wybierania, tworzy zachowanie uczenia się podobne do inicjalizacji wagi w nowoczesnych sztucznych sieciach neuronowych . W 1968 roku Donald Michie i RA Chambers stworzyli kolejny algorytm oparty na „BOXES” o nazwie GLEE (Game Learning Expectimaxing Engine), który musiał nauczyć się balansować tyczką na wózku.
Po gromkim przyjęciu MENACE, Michie został zaproszony do Biura Badań Marynarki Wojennej Stanów Zjednoczonych, gdzie zlecono mu zbudowanie programu uruchamiającego „pudełka” dla komputera IBM do użytku na Uniwersytecie Stanforda . Michie stworzył program symulacyjny MENACE na Pegazie 2 komputer przy pomocy D. Martina. W ostatnich latach było wiele odtworzeń MENACE, zarówno w jego oryginalnej formie fizycznej, jak i jako program komputerowy. Jego algorytm został później zbieżny z algorytmem Q-Learning Christophera Watkina. Chociaż nie jako funkcjonalny komputer, w przykładach demonstracyjnych MENACE był używany jako pomoc dydaktyczna na różnych zajęciach z sieci neuronowych, w tym w publicznej demonstracji Matthew Scroggsa, naukowca z University College London. Kopia MENACE zbudowana przez Scroggsa została zaprezentowana podczas wykładów bożonarodzeniowych Royal Institution w 2019 roku oraz w odcinku QI XL z 2023 roku .
Zobacz też
Źródła
- Michie, D.; Chambers, RA (1968), „BOXES: An Experiment in Adaptive Control” , Machine Intelligence , Edynburg, Wielka Brytania: Oliver and Boyd, S2CID 18229198 – za pośrednictwem Semantic Scholar , Michie i R. A Chambers' paper on the AI implikacje BOXES i GROŹBA.
- Russell, David W. (2012), The BOXES Methodology: Black Box Dynamic Control , Springer London, ISBN 978-1849965286 , książka o algorytmie „Boxes” stosowanym przez MENACE.