Rozwój sztucznej inteligencji w programach szachowych. Sztuczna inteligencja biła osobę w grach (Idź, szachy i inne) projekt szkolenia szachy i sztucznej inteligencji
Rok temu Program Alphago Sensational Beat najsilniejszy gracz na świecie, a teraz sztuczna inteligencja Alphazero pokonała najsilniejszy silnik szachowy.
Sztokfisz, który jest używany do przygotowania domu większość graczy, zwycięzca mistrzostw TCEC 2016 i Mistrzostwa Chess.com wśród programów komputerowych 2017, okazały się wyraźnie słabsze. W meczu ze 100 stron Alphazero zdobył 28 zwycięstw przy 72 rysunkami i nigdy nie zgubili.
Nawiasem mówiąc, alfazerko wydał tylko cztery godziny na "studiowanie" szachy. Przepraszam, ludzie, ale nie jesteś zły.
Wszystkie programiści Alphazero opracowane przez Deepmind, Google, stworzyli go w oparciu o mechanizm "uczenia maszynowego", dokładniej, "uczenia się ze wzmocnieniem". Mówiąc prosto, alfazero nie studiował szachów w tradycyjnym znaczeniu. Nie ma debiutanckiej książki, ani stołów końcowych, żadnych złożonych algorytmów do oceny siły pionków centralnych i flankowanych.
Jego prace mogą być porównywane z robotem, który może używać tysięcy części zamiennych, ale nie zna zasady działania silnika spalinowego, - przechodzi przez możliwe kombinacje, aż buduje Ferrari, a dla tego potrzebuje mniej czasu niż trylogia władcy pierścieni. Przez cztery godziny program odgrywał z tobą wiele imprez, stając się własnym nauczycielem.
Do tej pory zespół programistów ciągle cisza. Nie podawali komentarzy Chess.com, odnosząc się do faktu, że raport "podczas rozpatrywania", ale tutaj możesz przeczytać swój pełny tekst. Zespół badawczy obejmuje demisa Hassabis, kandydata głównego z Anglii i współzałożyciela Deepmind (zakupione Google w 2014 r.). Hassabis, który uczestniczył w turniejach Tandem Tandems na otwarciu London Chess Classic, jest obecnie na konferencji systemów przetwarzania informacji neuronowych (systemy przetwarzania informacji neuronowych) w Kalifornii, jako współpracownika raportu na innym temacie.
Ale z Chess.com z niecierpliwością udostępnił swoje osądy szachy, który ma wielkie osobiste doświadczenia gry przeciwko komputerom szachowym. MG Harry Kasparov nie jest zaskoczony, że Deepmind przeniósł się z iść do szachy.
"Jest to zauważalne osiągnięcie, chociaż oczekiwano po Alphago" - powiedział Chess.com. "Zbliża się do" type-b ", ludzkim podejściem do szachy, które kanałowy Shannon i Alan Turing marzyli o zastąpieniu solidnego biustu."
Podobnie jak osoba, alfazero rozważa mniej pozycji niż jego poprzedników. Raport stwierdził, że szacuje, że "suma" 80 tysięcy pozycji na sekundę w porównaniu z 70 milionami na sekundę od Smackafish.
MG Peter-Heine Nielsen, długoterminowy drugi mistrza świata MG Magnus Karlsen, otworzył swoją pasję, przynosząc mu bliżej prezesa FIDE: kosmitów. Powiedział Chess.com: "Po przeczytaniu raportu, aw szczególności, po przejrzeniu partii, pomyślałem:" Byłem zawsze ciekawy, że byłoby to, gdyby na naszej planecie sadzono na naszej planecie i pokazał nam swoją sztukę gra w szachy. Wydaje się, że teraz wiem, co to jest.
Nauczyliśmy się również o znaczeniu zalet łodygi, przynajmniej dla sztucznej inteligencji. 25 z 28 zwycięstw Alphazero wygrał biały (chociaż wynik + 3 \u003d 47-0 czarny przeciwko Sztokfiszie, którego ocena przekracza 3400, również nie zły).
Raport pokazuje i jak często silnik wybrał pewne debiuty, gdy uczą. Przepraszamy, kochankowie Ochrony Old-Indian, ale nie jesteś na korzyść. Zainteresowanie francuską jest również UGA w czasie, ale pragnienie grania w felu Gambit, a zwłaszcza, że \u200b\u200bangielski początek właśnie wzrosły.
Co byś zrobił w miejscu niezbędnego zmęczenia stworzenia, tylko kto opanował grę z historią 1400 lat? Przejmie drugą. Po meczu Stockfish Alphazero spędzony na "szkoleniu" tylko dwie godziny i pokonał Elmo, najsilniejszy z silników komputerowych do gry w SyoM.
Korzystanie z tego innowacyjnego programu samokształcenia nie ogranicza się do gier.
"Zawsze uważano, że istnieje zbyt wiele wiedzy empirycznej w szachach z maszyny, aby mogli grać silnie" od podstaw ", bez użycia wiedzy w ogóle" - powiedział Casparov. "Oczywiście będę zainteresowany, by zobaczyć Co możemy dowiedzieć się o szachach. Z pomocą Alphazero, która otwiera ogromne perspektywy uczenia się maszyny w całej maszynie, mogą znaleźć regularności niedostępne dla ludzi. Jest oczywiste, że konsekwencje rozszerzają się daleko poza szachy i inne gry. Zdolność Maszyna do otwarcia i przekracza znajomość złożonych systemów zamkniętych, nagromadzonych przez ludzkość przez wieki, - jest to narzędzie zmieniające świat. "
Chess.com Dziennikarzy przeprowadzali wywiad z ośmioma z dziesięciu uczestników turniejów w Londynie na swoim stosunku do dopasowania programu. Wideo z wywiadem zostanie opublikowany na stronie później.
Najbardziej ostro skrytykował warunki meczu MG Hikar Nakamura. Teraz istnieje gorąca dyskusja na temat siły komputerowej przeciwników, ale Nakamura uważa, że \u200b\u200binny jest ważniejszy.
Amerykański grandmaster zwany mecze "nieuczciwe", określając, że dla optymalnej pracy silnik, Ekokfish powinien używać debiutanckiej książki. Nakamura nie uważa, że \u200b\u200bwraz z jej pomoc stockfisz wygrał mecz, ale luka na koncie byłaby znacznie mniejsza.
"Jestem pewien, że sam Pan sam nie zyskałby 75 procent okularów z białym bez żadnego foowu", skomentował wynik alfazero biały: 25 zwycięstw i 25 rysunków.
MG Larry Kaufman, wiodący konsultant w szachy Komodo silnik, ma nadzieję zobaczyć, jak dobrze nowy program działa na komputerach osobistych, bez korzystania z kamienic obliczeniowych Google. Powtórzył także zastrzeżenia wyrażone przez Nakakurę o fakcie, że Łupka gra bez zwykłej wiedzy debiutycznej.
"Oczywiście, że jest prawie niesamowite", powiedział: "Tak, usłyszałem o osiągnięciach zero Alphago w grze i spodziewałem się czegoś takiego, biorąc pod uwagę, że zespół deweloperów miał szachy Demis Hassabis. Jednak nie jest jasne, czy program Alphazero może grać w szachy na zwykłym komputerze i jak dobrze się odnosi. Być może współczesna rozpowszechnianie silników szachowych za pomocą funkcji Minimax jest zbliża się do końca, ale do tej pory jest zbyt wcześnie, aby go głosić. Warto wskazać, że podczas szkolenia Alphazero de facto stworzył własną debiutancką książkę, więc byłoby bardziej sprawiedliwe, aby używać go do silnika z dobrą debiutancką książką. "
Nie dotykając warunków meczu, Nielsen jest pomyślany, w jakichkolwiek obszarach można zastosować ten typ uczenia się.
"[Ten] Nowoczesny sztuczny intelekt" - powiedział Grossmaster. "Pochodzi z czegoś takiego jak szachy do problemów godnych nagród Nobla i jeszcze więcej. Myślę, że mieliśmy szczęście, że postanowili spędzić cztery godziny na szachy, ale konsekwencje tego odkrycia są znacznie bardziej znaczące.
Przedmiot, wiek studentów
Informatyka i ICT, 10-11 klasa
Krótki abstrakcyjny projekt.
Projekt został opracowany jako część dyscypliny "informatyki i ICT" dla studentów klasy 10-11
Pytania Projekt prowadzący
Podstawowe pytanie
Czy komputer może zastąpić osobę?
Problemy z problemami
1. Czy sam komputer może umieścić zadania i rozwiązać je?
2. Czy komputer jest w stanie odtworzyć wszystkie działania i myśli osoby?
3. Czy komputer jest zdolny do zarządzania osobą?
Program
1. Jakie zadania rozwiązuje komputer?
2. Czy EMM Self-Second?
3. Czy automaty mogą zastąpić osobę?
4. Sztuczna inteligencja \u003d ludzka inteligencja?
5. Czy muszę zarządzać pracą komputera?
6. Czy można umieścić robota "na głowie tabeli"?
7. Czy komputer może wiedzieć, jak myśleć?
8. Czy można wymienić ludzki mózg sztuczny?
9. Czy osoba przygotowuje się do pouczania całej pracy do robotów?
Plan projektu
Reprezentacja sytuacji problemowej:
Nauczyciel musi posiadać burzę mózgów ze studentami, aby zidentyfikować istniejącą wiedzę uczniów na temat problemu, ich motywacji, skłonności i zainteresowań. Narzędzie - burza mózgów przy użyciu prezentacji wyjściowej. Przy pomocy prezentacji nauczyciel stwarza sytuację problemową, organizuje atak mózgu, omawiając kwestie, które powstały, nominować hipotezy i dystrybucję studentów na temat grup tematycznych, biorąc pod uwagę interesy.
Praca projektowa:
Na początku etapie projektu nauczyciel pomaga każdej grupie tematycznej do dystrybucji ról, omówić strategię badawczą, sposoby wyszukiwania informacji, metod badawczych i możliwość wykonania wyników pracy. Rezultatem jest indywidualny plan działania. Dalsze, niezależne badania zaczyna się, pracuje uczniów w zakresie wyszukiwarki zgodnie z planem. Na tym etapie uczniowie zbierają informacje na temat problematycznej kwestii w encyklopedii, podręcznikach i w Internecie, omawiają zebrane informacje w grupie, rozwijają narzędzia badawcze, prowadzić badania, porównują swoje wyniki ze zebranymi informacjami, wyciągnij wnioski, które będą być odpowiedzią na problematyczne pytanie. Koncentracja nauczyciela powinna być przekazywana do przejściowych dyskusji, dyskusji w ramach grup, konsultacje nauczycieli przedmiotów. Właściciel poczucia własnej wartości pomoże uczestnikom projektu, aby zrealizować poziom rozwoju osobistego.
Rejestracja działań projektowych:
Projektowanie wyników planuje się w formie prezentacji, broszury lub artykułu wiki, więc tutaj możesz potrzebować konsultacji z nauczycielem informatyki, na jednej z konsultacji konieczne jest omówienie z facetami kryteriami szacowania tych produktów . Jednocześnie wydajność Grupy przygotowuje się, więc w kryteriach oceny konieczne jest składanie pozycji do oszacowania mowy uczniów, możliwość zadawania pytań i reagowania na nich.
Ochrona projektu, przeciwnik, dyskusja:
W trakcie ochrony każda grupa przedstawia swoją pracę (prezentacja, broszura lub artykuł wiki), odpowiedzi odpowiedzi. Ocena występuje przez Grupę opracowaną przez kryteria, uczestników innych grup, nauczycieli. Ochrona projektów pozwala na odpowiedź na podstawowe pytanie, sformułować ogólne konkluzje na temat wyniku.
Pod koniec pracy:
Niezbędnym elementem całej działalności projektu jest analiza wykonanej pracy, gdzie nauczyciel omawia studentami, że to się stało, że nie działa i dlaczego. Na tym etapie możesz ponownie skontaktować się z arkuszem poczucia własnej wartości i zobaczyć wysokiej jakości wzrost każdego uczestnika. Ponadto możliwe jest odbicie bloga. Staje się ważne, aby być przyznawanym grupą. I możesz zapoznać się na stronie projektu. 
Projekt wizytówki
Publikacja nauczyciela.
1997, Nowy Jork. Mistrz świata w szachy Garry Kasparov traci "Głębokie niebieskie" komputer firmy IBM, a ta bitwa staje się największą szachową stroną wszystkich czasów i narodów. Ta gra mówi o "ostatniej bitwie ludzkiego umysłu", wielu porównuje ją z pierwszym lotem braci Wright i Disembarka astronautów na Księżycu.
20 lipca - na międzynarodowym dniu szachowym - opowiedz o tym, co się stało. A także o tym, co sztuczna inteligencja jest gorsza od człowieka i gdzie jest turowanie Alan. Słowo Harry Kasparov, World Chess Mistrz i autor książki.
Paradoksalnie, ale podczas jednoczesnej gry o jednoczesnej grze z najlepszymi profesjonalnymi szachownicami robot jest najtrudniejszym sposobem poruszania się między stołami i zmieniaj szachy, a nie liczyć ruchów. Chociaż nauki naukowe nauk na temat kilku stuleci pojawiły się automaty, które wyglądają i poruszają się jak ludzie, a dziś roboty są pomyślnie zaangażowane w fizyczną pracę, musisz przyznać, że nasze samochody są znacznie lepsze odtwarzanie ludzkiego myślenia niż ruchy ludzkie.
W szachy, jak w wielu innych obszarach aktywności, samochody są silne w tym, co ludzie są słabe, a odwrotnie.
Ta dobrze znana zasada w dziedzinie sztucznej inteligencji i robotyki sformułowała MES kanału w roku, który zauważył, że "stosunkowo po prostu, aby zapewnić, że komputery przeprowadzają test rozwoju psychicznego lub grać w warcaby na poziomie dorosłego, ale to jest trudny lub niemożliwy do wystąpienia umiejętności jednorocznego dziecka na szczycie percepcji lub mobilności. "
W tym czasie nie byłem świadomy tych teorii; Ponadto płótno mówił o warcabach, a nie o szachy, ale dziesięć lat później stało się oczywiste, że ta zasada dotyczy mojej sfery działalności. Grandmasters doskonale poradzili sobie z szacunkiem Pozycji i planowania strategicznego - słabe miejsca komputerów szachowych, ale mogły obliczyć taktyczne konsekwencje w sekundach, które nawet najlepsze ludzkie umysły byłyby wymagane przez wiele dni.
Zastosowano do mnie pomysł. Po tym, jak moje mecze z głębokim niebieskim przyciągnął tak blisko uwagi, chciałem kontynuować eksperymenty szachowe, mimo że IBM odmówił ich.
Mój plan, po prostu mówiąc, był taki: jeśli nie możesz ich wygrać, a następnie dołącz do nich.
Myślałem: co jeśli osoba i samochód nie są przeciwnikami, ale przez partnerów? Pomysł został zawarty w roku w hiszpańskim Leone, gdzie odbył się pierwszy zaawansowany mecz szachowy (zaawansowane szachy). Oba partnerzy mieli w ręku komputer osobisty i mogły korzystać z dowolnego programu w wyborze podczas imprezy. Celem było wejście do nowego, najwyższego poziomu gry - ze względu na syntezę najsilniejszych stron inteligencji człowieka i maszynowej. Chociaż, jak zobaczymy dalej, nie wszystko minęło drogę, uderzające wyniki tych "bitwy Centaurów" przekonały mnie, że szachy mogą nadal oferować dużo w takim obszarze, jak interakcja ludzkiego umysłu i sztucznej inteligencji.
Do tego przekonania, przyszedłem z początku. Charaktery były długim świętym cmentarzem, zanim ludzie je stworzyli. A teraz nauka ostatecznie zdobyła dostęp do tego kubka - i okazało się, że jest osobą, która trzyma ją w rękach. Przede mną stał wybór: Odrzuć połączenie lub weź go. Jak mogłem się oprzeć? Była to szansa na dalsze podniesienie popularności szachów i rozszerzyć publiczność podbite przez nich po słynnym meczu między Bobby Fisher i Borisa Spassky podczas zimnej wojny i po moich walkach o światową koronę z Anatolem Karpovem. Pozwoliłoby to na armię hojnych sponsorów świata szachów, zwłaszcza z liczby spółek high-tech. W związku z tym Intel Corporation w połowie lat 90. sponsorował całą serię szybkich i klasycznych turniejów szachowych oraz pełny cykl Pucharu Świata, w tym mój tytułowy mecz z Vishvanatanem Anand, który odbył się na najwyższym piętrze World Trade Center. Ponadto udało mi się nawołonioną ciekawość. Czy samochody naprawdę mogą dowiedzieć się, jak grać w szachy, jest tak dobry jak mistrz świata? Czy naprawdę są w stanie myśleć?
zastanawiam się, co
pierwszy program szachowy pojawił się wcześniej niż pierwszy komputer.
Opracowała genialny brytyjski turing Alan Matematyk, który zhakował kod maszyny szyfrowej nazistowskiej "Enigma". W 1952 r. Napisał algorytm na papierze, z pomocą którego samochód może grać w szachy, a sam matematyk był wykonywany w roli centralnego procesora. "Papierowa maszyna Turinga" okazała się całkowicie kompetentnym graczem. Powodem jego projektu wykraczał poza struktury osobistego interesu turowania do szachy. Zdolność do gry w szachy była uważana za część ludzkiej inteligencji, a stworzenie urządzenia zdolnego do pokonania osoby w tej grze powinno oznaczyć wygląd prawdziwie inteligentnego samochodu.
Nazwa Alan Tyurring jest również zawsze połączona z nazwą eksperymentu psychicznego zaproponowanego przez nich, później przeprowadzona w rzeczywistości i nazwa "Testowanie testowe". Jego istotą jest ustalenie, czy komputer będzie w stanie oszukać osobę w taki sposób, że uważa, że \u200b\u200bma on do czynienia z osobą, a jeśli może - test jest uważany za minę. Nawet przed moim pierwszym meczem z głębokim niebieskim, komputery zaczęły przejść przez to, co można nazwać "Szachy Turinga". Nadal grali dość źle i często wyraźnie nieludzkie ruchy, ale czasami udało im się grać na imprezy, które wyglądałyby dość odpowiednim i w przyzwoitym kraju turnieju. Każdego roku samochód stał się silniejszy i silniejszy, ale w procesie ich ewolucji dowiedzieliśmy się więcej o samych szachach niż o sztucznej inteligencji (AI).
Nie można twierdzić, że punkt kulminacyjny 45-letnich poszukiwań, które stało się światowym wydarzeniem odwróconym z rozczarowaniem, ale wyraźnie pokazała, że \u200b\u200bnie było to samo, co stworzyć sztuczny intelektu, który był w stanie porównać z ludzkim umysłem Co było w stanie porównać stracę i inne.
W istocie "umysł" głębokiego niebieskiego nie różnił się od "umysłu" programowalnego alarmu.
Pomyślałem o tym po prostu pogorszył się dla mnie goryczy porażki - stracić programowalną klinikę alarmową, nawet jeśli 10 milionów dolarów i wart 10 milionów dolarów?
Tak zwana społeczność AI oczywiście cieszyła wynik i przyciągnęła uwagę, ale jednocześnie uczonych byli wyraźnie zniechęceni fakt, że głębokie niebieski nie przypomina sztucznej inteligencji, o której marzyli ich poprzedniki. Zamiast grać w szachy jako osoba - wykazując ludzkie intuicja i niestandardowe kreatywne myślenie, gra w szachy jako samochód: ocenia do 200 milionów możliwych ruchów na sekundę i wygrywa z powodu szorstkiej mocy obliczeniowej. Oczywiście nie zmniejsza to samo osiągnięcia. W końcu głębokie błękit jest stworzeniem ludzkiego umysłu, a strata osoby stworzonej przez niego przez samochód jednocześnie oznacza jego zwycięstwo.
Po niesamowitym napięciu tego meczu, który był pogorszył podejrzane zachowanie IBM i moją tendencję do wątpliwości, nie mogłem łatwiej rozpoznać moją porażkę. Szczerze mówiąc, nigdy nie wiedziałem, jak stracić. Wierzę, że osoba, która jest łatwo rozszerzona z porażką, nigdy nie stanie się prawdziwym mistrzem, a ta zasada oczywiście jest również uczciwa iw moim przypadku. Ale wierzę w uczciwą walkę. Wtedy wierzyłem, że IBM oszukał mnie - jak również cały świat, który ściśle śledził nasz mecz.
Musi przyznać, że powtarzająca się analiza każdego aspektu tej obrzydliwej pojedynki z głębokim niebieskim okazała się trudna.
Przez lata celowo uniknąłem żadnych rozmów na ten temat, biorąc tylko to, co było już znane ogółu społeczeństwa.
Publikacje poświęcone głębokim niebieskim, wspaniałym zestawie, ale ta książka jest pierwszym i jedynym, w którym wszystkie fakty są gromadzone, a cała historia jest powiedziane tak, jak go widzę. Pomimo bolesności wspomnień, to był instrumentowany i korzystny doświadczenie. Mój wielki nauczyciel Mikhail Botvinnik, szósty mistrz świata w szachy, nauczył mnie szukać prawdy w każdej pozycji. I próbowałem wykonać jego przymierza i szukałem prawdy w samej istocie głębokiego błękitu.
Ilustracja: Shutterstock.Wyślij dobrą pracę w bazie wiedzy jest proste. Użyj poniższego formularza
Studenci, studiach studentów, młodych naukowców, którzy korzystają z bazy wiedzy w swoich badaniach i pracach, będą ci bardzo wdzięczni.
Wysłane przez http://www.allbest.ru/
Rozwójoprogramowaniemodułsztucznyintelektdlagrywszachy
algorytm intelektalny komputera szachowego
- Wprowadzenie
Koncepcja "szachy komputerowej" jest rówieśnikiem nauki o cybernetyce i jej sekcji "sztuczny intelekt". Szachy jest idealnym modelem do badania złożonych zadań, zwłaszcza tych, w których potrzebujesz opcji biustu. Rozwój programu szachowego odnosi się do problemu rozwijania sztucznej inteligencji z następujących powodów:
* Istnieje ogólne zaufanie, że zadanie jest związane z problemem sztucznej inteligencji, ponieważ szachy jest uważane za najbardziej intelektualną grę
* Wykonano obiektywne kryterium pracy - siłę programu szachowego
* Duże zróżnicowanie tego kryterium reprezentuje możliwość stopniowego poprawy programu.
Jeden z założycieli cybernetyki i teorii informacji - Claude Shannon - w latach 50. najpierw sformułował zasady wyboru udaru na szachownicy. W analizowanej pozycji przez określoną głębokość, wszystkie możliwe opcje są przenoszone, a całkowite pozycje za pomocą funkcji docelowych są przypisane ocenę numeryczną. Następnie wykonywana jest procedura minimax, aby włączyć do pozycji początkowej, wskazuje, że jego ocena i najlepiej, zgodnie z samochodem.
Rolą osoby jest oszacowanie pozycji, jak najdokładniej, aby ustawić funkcje docelowe. Funkcje te mają dwa elementy - materiał i pozycyjny. Od pierwszego wszystkiego jest jasne - przewaga materiałowa (na rysunkach i pionkach) jest z reguły, bardzo poważnym argumentem oceny stanowiska jako najlepszego. Ponadto, im mniejszy materiał na pokładzie po obu stronach, tym dokładniejsza ocena.
Ale z elementem pozycyjnym wszystko jest znacznie bardziej skomplikowane: wiele czynników jest brane pod uwagę, na przykład cechy lokalizacji poszczególnych kształtów i pionków, przestrzeni na pokładzie, czas na przegrupowanie sił i innych. Umiejętność doceniania Rola wszystkich czynników w określonej pozycji zawsze została uznana za jedno ze znaków odpieniaczów szachowych. - Ludzie.
Słabość gry komputerowej była dokładnie w nadużyciu materiałów i niemożności wdrażania "absolutnej brutalnej siły" opcji. W Książkach w Chessach z lat 70. i 80. można znaleźć znaczną liczbę przykładowych przykładów gry z maszynami, gdy Master lub Grandmaster wygrał przyjęcie z pomocą pięknych poświęconych figur i pionków. Sekret jest już czysty: dla ludzkiej inteligencji, w przeciwieństwie do sztucznego, dominacja czynników pozycyjnych jest oczywista w tych momentach, gdy ofiary materiału zostały przeprowadzone.
Lata minęły, ze wzrostem prędkości komputera, głębokość obliczeń wzrosła, a jednocześnie algorytmy poprawiły się, co poprawia kompilację funkcji oceny położenia. W drugiej połowie lat 90. komputery stały się już z powodzeniem konkurując z grasistami dodatkowej klasy. Epokal dla "Cybernetyki szachowej" wydarzenie miało miejsce w maju 1997 r. Stworzony przez IBM Corporation Deep Blue w meczu od 6 stron wygrał Harry Kasparov. Komputer został wyposażony w specjalny chip szachowy, a samochód spojrzał przez około 200 milionów pozycji na sekundę. IBM Corporation dla swojego projektu przyciągnęła wielu babci, najnowsze osiągnięcia teorii szachowej były używane do tworzenia jak najwięcej doskonałych algorytmów. I tak, jak już zauważył, w latach 90., programy szachowe dla komputerów pulpitu zaczęły zamknąć specjalistyczne komputery.
Każdego miesiąca siłę programów szachowych i moc komputerów wzrasta nieubłaganie, a nawet najbardziej odważne założenia optymistów. Kolejne 12-15 lat temu na ten temat "Kiedy samochód będzie mógł pokonać Brandmaster?" Zasadniczo został zredukowany do pytania "Czy jest w stanie tego robić w zasadzie?". A jeśli odpowiedź "może" nadal udało się uzyskać, czas oszacowano w przedziale 15-25 lat.
Rzeczywistość obaliła te prognozy. Wszystko stało się znacznie szybciej! Już w połowie lat 90. stwierdzono, że synteza "programu gier + komputera" może konkurować z Brandmaster.
Celem pracy jest opracowanie i wdrożenie modułu oprogramowania sztucznego wywiadu do gry w szachy, które obejmuje:
1. Badanie istniejących algorytmów gier Dokładne szachy
2. Rozwój algorytmu zachowania przeciwnika komputerowego
3. Określenie parametrów algorytmu zachowania przeciwnika komputerowego
4. Wdrożenie oprogramowania, które obejmuje wdrażanie algorytmu gry i rozwój interfejsu graficznego
5. Porównanie opracowanego oprogramowania z istniejącymi analogami.
1 . Historiarozwójszachyprogram
W 1951 r. Alan Turing napisał algorytm, z którym samochód może grać w szachy. Tylko w tym czasie sam inventor występował w roli samochodu. W tym samym 1951 r. Matematyk Claude Shannon pisze swój pierwszy artykuł o programowaniu szachowym. Opisał dwie strategie dla znalezienia lepszej obrotu, oba są oparte na heurystycznej funkcji oszacowania punktów końcowych:
* Wpisz A - biust Wszystkie możliwe ruchy do stałej głębokości, z połączeniem na końcu szacowanej funkcji (ponieważ niemożliwe jest rozszerzenie do końca)
* Typ B - wykonuje tylko selektywną rozszerzenie niektórych wierszy przy użyciu zgromadzonej wiedzy szachowej do przycinania nieinteresownych gałęzi
Pierwszy komputer został zaprojektowany przez Neumanna Tło do utrzymania złożonych obliczeń podczas tworzenia broni jądrowej. W 1950 roku pojawiła się pierwsza próbka, zdolna do wytwarzania 10 000 operacji na sekundę. Jednym z pierwszych eksperymentów z aparatem było pisanie programu szachowego, jednak szachy były niestandardowe - na tablicy 6 * 6 bez słoni.
Kilka lat później komputer ("Maniak") grał z ludźmi: silny szachy wygrał pewne zwycięstwo, a przybysz stracony w 23 udaru.
W 1957 r. IBM704 (42 kHz, 7 KBYTES-stały) wdrożono w programie na pełnym wyżywieniu, z udziałem wszystkich danych. Samochód wierzył 4 dni w 8 minut. Poziom gry jest amator.
W 1962 r. Newel, Simon i Shaw otworzył algorytm o nazwie Alpha-Beta (Alpha-Beta), dał wynik nie gorzej niż pełny biust, bez zbadania wszystkich opcji. Nie wymagał specjalnej wiedzy szachowej i można go zastosować do rozwiązania jakichkolwiek zadań transmisji. Istotą algorytmu jest to, że w każdym rzędzie gry, na białe i czarne ich maksymalne wyniki są śledzone, a jeśli w pewnym momencie czarny otrzymał już wynik, który został już wykonany z maksymalnie białego, osiągniętego wcześniej, Wtedy nie ma sensu wyeliminować. Gdy biust wraca do punktu, w którym osiągnięto biel maksimum, wynik, nadal zostanie odrzucony. Podstawą wszystkich nowoczesnych programów szachowych jest jedną z zaawansowanych wersji tego algorytmu.
Około 1973 r. Wszystkie programy szachowe były typu V. Są głównie na podstawie generatorów wiarygodnych przemieszczeń, które odcinają statyczną oceną małego działania. Wraz z pojawieniem się bardziej potężnych procesorów programiści zaczęli przełączać się na typ A. Pierwszy byli nauczyli i szachy4, były to programy "szorstki", gdy tylko dotarli do głębokości 5 staranności środkowego etapu, zaczęli wygrać W konkursach z programami V.
W 1975 r. Robert Hyat zaczyna rozwijać Crayblitz, który od dawna był najszybszy program szachowy przez długi czas i od 1983 do 1989 roku. - Mistrzowie świata wśród programów szachowych. Szukał około 40-50 tysięcy pozycji na sekundę (w 1983 roku), że za jego czas był świetnym osiągnięciem.
W 1977 r. Thompson i Condon z Bell Laboratory tworzy pierwszą specjalistyczną społeczność szachową. Podstawowa idea była w realizacji niektórych części programu szachowego (generator skoków, funkcje oszacowania pozycji, detektora Shakhowa itp.) Na poziomie sprzętu, który zapisał opóźnienia programu w każdej pozycji bez czekania na zwiększenie moc procesorów. Najlepsze komputery z tego czasu mogły zbadać do 5000 pozycji na sekundę, a maszyna Tompson Ken, która Belle o imieniu, przetworzyła 180 tysięcy wierszy na sekundę. Belle mógł pomyśleć o pozycjach 8-9 Dipów do przodu, które umieszczają na poziomie kreatora. Wygrał wiele turniejów szachowych komputerowych. Ale pomimo faktu, że wyspecjalizowane żelazo jest rzędem wielkości szybszym niż zwykły samochód, program Crayblitz w przełożonym, wciąż samochód nadal grał lepiej.
W latach 90. Richard Lang, napisanie wyłącznie na asemblerze, wykonał bardzo silny genius selektywnego programu wyszukiwania. Do tej pory program ten stale trzymał 5-6 miejsce na globalnych mistrzostwach szachowych komputerowych. Również w latach 90. algorytmy szachowe zaczęły rozwijać się silnie, eurystyki pustego skoku pojawił się (Nullmove), selektywne odcięte oddziały graniczne z rozwojem drzewa.
Oddzielnie warto rozważyć najsłynniejszy program szachowy, super komputerowy - głęboki niebieski. W 1987 r. Głębokie niebieski rozpoczął się jako rozwój studentów - był interesujący, że ma grupę zdolnych uczniów wypróbować ich siłę, a temat dla dyplomu jest doskonały. Postęp technologii pozwolił, aby pierwsza wersja procesorów (zwana Chiptest) bardzo szybko. Następująca, zaawansowana wersja, o której następuje głęboka myśl. W tym momencie Grupa odnotowała Departament Marketingu IBM i skierowany do niej z propozycją, z której nie można odmówić. Wynikiem stali głębokiego niebieskiego i głębokiego niebieskiego II. W ten sposób Głębokie Blue II jest wynikiem ponad 10 lat działania bardzo zdolnej grupy, w którym zarówno programiści / koleje, jak i ciężkie babci. Wszystkie prace były finansowane przez IBM, więc grupa miała zasoby, które nie marzy o organizacjach akademickich. Deep Blue II jest wykonany na podstawie potężnego serwera IBM RS / 6000. Serwer ma 31 zwykłych procesorów; Jeden zadeklarował główną rzecz, podlega 30 innych. 16 Specjalistycznego procesora szachowego jest podłączony do każdego procesora "pracownika", w ten sposób istnieje 480 procesorów szachowych. Cały kompleks przetworzony ponad miliard stanowisk na sekundę.
W dniu 11 maja 1997 r. Deep Blue II wygrał mistrz świata szachy Garry Kasparov w meczu z 6 stron. Po meczu z mistrzem, głęboki niebieski został zdemontowany.
Jak widać, począwszy od pierwszego, a kończąc się z najnowocześniejszymi programami, programy szachowe zostały zbudowane na podstawie integralności możliwych ruchów, ale były próby zbudowania więcej "intelektualnych" algorytmów innych niż przytłaczający. Wielu znanych szachowców próbowało rozwinąć takie algorytmy, ale wyniki nie spełniają wymagań. Na przykład Botvinnik M.m., będąc mistrzem świata i autorem licznych dzieł na teorii szachów, od ponad 20 lat, był zaangażowany w tworzenie programu szachowego, ale program nigdy nie grał.
Wszystkie algorytmy przeciążeń do znalezienia najlepszego kursu budują drzewo gry i szuka najlepszego ruchu.
2. Generałkoncepcjeteoriagry
2.1 Drewnomożliwypozycje
Niech ostatnie zorientowane drzewo G, zestaw w swoich wierzchołkach składa się z dwóch podzbiorów non-cyklowych B0 i B1, a każdy wierzchołek pb, który nie jest początkiem jakiegokolwiek ogniska z tego drzewa, umieścić zgodność z rzeczywistą liczbą OE (P). Określa grę dwóch przeciwników z pełną informacją. Wierzchołki zorientowanego drzewa G, należące do podzbioru B0, nazywane są pozycjami z białym i podzbiorem B1 - pozycje z czarnymi ruchami; Linki tego drzewa nazywane są białe lub czarne uderzenia, w zależności od których podzbiory B0 lub B1 należy do ich początku. Jeśli pozycja pb jest umieszczona zgodnie z numerem OE (P), nazywa się to final, a OE (P) nazywana jest oceną statyczną tej pozycji.
Zorientowany drzewo G Nazwał drzewo gry.
Zgodnie z definicją dla każdej pozycji PB, istnieje jedyna ścieżka L (P0\u003e P1, P1\u003e P2, ..., PK\u003e P) z początkiem na drzewie zorientowanym z korkiem ROOT R i końcu w rozważanej pozycji Ta ścieżka nazywana jest imprezą prowadzącą do pozycji p.
Gra roota P0 Drzewa G to podświetlona pozycja. Jest to pozycja zaproponowana przez program, a zadaniem jest znalezienie najlepszego kursu w nim. Aby to zrobić, wystarczy zdefiniować OEP0 i OEPI dla wszystkich pozycji uzyskanych z P0 na kurs. Definicje oceny pozycji początkowej P0 są przeprowadzane przez schemat całkowitych gaśni, aw teorii gier, algorytm ten nazywa się algorytmem Negamax.
Złożoność drzewa do gier oblicza się o wzorze: W ^ D, gdzie W jest średnia liczba możliwych ruchów, a D-Głębokość drzewa.
Rysunek 1 - Drzewo możliwych pozycji
2.2 Zasadaminimax
Ten algorytm jest przeprowadzany przez poszukiwanie głębokości. Oznacza to, że dla każdego głoszonego wierzchołka konieczne jest znalezienie wszystkich sąsiednich wierzchołków i powtarzają ich wyszukiwanie. Wracamy na szczyt ostatniej głębi i oczekujemy wygranych pierwszego gracza. Następnie, z węzła macierzystego, przejdź do następnego węzła dziecka (jeśli w ogóle) i spodziewamy się tam wygranych okularów. Jeśli liczba węzłów pomocniczych się skończy, szukamy minimum wygranych (jeśli poziom węzła macierzystego jest nieparzyste) lub maksimum (jeśli nawet). Węzeł rodzicielski ma zysk. Wykonujemy podobne wyszukiwanie, ale biorąc pod uwagę już, że węzeł macierzysty jest już spółka zależna.
W liściach drzewa obliczanie punktów występuje w stosunku do pierwszego gracza, tj. Uważa się, że pierwszy gracz dąży do maksymalizacji jego wygranych, a drugi gracz, aby zminimalizować wygrane zwycięskie wygrane gracza. Pierwszy gracz wygrywa w przypadku, gdy liczba punktów na górze drzewa na poziomie jest większa niż zero.
Rysunek 2 - Wyszukaj algorytm algorytmu drzewa Minimax
W rezultacie proces stosowany przez program odpowiada rozwiązaniom przemiennym (komputerowi / osobiście), na każdym kursie komputer wybiera maksymalną ocenę. Rozwiązanie powróciło do korzenia drzewa niewątpliwie okazuje się najlepszym wyborem, w ramach założenia, że \u200b\u200bwroga w każdym przypadku również wykonuje najsilniejsze ruchy. Szacowanie statyczne wykonywane jest tylko w węzłach ostatniego poziomu (liście drzew) dla pozycji komputera.
Ten algorytm zapewnia pełne wyszukiwanie wszystkich opcji. Liczba rozważanych pozycji zostanie oceniona jako w do stopnia D, gdzie W jest przybliżoną liczbą ruchów w jednej pozycji, d jest głębokością błędnej W przypadku szachy w około 40 oznacza to, że liczenie na głębokość 4, musimy nadeprzeć 40 ^ 4 \u003d 2560 tysięcy pozycji, a na głębokość 5 - 10240 tysięcy pozycji.
Rozbijające drzewo rośnie wykładniczo. Do tej pory na najpotężniejszych procesorach, z najbardziej optymalnym kodem, możliwe jest, aby być uważanym za głębokość 6 w prawdziwym szacowanym okresie czasu. Jest to główny problem rozwoju algorytmów gier w szachy, a wszystkie zmiany mają na celu zmniejszenie połączonych kombinacji.
Figura 3 przedstawia schemat blokowy algorytmu Minimax do wyboru lepszego postępu, algorytm przedstawiony przez algorytm zwraca najlepsze postępy w ocenie uzyskanej z głębszą analizą. Schemat blokowy algorytmu do znalezienia oceny w głębokości przedstawiono na rysunku 4.
Rysunek 3 - Diagram blokowania do wyboru lepszego udaru
Rysunek 4 - Diagram blokowania, aby wyszukać ocenę
Kiedy nazywasz algorytm do znalezienia oceny na głębokość z bardzo dużą wymaganą głębokością, otrzymujemy ocenę z pełną integralnością wszystkich możliwych ruchów.
2.3 metodanegatywnymaksymalny(Negamax)
W tym algorytmie statyczne oszacowanie pozycji dla jednej ze stron jest równe statycznej ocenie drugiej strony z przeciwnym znakiem.
Rysunek 5 - Metoda ujemnego maksimum
2.4 Statycznyocenapozycjaikonserwacjawymaganiadoszacowanyfunkcje
Oszacowanie statyczne położenia jest metodą obiektywnej, ilościowej ekspresji subiektywnego odczucia, które występuje u osoby patrzącej na stanowisko, bez analizowania możliwych sposobów rozwoju gry. W grach programistycznych ocena pozycji statycznej nazywana jest funkcją jakości pozycji.
Jeśli znalezienie lepszego ruchu za pomocą drzewa gry można zastosować z tym samym sukcesem dla wszystkich gier, a następnie ocena pozycji statycznej jest częścią specjalistyczną dla określonej gry. Jego specjalizacja definiuje styl gry sztucznego gracza, czynniki określone w szacowanej funkcji określają cel zgiełku.
Porównanie liczby z pozycją umożliwia odróżnienie samochodu złych i dobrych kombinacji. Zdolność do odróżnienia dobrych kombinacji ze złego, określa siłę wirtualnego gracza. W grach dwóch osób, oszacowanie jest wykonane przez jednego z graczy. Jeśli szacunkowa funkcja zwraca dobre oszacowanie dla jednego gracza, musi zwrócić źle dla przeciwnika. Zasada ta jest kryterium stosowania dowolnej funkcji wyceny w algorytmach, które wdrażają sztuczną inteligencję.
Podstawowym wymogiem funkcji oceny jest jego symetria w stosunku do graczy, tj. Stan musi być wykonany - co jest dobre dla jednego gracza, złego dla drugiego. Dobra szacunkowa funkcja powinna uwzględniać podstawowe zasady strategii gry i odpowiedzieć na następujące cechy:
* Materiał - obliczony bezpośrednio jako różnicę w liczbie kształtów graczy, możliwe jest dodanie współczynników wagowych dla każdej konkretnej figury
* Pozycjonowanie - pokazuje jakość liczb odtwarzacza
* Rozwój pozycji - pokazuje liczbę możliwych ruchów graczy. Im lepsza pozycja jest opracowana, bardziej możliwe strategie ma gracza. Z tego powodu konieczne jest kontrolowanie i zmniejszenie stanu wroga
* Śledzenie końca gry - w przypadkach wygranej (biorąc król przeciwnika), powinien dać maksymalną rating, zwykle + nieskończoność, w przypadkach utraty (utrata króla), musi zwrócić minimalną ocenę, zwykle nieskończoność
Aby grać w szachy, konieczne jest uwzględnienie zmiany oceny pozycji, w zależności od etapu strony.
Klasyczna szacunkowa funkcja jest funkcją niektórych powyższych cech położenia gry, czyli, że szacowana funkcja jest łącznym wynikiem oszacowania pozycji z różnych punktów widzenia.
Szacowana funkcja dla wszystkich gier jest inna, ponieważ odzwierciedla specyfikę gry. Funkcje oceny są wybrane Eksperymentalnie.
Znaczenie wybranej charakterystyki jest niezbędne. Znaczenie jest określane przez pomnożenie wybranej charakterystyki do odpowiedniego, współczynnika. Współczynnik ten musi mieć uzasadnienie statystyczne.
W związku z tym szacowana funkcja może być reprezentowana w następującym formularzu:
F (P) - Funkcja Szacowana według pozycji p,
Współczynnik ważności charakterystyki I-OH,
Charakterystyka pozycji I-Aya P.
2.5 Inscenizacjazadania
Podczas wykonywania pracy konieczne jest zbadanie istniejących metod i algorytmów do wdrożenia komputerowego gry w szachy, określić ich główne zalety i wady, w celu oparte na zdobyciu wiedzy, wybierz algorytm, który zapewnia najlepszą obsługę ten system.
Po pracy dyplomowej konieczne jest:
wdrażam badane algorytmy w języku programowania C #
wdrażam różne modyfikacje przy użyciu dodatkowych modułów
b Przeprowadzić eksperymenty numeryczne, aby oszacować jakość opracowanych modeli, porównują wdrożone modyfikacje, aby wybrać najlepsze
le Opracuj wygodny i intuicyjny interfejs
3. Zbadanyalgorytmyisuplementy
3.1 Alpha betakontyntynuj
Czyszczenie alfa-beta (angielski alfa-beta przycinanie) jest algorytm wyszukiwania, który wydaje się zmniejszyć liczbę węzłów ocenianych w drzewie wyszukiwania algorytmu Minimax. Główna idea jest następująca: jeśli jeden z twoich ruchów, przeciwnik ma dla ciebie niekorzystną odpowiedź, jest bez znaczenia, że \u200b\u200banalizuje inne możliwe odpowiedzi na ten ruch, ponieważ nawet jeśli wśród nich są dla ciebie bardziej korzystne, przeciwnik będzie nie wybieraj ich. Clipping Alpha-Beta jest optymalizacją, ponieważ wyniki zoptymalizowanego algorytmu nie są zmieniane.
Rysunek 6 - Algorytm wycięcia alfa-beta
Zaleta odcięcia alfa-beta faktycznie polega na tym, że niektóre gałęzie drzewa wyszukiwania mogą być wyłączone po całkowitym uwzględnieniu przynajmniej jednej z gałęzi poziomu. Ponieważ odcięcie występuje na każdym poziomie zagnieżdżania (z wyjątkiem ostatnich), efekt może być dość znaczący. Skuteczność sposobu znacząco wpływa na wstępne sortowanie opcji (bez rzucania lub mniejszej głębokości) - podczas sortowania większych opcji "dobrych", tym większe są odcinki "złe" gałęzie można odciąć bez wyczerpującej analizy. Wyszukiwanie Minimax jest wykonywane w głębi, więc w dowolnym momencie wystarczy rozważyć węzły wzdłuż jedynej ścieżki na drzewie.
Kluczową ideą przycinania Alpha - Beta jest znalezienie kursu niekoniecznie najlepszego, ale "wystarczająco dobrego" w celu podjęcia właściwej decyzji.
Na wejściem tego algorytmu serwowane są parametry alfa i beta, nazywane są one okno. Parametry te są odpowiedzialne za granice odcięcia na pierwszym poziomie, podczas pogłębiania się do drzewa gry, te parametry zmieniają się. Algorytm alfa-beta z parametrami alfa \u003d + nieskończoność i beta \u003d nieskończoność (brutalna siła z pełnym oknem) daje wynik dokładnie taki sam jak algorytm Negamax, to jest pełne biust. Figura 7 przedstawia schemat blokowy algorytmu algorytmu alfa-beta, aby policzyć oszacowanie pozycji w głębokości.
Rysunek 7 - Schemat Alpha-Beta, aby wyszukać ocenę
3.1.1 Przykładstandardodciąć
Rysunek 8 - Przykład standardowych przycinania
Rozważmy przykład standardowej odcięcia Alpha Beta. Na stanowiskach wybieramy więc ruch, dlatego wybramy największą wartość z pozycji w i C. Wartość w już obliczonej - jest to 10. Przy obliczaniu pozycji z jej wyróżniającym się, jeden z węzłów ma wartość 5 . W pozycji z ruchem nasz przeciwnik zrobi, a zatem wybrał najmniejszą wartość. Z tego wynika, że \u200b\u200bwartość pozycji C będzie od 5 i poniżej, dlatego zawsze wybieramy w opcji. Dlatego obliczanie reszty węzłów, które nie prowadzimy.
3 .1.2 Przykładdogłębnyodciąć
Rysunek 9 - Przykład klipu dogłębnego
Rozważmy przykład głębokiego przycinania. Na stanowiskach wybierzemy między podróżami w pozycji i C. Wartość B \u003d 15. Rozpoczynamy obliczenie C. W pozycji E jeden z węzłów dał wartość 5. W pozycji E, wybór skoku należy do przeciwnika, co oznacza, że \u200b\u200bkońcowa wartość E będzie od 5 i niższa. Jeśli wartość C jest równa E, wybierzemy opcję, ponieważ jest bardziej atrakcyjna. Dlatego niekoniecznie znamy dokładną wartość pozycji E, więc wszystkie inne gałęzie są odcięte z niego.
3 .2 Wielokrotnyzanurzenie(IterowanyPoglądający.)
Znaczenie ucieczki wydechowej lub iteracyjnej wnęki leży w powtarzającym się wezwaniu do ustalonej procedury głębokości przy rosnącej głębokości, aż określony termin nie zostanie przekroczony lub głębokość wyszukiwania nie zostanie osiągnięta. Zaletą tej metody jest to, że nie powinieneś wybrać głębokości wyszukiwania z góry; Ponadto zawsze możesz używać wyniku ostatniego zakończonego wyszukiwania. Wartości zwracane z każdego wyszukiwania mogą być używane do regulacji żądanego okna wyszukiwania.
Ogólnie rzecz biorąc, klip alfa-beta jest spowodowany z górnej części drzewa w przedziale (- ?; +?). Jednak przy użyciu iteracyjnego zanurzenia możemy go zmienić.
Przypuśćmy, że X - wartość optymalnego ruchu znalezionego na poprzedniej iteracji, a liczba Epsilon oznaczy szacowaną różnicę w wynikach między poszukiwaniem głębokości D-1 i głębokości D. Dalej, po prostu zadzwonić do alfa -Beta cięcia z górnej części drzewa z szacowanym przedziałem: Alphabeta (D, X-Epsilon, X + Epsilon).
1. Wartość zwraca w przedziale (X-Epsilon, X + Epsilon) jest poprawną wartością, możemy go użyć.
2. Wartość powróci z interwału (X-Epsilon, X + Epsilon) konieczne jest powtórzenie obliczeń ze zmodyfikowanym interwałem.
Nawet jeśli zakładamy, że metoda alfa-beta odcięcia nie daje żadnej zwycięstwa, ogólny wzrost analizy czasu rzeczywiście okaże się stosunkowo mały. Rzeczywiście, zakładając, że średnia liczba opcji na każdym poziomie jest D, a liczba analizowanych poziomów jest p, a następnie iteracyjne wyszukiwanie na pierwszy poziomie, a następnie drugi itp. do poziomu PO, odpowiednik (bez przycinania alfa-beta) Widok D + + ... + Pozycje.
Kwota ta jest równa, podczas gdy liczba pozycji oglądanych w konwencjonalnej analizie jest równa. Stosunek między tymi dwoma liczbami w dużym stopniu p jest mniej więcej taki sam, a zatem blisko 1 w przypadkach, gdy D jest wystarczająco duży
Ponadto, przy użyciu wyszukiwania iteracyjnego można wprowadzić kontrolę czasu, co pozwoli na komputer w dowolnym momencie, aby zaoferować zadowalające rozwiązanie. W ten sposób, jeśli czas myślenia jest ograniczony do 5 sekund, rozważy wszystkie pozycje do poziomu 2, na przykład, w 0,001 sekundy, do poziomu 3 - w 0,01 sekundy, do poziomu 4 - w 1 sekundzie, a następnie po Rozpoczęcie analizy na poziomie 5 zostanie zmuszony do przerwania z powodu braku czasu. Jednak w tym samym czasie komputer ma już dość dobre rozwiązanie znalezione na 4 poziomie.
W rezultacie komputer jest w stanie udzielić odpowiedzi w określonym czasie (na przykład, aby wykonać 50 ruchów w ciągu 2 godzin). Jest również oczywiste, że program, który obsługuje taką metodę, będzie grać z różnymi stronami na różnych komputerach.
Pomimo faktu, że kilka gałęzi drzewa będą musieli sprawdzić kilka razy, ta metoda daje wystarczającą ilość odcięcia.
3.3 Sortowanieruchy
Wyniki odcięcia alfa-beta są bardzo pod wpływem, w jakiej kolejności sprawdzane są ruchy. Rozważ to na przykładach:
W pierwszym przypadku przeprowadzimy obliczenia sortowanie ruchów "z najgorszego na lepsze"
Rysunek 10 - Alpha-beta odcinając ruchy "z najgorszego na lepsze"
Jak widać z przykładu, nie odcięto gałęzi drzewa.
Teraz uporządkuj ruchy "z najlepszych do najgorszego"
Rysunek 11 - Alpha-beta wycinanie ruchów "z najlepszych do najgorszego"
W optymalnych okolicznościach brutalna siła z odcięcia alfa-beta powinna być oglądana przez w ^ ((D + 1) / 2) + w ^ (D / 2) - 1 pozycja. Jest znacznie mniejszy niż minimam.
Aby zwiększyć wydajność odcięcia alfa-beta, musisz pomyśleć o tym, jakie ruchy należy zbadać najpierw. W tych celach stosuje się tak zwane heurystyki zabójcy.
Chodzi o to, że jeśli ruch był dobry w jednej części drzewa, a jeśli jest to możliwe, warto spróbować go sprawdzić w innych (na tej samej głębokości). W tym celu wprowadzono tablicę, w którym wprowadza się kilka najlepszych ruchów dla każdej głębokości, jeśli istnieją ruchy z tej tabeli w pozycji dla bieżących głębokości - są one najpierw sprawdzane.
W przypadku innych ruchów algorytm woli porusza się z Shaghasem i przyjmuje.
3 .4 Nega Scout.(Negascicout)
Negascicout - dodatek na Alpha Beta. Jest to skierowany algorytm wyszukiwania, aby obliczyć wartość węzła Minimax.
Negascicel jest najpopularniejszym algorytmem wysiłku brutto dzisiaj. Jest to niezwykle proste i zapewnia akcelerację (do 50%) bez podejmowania dodatkowego błędu w obliczeniach. Łączy bardzo dobrze z nowoczesnymi atrybutami programów szachowych - stoły Hash.
Ten algorytm ma zaletę, że nigdy nie zbadamy węzłów, które można odciąć alfa-beta, ale niektóre gałęzie można traktować kilka razy.
Algorytm Negalizacji sprawdza pierwszy węzeł za pomocą pełnego okna (Alpha, Beta), biorąc pod uwagę tę opcję jest najlepsza. Następujące węzły, które próbuje odciąć się z zerowym oknem, tj. Okno (alfa, alfa + 1). Jeśli wynik konta poprawia alfa, oznacza to, że 1 węzeł nie był najlepszy, a ten węzeł musi być sprawdzany za pomocą pełnego okna, ale zamiast alfa, możemy wziąć wartość (wartość, beta). Kod tej metody jest poniżej:
public Int Negascicout (komórka [,] Kopiaboard, Int Głębokość, int finalDepth, int alfa, int beta, int możliwości, bool ismy)
int Value \u003d 0, Maxvalue \u003d -1000, Leight \u003d 0;
Komórka [,] Board \u003d nowa komórka;
Punkt [,] ruchy \u003d nowy punkt;
Punkt ruchu \u003d nowy punkt;
FindMoves (ruchy, Ref Leight, Board, True, True);
Możliwe \u003d Leight;
FindMoves (ruchy, Ref Leight, Board, False, True);
Możliwości + \u003d Leight;
jeśli ((głębokość \u003d\u003d finaldepth) || Gameisover (deska, ismy))
wróć eval (deska, możliwości);
powrót -1 * Eval (deska, możliwości);
FindMoves (ruchy, Ref Leight, Board, HaversquiredMove (Board, ISMY), ISMY);
int a \u003d alfa, b \u003d beta;
dla (int i \u003d 0; ja< leight; i++)
Copymove (ruch, ruchy, i);
Domove (deska, ruch);
Wartość \u003d -1 * Negascicout (deska, głębokość + 1, finaldepth, -1 * b, -1 * a, możliwe,! Ismy);
jeśli (wartość\u003e wartość A && a \u003d -1 * Negascicout (deska, głębokość + 1, finalDepth, -1 * beta, -1 * Wartość, możliwości ,! ISMY); jeśli (wartość\u003e a) Copyposition (Board, Copyboard); Jak widać z powyższego opisu dla negatywnego harcerza, przejście ruchów jest ważną funkcją. Jeśli zorganizujesz wszystkie ruchy "z najgorszego na lepsze", popiersie może potrwać jeszcze więcej czasu niż minimax. 3
.5
Tabela Hash. 3
.5
.1
Teoria W szachach podczas wyszukiwania okazuje się, że nie ma drzewa gry, ale wykres jest bardzo często po ruchach ruchów, które otrzymujemy tę samą pozycję. Metoda używania tabel Hash jest utrzymanie oceny już uważanych za pozycje. Dla każdej pozycji konieczne jest przechowywanie jego oceny (dokładniej, uznania w tej pozycji), głębokość rozwojem, najlepszy ruch. Teraz, zaczynając demontować pozycję, musisz wyglądać - i czy nie spotkaliśmy już tego? Jeśli się nie spotkałeś, to robimy to jak wcześniej. Gdybyśmy poznali, patrzymy na głębokość, którą wcześniej byliśmy zdemontowani. Jeśli tak samo, jak potrzebujemy teraz, albo głębiej, możesz użyć starego szacunku i oszczędzać czas. Jeśli jest mniej, nadal możemy używać części informacji, a mianowicie najlepszy ruch. Najlepszy ruch na głębokość N może być najlepszy i dla głębokości N + 1. Oznacza to, że oprócz jej początkowego miejsca docelowego, stół Hash okazuje się przydatny do usprawniania ruchów. Nadal nieoczekiwanie pomaga iteracyjnej wgłębieniu - gdy rozpoczynamy następną iterację, stół Hash okazuje się być wypełniona informacjami z poprzedniego, a do chwili (na głębokość 1), wszystkie pozycje po prostu mają w nim, z najlepszym sposobem do głębokości N-1. Program przy użyciu iteracyjnej wnęki i stole Hash często wykonuje wszystkie iteracje od 1 do N kilkakrotnie szybciej niż gdyby słusznie zaczyna się iteracja n, ponieważ Z prawdopodobieństwem 75%, zawsze jest to pierwszy wybór najlepszego kursu, a z prawdopodobieństwem ~ 90% najlepszy ruch należy do pierwszych trzech rozpatrywanych. 3
.
5
.2
Sprzedaż Hashing jest jednym z najpotężniejszych sposobów zwiększenia wydajności komputera. Korzystanie ze stołów Hash jest głównym narzędziem w programowaniu gier w szachy. Tabela Hash - reprezentuje dużą tabelę indeksowaną w komórkach, z których przechowywane są następujące informacje: · 2 Indeks Hesh · Głębokość błędu do tego ruchu · Ocena tego ruchu Wybór algorytmu obudowy indeksu obudowy jest istotnym punktem przy użyciu algorytmów mieszania. Wybierając algorytm do obliczania indeksu Hash, należy wziąć pod uwagę 2 najważniejszych punktów: Indeks musi najbardziej odzwierciedlać unikalne informacje o postępach, aby zminimalizować liczbę kolizji. Indeks Hese powinien być prosty do liczenia Złożony algorytm daje najlepsze wskaźniki liczby kolizji, ale są trudne do przeliczenia, a zatem zajmują dużo czasu procesora. Konieczne jest zbudowanie algorytmu, łatwe do liczenia, ale mając minimalnie liczbę kolizji. Aby obliczyć indeks, wybrano operacje z niektórymi losowo wygenerowanymi maskami. Początkowo maski Hash są wypełnione losowymi liczbami. Dla każdej pozycji oblicza się 2 indeks HESH, pierwszy służy do wyszukiwania pozycji w tabeli Hash, drugi, aby sprawdzić zderzenia. Przed użyciem informacji z tabeli Hash, zbieg okoliczności drugiego indeksów Hash zostanie sprawdzone, jeśli nie zbiegły, a następnie wystąpiła kolizja, a informacje są ignorowane. Aktualizowanie informacji o pozycji powinny być wykonywane tylko wtedy, gdy głębokość niedoboru prądu jest większa niż ta już przechowywana w tabeli Hash. Informacje z Wath, możliwe jest zaufanie tylko wtedy, gdy głębokość znajduje się w Haheus, więcej niż obecna głębokość aklującego. 3.6
Za pomocąbibliotekideutov. Algorytm przy użyciu bibliotek debiutów jest wykorzystanie wstępnie obliczonych baz danych z debiutami stron, ponieważ na początku strony największa liczba możliwych ruchów tych samych szacunków. 3
.7
Ocenapozycja Podczas opracowywania algorytmu oceny stanowiska statycznego (funkcja jakościowa) istnieje niepewność wyboru między jakością a szybkością. Jakościowe funkcje szacunkowe oparte na podstawie podstawy statystycznej powoli, ale zapewniają bardzo dokładne szacunki, niektóre nawet bez użycia depozytu wywiadowcze. Znacznie szybsza, proste funkcje pracują, biorąc pod uwagę najprostsze zasady gry, nie podają dokładnej oceny, ale pozwalają na głębokie wyszukiwanie. Tak więc dokładny, ale powolny wynik, może dać się głupi, ale szybko. Jakość oceny jest określona przez wiedzę o grze, na podstawie której pozycja jest porównywana. Jakość oceny jest bezpośrednio proporcjonalna do prędkości działania i objętości wiedzy. Ponieważ 40-letnia praktyka tworzenia programów ze sztuczną inteligencją pokazuje, wielkość znajomości funkcji oceny jest odwrotnie proporcjonalna do jego prędkości. Graficzny, ta zależność jest pokazana na rysunku w postaci rodziny hiperballa. Rysunek 12 - Przykład klipu dogłębnego Podczas opracowywania funkcji oceny szachy należy pamiętać, że w zakresie oceny w szachy wszystkich parametrów zależą od etapu gry. Szansa jest udostępniana na scenie: Debiut - otwarcie imprezy, Mittelspil - środek gry, Endgame jest ostatnim etapem. W przypadku algorytmu postanowiono podzielić strony na 3 etapy o liczbie liczb pozostawionych na desce z odtwarzaczem komputera. Początkowo na tablicy na 16 postaciach na graczy. Tabela przedstawia zależność etapu gry z liczby pozostałych liczb: Tabela 1 - Etapy gry 3
.
7
.1
Materiałocena Zaletą materiału jednego z graczy uważa się za najważniejszy parametr w teorii szachowej, dlatego ocena materiałów ma największy wpływ na ogólną ocenę stanowiska. Ocena materiału jest uważana za sumę współczynników wagowych wszystkich kształtów na pokładzie. Król nie jest wliczony w oszacowanie materiału, jak w przypadku utraty Króla, gracz automatycznie traci. Ocena skal danych jest głównym zadaniem w konstruowaniu funkcji oceny. Aby określić łuski liczb, postanowiono skorzystać z samodzielnego algorytmu na podstawie algorytmu genetycznego. Ciężary figur nie zależą od etapu gry. Algorytm genetyczny jest heurystycznym algorytmem wyszukiwania używany do rozwiązywania problemów optymalizacyjnych i symulacyjnych przez wybór losowy, kombinację i zmienność pożądanych parametrów przy użyciu mechanizmów przypominających ewolucję biologiczną po raz pierwszy zaproponowany przez Holland (1975). 3
.
7
.
2
Opispracagenetycznyalgorytm Początkowe zadanie jest zakodowane w taki sposób, że jego roztwór może być reprezentowany jako wektor ("chromosom"). Losowo tworzy wiele wstępnych wektorów ("populacja początkowa"). Są one oceniane przy użyciu "funkcji adaptacyjnej", w wyniku której każdy wektor jest przypisany pewną wartość ("fitness"), co określa prawdopodobieństwo przeżycia ciała reprezentowanego przez ten wektor. Po tym, używając uzyskanych wartości sprawności, wektor (wybór), pozostawiono do "kuszenia". "Operatorzy genetyczne" (zwykle "przekraczanie" i "mutacja") są stosowane do tych wektorów), tworząc w ten sposób następujące "pokolenia". Oceniane są również osobniki następnej generacji, wykorzystywane są wybór, wykorzystywane są operatorzy genetycznymi itp. W ten sposób symulowany jest "proces ewolucyjny", który kontynuuje kilka cykli życia (generacji), aż do wykonywania kryterium zatrzymania algorytmu. Takie kryterium może być: Znalezienie optymalnego rozwiązania; Wyczerpanie liczby pokoleń uwalnianych na ewolucji; Wyczerpanie czasu wydanego do ewolucji. Algorytmy genetyczne służą głównie do znalezienia rozwiązań w bardzo dużych, złożonych przestrzeniach wyszukiwania. W ten sposób można pracować algorytm genetycznym w następnym schorzeniu: Rysunek 13 - Przykład klipu dogłębnego 3
.
7
.
3
Gradacjapracagenetycznyalgorytm Powstanie początkowej populacji - początkową populację jest losowo utworzona; Nawet jeśli okaże się, że jest całkowicie niekonkurencyjny, algorytm genetyczny nadal szybko przetłumaczy na realną populację. W pierwszym kroku można w szczególności nie próbować zbyt dopasowanych osób, wystarczająco, aby dopasować format populacji. Wybór (wybór) - z całej populacji jest wybrana pewna proporcja, która pozostanie "żywa" na tym etapie ewolucji. Przekraczanie (reprodukcja) - w celu uzyskania potomku, potrzebujesz kilku rodziców; Zwykle, oczywiście potrzebujemy dokładnie dwóch. Reprodukcja w różnych algorytmach jest określona na różne sposoby - oczywiście zależy od prezentacji danych. Głównym wymogiem reprodukcji jest to, że potomek lub potomkowie mają okazję dziedziczyć cechy obu rodziców ", mieszając" ich w dość rozsądny sposób. Mutacje są stochastyczną zmianą częściami osób (chromosomy). 3
.
7
.
4
Definicjaważyfigi.zwsparciegenetycznyalgorytm Chromosom algorytmu genetycznego obejmuje ciężary postaci szachowych, z wyjątkiem króla. Aby ustawić początkową populację, wartość chromosoma jest ustawiona losowo w przedziale, z wyjątkiem pionków i ciężarów królowej, wartości ich skali są stałe, pionek - 100, królowa - 1000. Do wyboru używany jest wybór turnieju. Istnieją wśród siebie losowe 2 chromosomy, do czterech zwycięstw, idą najpierw z kolei. Zwycięzca pozostałości pojedynku, przegrany jest usuwany z populacji. Podczas przejścia używany jest metoda przekraczania pojedynczego punktu. Trwa losowo 2 rodziców, liczba chromosomów jest wybierana przez przypadek, diagram jest pokazany na rysunku nr 14. W rezultacie każdy potomek będzie działać zarówno od pierwszego, jak iz drugi rodzic. Rysunek 14 - Przykład klipu dogłębnego Mutacje są wykonywane w następujący sposób: wybiera z pewnym prawdopodobieństwem chromosomu, a one, każdy "gen" zmienia się przez liczbę losową w zakresie [-50; 50], Z wyjątkiem wartości oceny statycznych królowej i pionków. W przypadku wartości końcowych otrzymane wagi są podzielone przez 100. 3
.
7
.
5
Całkowityocena Przy ocenie pozycji narysowanej uwagi na 8 składników: 1. Materiał siły rywali 2. Liczba pól pod bitwą 3. Kluczowe pola 4. Przechodząc spodnie 5. Podwójne pionki 6. Rocking. 7. Promocja pionku 8. Łańcuchy Hound [* 1] Liczba pól pod bitwą oblicza się na głębokości drewna 2, ze względu na duże koszty produkcyjne. Dla każdego pola bije figurę komputera, aby oszacować pozycję dodaje się 1 punkt, dla pól walczących z liczbami gracza są usuwane przez punkty. Wynikowa wartość jest przesyłana do dna drzewa jako parametru. Również na głębokości 2 obliczone punkty dla łańcuchów morskich, przechodzących i podwójnych pionków. Na obecność przybycia na lewe lub prawe pionki, strona otrzymuje 1 punkt. Pionek jest uważany za przejście, jeśli na pionowym, a także na sąsiednim z nią, nie ma rywalowych pionków, którzy mogą uniemożliwić jej przejście do końca. Podwójne pionki - 2 pionki jednego koloru stojącego na jednym pionie. W przypadku obecności podwójnych pionków usuwa się 4 punkty, 5 punktów są dodawane dla obecności każdego pionka przechodzącego. Szachy mają kluczowe pola: Rysunek 15 - Kluczowe pola Dla okupacji każdego z nich to dodatkowe 4 punkty. Dlatego Po złożeniu króla Król jest w bardzo zrównoważonym stanowisku, strona otrzymuje 3 punkty za idealne odlewanie. Im bliżej pionka do ostatniego poziomego, tym bliżej transformacji. Dla każdej komórki dodaje się do wartości pionków dodaje się 1. Po obliczeniu liczby punktów dla obu stron otrzymuje się końcowe oszacowanie pozycji, odejmując punkty gracza z kieliszków przeciwnika komputera. 4
.
Rozwójprograms. 4
.1
Wymaganiadoszachyalgorytm Podczas opracowania modelu modułu oprogramowania do grania w szachy należy wziąć pod uwagę następujące parametry: * Algorytmy w szachy są bardzo wymagające wydajności, a wytrzymałość programu Programu bezpośrednio zależy od wykonania programu * Moduły oprogramowania powinny być łatwe do opracowania i testowania * Interfejs użytkownika powinien być łatwy, łatwy do konfigurowalny i skalowalny 4
.2
Wyświetleniaszachyalgorytm Większość nowoczesnych programów można podzielić na 3 kategorie: * Pierwsza kategoria szybkich poszukiwaczy jest to, że pomysł jest to, że upraszczając limit funkcji oceny i dokładnie z optymalizacją całego programu jako całość (zazwyczaj osiągany przez zapisanie programu na asemblerze), możesz przynieść Liczba pozycji rozpatrywanych przez program (NPS - węzły na sekundę) do numeru astronomicznego, na przykład do 150-200k NPS na P / 200. Oznacza to, że program spędza około jednego lub dwóch tysięcy komend maszynowych do każdej pozycji. Numer ten obejmuje postęp poprzedniego stanowiska, oszacowanie pozycji, wytwarzanie ruchów z tej pozycji, logiki zarządzania itp. Ogólnie rzecz biorąc, szacowana funkcja pozostaje na wszystkich okruchach - około setek zespołów. Programy prowadzone są szaleńczo szybkie i doskonale zachowują się w złożonych pozycjach taktycznych, a także doskonale rozwiązywać zadania kombinacyjne, ale mają słabą grę pozycyjną * Druga kategoria to program oparty na wiedzy. Tutaj wszystkie siły są rzucane do pisania złożonej funkcji wyceny. Oddziaływanie liczb ze sobą, a okładka Króla oraz kontrola pozycji i prawie faza księżyca jest prawie. Jeśli chodzi o NPS, program działa 10-100 razy wolniej niż szybkie wyszukiwania, ale odtwarza dobre szachy pozycyjne. Dokładniej, te szachy są dobre, tylko wtedy, gdy istnieją głębokie taktyki na tablicy lub czas kontroli jest taki, że program ma wystarczająco dużo czasu, aby obliczyć tę taktykę. 4
.3
Kontrolaczasuwszachyalgorytmy Najważniejszym parametrem w konstruowaniu sztucznej inteligencji przeciwnika szachownicy jest kontrolowanie czasu udaru. System gry programu szachowego zależy od kontroli czasowej. Przed komputerem "myślenia", należy obliczyć czas dostępny do komputera. Przy obliczaniu czasu dostępnego na kursie konieczne jest kontynuowanie z dwóch parametrów: * Algorytm poszukiwania lepszej kolejności ma być zbudowany na CrossPower wszystkich możliwych ruchów na pewnej głębokości, a zatem bezpośrednio zależy od czasu spędzonego na popiersie. Im więcej czasu używamy, tym silniejszy jest granie * Czas oczekiwania na odpowiedź przeciwnika komputera nie powinna być zbyt duża. Na przykład, można podjąć międzynarodowe przepisy dotyczące szachów, w których istnieje kilka rodzajów stron: Blitz - 15 minut na imprezę, szybko - 60 minut na partię, klasyczny - ponad 60 minut na imprezie. Na podstawie wymaganych parametrów zdecyduje się obliczyć czas dostępny do ruchu przed następującym wzorem: gdzie: czas na kursie; Full_game_time - Total Party Time; AVG_MOVES - średnia liczba uderzeń gracza na imprezie; Collect_Time - dodatkowo nagromadzony czas; D - Niewielkie zmniejszenie czasu wymagane do dodatkowych obliczeń. Całkowity czas imprezy i średnia liczba ruchów gracza na imprezie są dwa główne parametry zewnętrzne, zmiana, którą można zmienić moc gry. Według statystyk portalu szachowego thechess.ru, średnia liczba graczy dla partii jest równa 30, dlatego postanowiono podjąć średnią liczbę ruchów graczy na imprezie równej 30. Zatem spoza całkowitego czasu ze stron jest ustawiony. Podczas opracowywania algorytmu do zachowania komputerowego przeciwnika (sztuczna inteligencja) zastosowano następujące algorytmy: * Algorytm wyszukiwania iteracyjnego, z kontrolą czasu * Algorytm Alpha-Beta Clipping i Nega-Scout * Biblioteki Debutov. * Stół Hash. * Aby posortować ruchy, wykorzystano heurystyki zabójcy i historii. 4
.4
Rozwiniętyprogram W programie w języku programowania wszystkie powyższe algorytmy i dodatki zostały wdrożone. Zrzuty ekranu programu przedstawiono poniżej: Rysunek 16-kolorowy wybór Rysunek 17 - Screenshot programu Rysunek 18 - Screenshot programu Kiedy najeżdżasz na kształt swojego koloru, jest podświetlony z białym. Przy wyborze figury dla skoku, jego kolor pola staje się pomarańczowy i wszystkie komórki, które postać może iść, wyróżnia się przez biały. Kiedy najeżdżasz na taką komórkę, jego kolor staje się pomarańczowy. Podczas gry idealne ruchy są wyświetlane na tablecie po lewej, gracz może zapisać historię w osobnym pliku. 4
.5
Bazacyklszukajlepszyudar mózgu Głównym zadaniem podstawowego cyklu wyszukiwania najlepszego udaru jest znalezienie i wykonywanie najlepszej drogi do komputera przeciwnika. Cykl wykorzystuje debiutanckie biblioteki i wyszukiwanie iteracyjne z kontrolą czasu. Rysunek 12 pokazuje proces znalezienia lepszego sposobu: Rysunek 19 - Podstawowy cykl wyszukiwania najlepszego kursu 4
.6
Szukajlepszyudar mózgupierwszypoziom Głównym zadaniem algorytmu pracy do poszukiwania najlepszego ruchu pierwszego poziomu (odpowiedź wroga) jest znalezienie najlepszego ruchu przeciwnika na pierwszym poziomie. Algorytm jest zbudowany na algorytmie Negoriitm przy użyciu głębokości oszacowania, aby określić oszacowanie bieżącego skoku. Rysunek 13 przedstawia pracę algorytmu: Rysunek 20 - Szukaj lepszego pierwszego poziomu 4
.7
Odkryciegłębokośćszacunkiudar mózgu Głównym zadaniem znalezienia ocenę głębokości jest znalezienie oceny bieżącego kursu przy użyciu algorytmu Negchout, heurystyki zera, dane z tabeli ma tabelę i oceną pozycji statycznej. Rysunek 14 przedstawia proces liczenia oceny kursu dogłębnej: Rysunek 21 - Znalezienie głębokiej oceny skoku 4.8
Inni.modeleiwykres Model matematyczny programu jest następujący: Rysunek 22 - Model matematyczny Z abstrakcyjnej klasy obliczają 7 klas spadkobierców opisujących działania i właściwości danych liczbowych. Istnieje również klasa pustych, oznaczająca, że \u200b\u200bkomórka jest pusta. Płyta jest tablicą 64 elementów figury, z których każdy może stać się dowolnym z klas dziedzic. Kurs w komputerze jest reprezentowany w postaci 4 cyfr - współrzędnych (od 1 do 8) punktu rozpoczęcia i współrzędnych końca końca. Poniżej znajduje się diagram statusu dla programu: Rysunek 23 - Wykres warunku 5
.
Eksperymentalnyocenajakośćr.ealiz.anno.algorytm
Wdrożone algorytmy poddano analizie porównawczej w celu określenia optymalnej prędkości i jakości konfiguracji. Podczas eksperymentu odbyło się wiele turniejów między każdą parą różnych implementacji. 5
.1
OcenapracaAlpha betaodciąć Dzięki temu eksperymentowi było konieczne, aby dowiedzieć się, czy czynnik rozgałęzienia został zmniejszony, a w wyniku poprawy prędkości algorytmu, bez utraty jakości decyzji w sprawie kursu zleconego. Aby ocenić jakość końcowego algorytmu, algorytm wyszukiwania był eksperymentalnie w porównaniu z zasadą minimax. Tabele przedstawiają współczynniki wykazujące ocenę liczby elementów do algorytmów, a także stosunek czasów przypisanych do tego przeglądania. Tabela 1 - Porównanie wskaźników algorytmu algorytmu algorytmu odcięcia z algorytmem Minimax. Wyniki eksperymentów pokazują, że przycinanie Alpha-Beta jest znacznie lepsze niż proste wyszukiwanie Minimax. 5
.2
Ocenapracawielokrotnynurkowaćisortowanieruchy Aby ocenić jakość algorytmu, ten algorytm wyszukiwania z odcięcia ALFA-Beta i po prostu odcięcia alfa-beta jest porównywane doświadczalnie. Opis zasad gry "Battle morskie". Cechy nowoczesnych komputerów i sztucznej inteligencji. Tworzenie wspólnego diagramu bloku programu, jego wygląd. Wymagane zmienne, procedury i funkcje. Charakterystyka obiektów używanych w aplikacji. zajęcia, dodane 05.11.2012 Rozwój oparty na grze "punkt" podejście do programowania "sztucznej inteligencji" w grach pozycyjnych i możliwości zastosowania tego podejścia do rozwiązywania problemów w dziedzinie ekonomii, zarządzania i innych regionów naukowych. Model sytuacji do gier. teza, dodano 07/21/2013 Strukturalny diagram modułu oprogramowania. Opracowanie modułu oprogramowania i schematu interfejsu użytkownika. Wdrożenie modułu programu: Kod programu; Opis używanych operatorów i funkcji. Widok niestandardowej formy z wypełnioną matrycą. praca kursu, dodano 01.09.2010 Badanie ogólnych zasad gry w warcaby, instrukcji obsługi i programista. Charakterystyka głównych algorytmów wykonujących zadania klasowe widgetów życia. Ocena ruchów komputera i człowieka. Budowanie drzewa wyszukiwania drzewa na podstawie oceny funkcji. egzamin, dodano 12/20/2012 Główne etapy rozwoju, zasady testowania i debugowanie modułu Software VFS. Funkcje projektowania w UML. Metody "zgrubnej mocy" i ich zastosowania podczas debugowania programu. Szkodliwe czynniki obecne w miejscu pracy programisty. teza, dodano 03/07/2012 Analiza modeli i metod wdrażania inteligentnych gier w systemie osoby robota. Środowisko rozwoju Choreographe. Algorytmy modułu rozpoznawania, przetwarzania danych, funkcji modułu gry. Testowanie pakietu oprogramowania, poprawiania i energii. teza dodana 12.08.2017 Esencja i problem określenia sztucznej inteligencji, głównych zadań i funkcji. Problemy filozoficzne tworzenia sztucznej inteligencji i zapewnienie bezpieczeństwa ludzkiego podczas pracy z robotem. Wybór sposobu na tworzenie sztucznej inteligencji. egzaminowanie dodane 07.12.2009 Program gier "warcaby" do gry między mężczyzną a komputerem. Rozwój algorytmów, historyczny rozwój zadań. Różne podejścia do systemów budowlanych. Skrócona lista programów i opisu algorytmu. Składniki sztucznej inteligencji. praca kursu, dodano 03/26/2009 Budowanie i analizowanie modelu matematycznego gry. Określenie prawdopodobieństwa wykrywania statków o wszystkich możliwych lokalizacjach i różnych systemach wyszukiwania. Rozwój algorytmów do sztucznej inteligencji. Struktura programu i jego składników. zajęcia, dodano 12/22/2012 Koncepcja sztucznej inteligencji jako właściwości automatycznych systemów do podjęcia poszczególnych funkcji ludzkiej inteligencji. Systemy eksperckie w dziedzinie medycyny. Różne podejścia do budowania sztucznych systemów inteligencji. Tworzenie sieci neuronowych. Rozważmy podstawowe koncepcje, które pomogą nam stworzyć prostą sztuczną inteligencję, która może grać w szachy: Na każdym kroku poprawimy nasz algorytm za pomocą jednego z tych sprawdzonych metod programowania. Zobaczysz, jak każdy z nich wpływa na styl gry algorytmowej. Gotowy algorytm można znaleźć na GitHub. Użyjemy bibliotek Chess.js do generowania ruchów i szachownicy.js, aby wizualizować planszę. Biblioteka do wytwarzania ruchów wdraża wszystkie zasady szachy. Na tej podstawie możemy obliczyć wszystkie ruchy do tego stanu zarządu. Wizualizacja funkcji wytwarzania funkcji. Początkowe położenie jest używane jako wejście, a na wyjściu - wszystkie możliwe ruchy z tej pozycji. Wykorzystanie tych bibliotek pomoże nam skupić się tylko na najciekawszym zadaniu - tworzenie algorytmu, który znajduje najlepszy kurs. Zaczniemy pisać funkcję, która zwraca losowy kurs ze wszystkich możliwych ruchów: Var calculatebestmove \u003d funkcja (gra) (// generacja wszystkich ruchów do tej pozycji VAR Newgamemoves \u003d Game.Ugly_Moves (); zwrot newgamoves;); Chociaż algorytm ten nie jest bardzo solidnym graczem szachowym, ale jest to dobry punkt wyjścia, ponieważ jego poziom wystarczy, by bawić się nami: Czarna gra przez przypadkowe ruchy JSFiddle. Teraz spróbuj zrozumieć, który z boków jest silniejszy w pewnej pozycji. Najprostszym sposobem na osiągnięcie jest obliczenie względnych mocnych danych liczb na płycie przy użyciu poniższej tabeli: Korzystając z funkcji oceny, możemy utworzyć algorytm, który wybiera najwyższą ocenę: Var CalculateBestMove \u003d Funkcja (gra) (Var Newgamemoves \u003d gra< newGameMoves.length; i++) {
var newGameMove = newGameMoves[i];
game.ugly_move(newGameMove);
//Возьмите отрицательное число, поскольку ИИ играет черными
var boardValue = -evaluateBoard(game.board())
game.undo();
if (boardValue > BestValue) (BestValue \u003d BoardValue; Bestmove \u003d NewgameMove)) Powrót Bestmove; ); Jedyną rzeczącym poprawą jest to, że teraz nasz algorytm będzie zjeść postać, jeśli to możliwe: Czarna gra za pomocą prostej funkcji oceny Zobacz, co się stało na tym etapie, możesz w JSFiddle. Następnie stworzymy drzewo wyszukiwania, z którego algorytm może wybrać najlepszy kurs. Odbywa się to za pomocą algorytmu "Minimax". Około. Tłumaczyć W jednym z naszych artykułów już się zajmowaliśmy - nauczyłem się stworzyć AI, co niemożliwe jest pokonanie w Noliki Cross. W tym algorytmie rekurencyjne drzewo wszystkich możliwych ruchów jest badane na daną głębokość, a pozycja szacowana jest na "liściach" drzewa. Następnie wracamy najmniejszą lub najbardziej potomną wartość w węźle macierzystym, w zależności od tego, czy kurs jest obliczany (to znaczy, staramy się zminimalizować lub zmaksymalizować wynik na każdym poziomie). Wizualizacja minimax w sztucznej pozycji. Najlepszy udar na biały - B2-C3, więc możemy zagwarantować, że dotrzemy do pozycji, w której oszacowanie jest równe -50 VAR MINIMAX \u003d Funkcja (Głębokość, gra, IsMaxImisingPlayer) (jeśli (głębokość \u003d\u003d\u003d 0) (Return -evaluateboard (Game.board ());) var Newgamemoves \u003d Game.ugly_moves (); -9999; dla (var i \u003d 0; ja< newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
game.undo();
}
return bestMove;
} else {
var bestMove = 9999;
for (var i = 0; i < newGameMoves.length; i++) {
game.ugly_move(newGameMoves[i]);
bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
game.undo();
}
return bestMove;
}
};
Z Minimax nasz algorytm zaczyna rozumieć główną taktykę szachy: Minimax z poziomem głębokości 2 Zobacz, co się stało na tym etapie, możesz w JSFiddle. Wydajność minimax zależy w dużej mierze zależy od osiągalnego głębokości wyszukiwania. To właśnie będziemy poprawimy się w następnym kroku. Pozycje, których nie potrzebujemy, jeśli używany jest klips Alpha Beta. Drzewo jest odwiedzane w opisanej kolejności. Z Clipping Alpha Beta otrzymujemy znaczącą poprawę Minimax, jak pokazano w poniższym przykładzie: Liczba pozycji, które należy oszacować w przypadku wyszukiwania z głębokością 4 i początkową pozycją pokazaną na zdjęciu. Zobacz, co się stało na tym etapie, możesz w JSFiddle. Początkowa funkcja oceny jest ładna naiwna, ponieważ po prostu policzymy punkty figur, które są na pokładzie. Aby go poprawić, zaczniemy rozważyć pozycję figur. Na przykład konia w środku zarządu "Droższe", ponieważ ma bardziej dostępne ruchy, a zatem bardziej aktywne niż konia na krawędzi płyty.Podobne dokumenty
Krok 1. Wytwarzanie ruchów i wizualizacji szachownicy
Krok 2. Tablica wyników
Krok 3. Wyszukaj drzewo i minimam
Krok 4. Klip Alpha Beta
Krok 5. Ulepszona funkcja oceny
