Zasady. Ustawione krzesła są polami, tak jak w grze kółko i krzyżyk. Zasady są podobne: wygrywa drużyna, która ustawi 3 krzyżyki lub 3 kółka w rzędzie pionowym, poziomym lub skośnym. Na sygnał trenera osoby z każdej drużyny będą siadały (pojedynczo i na przemiennie z drugą drużyną) na wybranych przez siebie krzesłach. Tic Tac Toe, Dodelschach, Drei gewinnt to najczęstsze tłumaczenia "kółko i krzyżyk" na niemiecki. Przykładowe przetłumaczone zdanie: dadzą ci podkładkę i papier ale nie graj w kółko i krzyżyk. ↔ Sie werden dir einen Notizblock geben, aber spiel darauf kein Tic Tac Toe. kółko i krzyżyk. gramatyka. Kolko Krzyżyk z Imieniem na Allegro.pl - Zróżnicowany zbiór ofert, najlepsze ceny i promocje. Wejdź i znajdź to, czego szukasz! Tak więc w loterii kółko i krzyżyk były widoczne pewne liczby, stały się kluczem do ustalenia zwycięzców. Tajny kod okazał się prawdopodobnie prosty. Podczas dochodzenia Mohan uszeregował liczby na podstawie liczby ich występów na karcie i określił Zwycięskie bilety na podstawie powtórzeń liczb i sposobu ich powtarzania. Znalazła jakieś informacje jak wygrać i nie chce powiedzieć. Nie przepadam za nią, ale tak z czystej chciałabym wiedzieć, jak wygrać. Zawsze (jeśli jest pierwsza) stawia kółko na środku i bez wyjątku wygrywa, a jeśli jest druga a ja je dam na środek, to daje w róg a i tak jakoś jej się udaje (czasami jest remis). Vay Tiền Trả Góp Theo Tháng Chỉ Cần Cmnd Hỗ Trợ Nợ Xấu. Ludzi online: 4534, w tym 76 zalogowanych użytkowników i 4458 gości. Wszelkie demotywatory w serwisie są generowane przez użytkowników serwisu i jego właściciel nie bierze za nie odpowiedzialności. Przeciwnik zakreśla przypisanym mu znakiem pole znajdujące się w narożniku kwadratu, na którym rozgrywana jest gra, wówczas należy umieścić własny znak w środku tego kwadratu. W kolejnym ruchu, gdy rywal zakreśli znak na innym polu narożnikowym, należy uniemożliwić mu wygraną poprzez zakreślenie pola między zakreślonymi narożnikami. Jeśli natomiast przeciwnik zarezerwuje sobie pole leżące obok tego wcześniej zakreślonego, należy umieścić swój znak w linii tak, by zablokować rywala. Jeżeli natomiast przeciwnik rozpoczyna rozgrywkę w ten sposób, że umieszcza własny znak w środkowym polu kwadratu, trzeba blokować go zakreślając swój znak w jednym z pól narożnikowych (do wyboru). W następnych ruchach wystarczy już tylko blokować możliwość uzyskania przez przeciwnika całej linii. W sytuacji, gdy przeciwnik umieszcza swój znak w bocznym polu kwadratu, zakreśla się własny znak na środku kwadratu i tak samo jak powyżej – blokuje się w kolejnych ruchach możliwość uzyskania przez przeciwnika linii (w tym przypadki poziomej lub pionowej) stworzonej z jego wersją gry w kółko i krzyżyk jest gomoku, gra powstała w Japonii. W Europie gra ta funkcjonuje często pod nazwą „kółko i krzyżyk na nieograniczonej planszy”. W gomoku wykorzystuje się planszę o rozmiarach 19×19, a niekiedy mniejszą – 15×15. Gracze starają się stworzyć linię pięciu pionów własnego koloru. Przewaga gracza wykonującego pierwszy ruch jest tak duża, że teoretycznie ma on zapewnione zwycięstwo. Jednak ze względu na stopień skomplikowania niewielu graczy potrafi tę szansę zawsze wykorzystać, co wpływa z pewnością pozytywnie na atrakcyjność grać w Kółko i krzyżyk? Z kim gracie najczęściej? Jakie gry jeszcze lubicie? Dajcie znać. Norbert BanasiakNorbert Banasiak - ukończył studia na kierunku stosunki międzynarodowe na Uniwersytecie Warszawskim. Posiada różnorodne doświadczenie redaktorsko-dziennikarskie. Współpracował z Gazetą Prawną, portalem i miesięcznikiem branży rozrywkowej E-PLAY, miesięcznikiem What`up in specjalista pisze o sobie: Lubię w szczególności wszelkie gry, które rozwijają przydatne umiejętności: logiczne myślenie, koncentrację, szybkie podejmowanie decyzji. Moje zainteresowania zawodowe, jak i prywatne, oscylują poza tym wokół zagadnień związanych z kwestiami językowymi (translatoryka, semiotyka), Internetem, polityką międzynarodową. Zobacz też Może Cię zainteresuje: Najlepsza odpowiedź Odgłosy kredy lub ołówka na tabliczce to prawie na pewno źle. Prawdziwa historia jest niepewna. Ale współczesna nazwa „Tic Tac Toe”, którą znajduję już w 1884 roku, jest dość wyraźnie poprzedzona nazwą „Tit-Tat-To” (lub Toe), sięgającą aż do 1818 roku. (Również „Tick Tack Toe” to 1869; „Tip Tap To” do 1849.) Ta wersja nazwy odnosiła się również zarówno do współczesnej gry w tic tac to, jak i do gry w ślepe rzutki, o której mowa w drugiej odpowiedzi. Nazwa może pochodzić od „Tit for tat”, które jest bardzo starym wyrażeniem, które zasadniczo oznacza to, co nadal oznacza. Może to być związane z turowym charakterem gry. Istnieje wiersz związany z grą w różnych formach. Jedną z form jest wiersz używany przez zwycięzcę (ta wersja z 1882 roku). Tit-tat-to, moja ostatnia próba Trzech wesołych chłopców rzeźników wszyscy z rzędu Trzymaj jednego do góry, wbij jednego w dół, wbij jednego w grzebanie starego człowieka. Co jest związane z innym, starszym wierszem: Jajka, Masło, Ser, Chleb, Patyk, Bulion, Kamień, martwy, Wbij go, wbij go, Wbij go w koronę starego człowieka. Ten starszy wiersz jest wymieniony w jednej książce z 1842 r. w sekcji wierszy związanych z grami, bez określenia, jaka gra (może to być po prostu gra polegająca na liczeniu). Ale inna książka z 1846 roku pokazuje ten sam wiersz i mówi, że jest on przeznaczony do „Gry na łupku”. Jedną z możliwości jest to, że „Stick Stock Stone” zamienił się w „tit tat to”, ale w takim przypadku kolejność wydaje się niewłaściwa – spodziewam się, że najpierw przejdzie do „tic tac to”, a później do „tit tat to” (ale może tak było, wydrukowany zapis jest tylko przybliżonym przybliżeniem, a części, które faktycznie znalazłem, to tylko mała część tego przybliżonego przybliżenia). Jedno źródło podaje prawdziwe pochodzenie tego ostatniego wiersza jako niemiecki wiersz krytykujący kościół katolicki, w którym niemieckie słowa zostały arbitralnie przeniesione na angielski. To źródło twierdzi, że niemiecki był faktycznie bliżej „Stich” Stock „s Toe”, co sprawia, że ​​ta zmiana wydaje się jeszcze bardziej prawdopodobna. Właściwie nie mogę datować wiersza przed „tit-tat-to” „, ale jak zauważyła jedna z książek, te ustne wiersze tradycji były ogólnie uważane za zbyt wulgarne, aby można je było umieszczać w książkach, które w tamtych czasach były bardziej skomplikowane i kosztowne do wydrukowania. Powinienem wspomnieć, że istnieje również gra o nazwie „Tick Tack”, której historia sięga co najmniej czasów Szekspira, rodzaj szybkiej wersji Backgammon (zwanego wtedy Tabelami). Jednak ponieważ kółko i krzyżyk jest prawie na pewno pochodną morrisa dziewięciu mężczyzn (a konkretnie trzech morris), myślę, że ta nazwa to tylko zbieg znalazłem też niczego innego, co mogłoby łączyć te dwie gry. Warto jednak zauważyć, że niektórzy ludzie przypisują „Tick Tack” prawdopodobnie powiązaniu z dźwiękiem kości na stole w tryktraka. Prawie cała historia to domysły oparte na cienkich dowodach. Należy pamiętać, że zadając pytania takie jak to. Odpowiedź Tak – jest. Poniższe techniki pokazane poniżej wskazują sposób na „nigdy nie przegraną”, niekoniecznie na wygraną. Najgorszym scenariuszem byłoby jednak remis. Pamiętaj, że są dwie podstawy punkty, na podstawie których możemy nakreślić naszą strategię – Ty idziesz pierwszy, albo przeciwnik jest pierwszy. Ale przyjrzyjmy się kilku podstawowym definicjom. Kontratak – Wykonywanie ruchu, który blokuje przeciwnika Środek – kwadrat pośrodku otoczony wszystkimi innymi kwadratami. Krawędź – Kawałek graniczący ze środkiem. Narożnik – Kawałek ograniczony dwoma kwadratami krawędzi. Ok – dobrze! Mamy trochę podstawowego słownictwa. A teraz zaczynajmy. JEŚLI POTRZEBUJESZ PO PIERWSZE … Unikaj umieszczania pierwszego elementu na krawędzi kwadratu i trzymaj go pośrodku lub narożnika kwadratu. Umieszczenie go na krawędzi pola sprawi, że będziesz bezbronny i zapewni przeciwnikowi przewagę. 1) Środek Jeśli zaznaczysz środek, przeciwnik albo umieści swój pierwszy element na krawędź lub narożnik. Jeśli zaznaczą krawędź, jest niezwykle łatwo wygrać – nie ma nawet szans na remis. Po prostu umieść następny element na jednym z dwóch rogów najbardziej oddalonych od krawędzi. Najprawdopodobniej zablokują ten ruch, co z kolei da im szansę na wygraną. Zablokuj ich ruch i nagle masz dwa sposoby na wygraną, a twój przeciwnik jest bezradny. Jeśli oznaczają róg , jak by to zrobił mądrzejszy przeciwnik, jest to trochę bardziej skomplikowane. Umieść następny znak w przeciwległym rogu lub w rogu, który utworzyłby przekątną dwóch X-ów i jednego O. Jeśli umieści następny na krawędzi, popełnili błąd i teraz masz dwa sposoby na wygraną, w zależności od tego, na której przewadze umieścili swoje O. W przeciwnym razie, zakładając kontynuujesz kontratak, gra zakończy się remisem. 2) Rzut rożny Jeśli najpierw zagrasz narożnik, przeciwnik może zareagować tylko w dwóch znaczących sytuacjach: środkowy lub nie do środka. Jeśli ich pierwszy ruch jest od środka, powinieneś być w stanie wygrać. Pamiętaj, że pierwszy Kawałek jest zawarty zarówno w rzędzie pionowym, jak i poziomym. Następny ruch e powinno znajdować się w drugim rogu tego samego rzędu, w którym umieściłeś pierwszy element. Najprawdopodobniej kontratakują, pozostawiając ci dwie opcje i łatwą drogę do zwycięstwa. To zadziała niezależnie od tego, czy najpierw zagrają róg, czy przewagę. Oto kolejny świetny sposób na złapanie przeciwnika w pułapkę: Jeśli ich pierwszy ruch jest w środku , jest to trochę trudniejsze. Ponownie utwórz przekątną. Jeśli ich następny ruch jest w rogu, możesz je uwięzić, umieszczając następny element na przecięciu rzędu i kolumny dwóch poprzednich X ”. Jeśli ich następny ruch jest na krawędzi, będziesz zmuszony zadowolić się remisem. JEŚLI PRZECIWNIK JEST PIERWSZY … Niestety, jeśli twój przeciwnik idzie pierwszy i używa wszystkich powyższych technik, nie ma możliwości, abyś wygrał. W rzeczywistości jedynym sposobem na wygraną jest jego / jej pierwszy ruch na krawędzi. Jeśli tak, wykonaj wszystkie kroki przedstawione powyżej. Co więc możesz zrobić, aby przynajmniej doprowadzić mecz do remisu, biorąc pod uwagę, że twój przeciwnik gra dobrą strategię? Pamiętaj, co powiedzieliśmy wcześniej – Twój przeciwnik wybierze róg lub środkową figurę. 1) Środek Jeśli wybierze środek, natychmiast umieść swoje O w rogu, co da ci trochę czasu. Zgodnie z najlepszą strategią, twój przeciwnik umieści swój następny X na przeciwległym rogu twojego. Twój następny kawałek nie powinien graniczyć z poprzednim ruchem. W takim razie jest to prosta kwestia ciągłego blokowania i kontrataku, aż do osiągnięcia remisu. Nawet jeśli nie stosują tej strategii, blokuj dalej, aż dojdziesz do remisu. 2) Narożnik Jeśli wyznaczą róg, zaznacz środek, albo prawie na pewno przegrasz z dobrym przeciwnikiem. Następnie pamiętaj, że jest jeden wynik, w którym remis jest możliwy z góry. Twój przeciwnik ma dwie możliwości: ułożyć ukośną lub umieścić następny pionek w innym miejscu. Zakładając, że ich ruch jest ukośny, jak dyktuje strategia, pozostań na krawędziach i poza rogami. W ten sposób możesz wymusić remis. W przeciwnym razie, jak zwykle, blokuj, aż do osiągnięcia remisu. Oczywiście taka jest logika gry w kółko i krzyżyk, ale istnieją pewne przydatne wskazówki, które mogą Ci pomóc podczas gry z dobrym graczem. Nie bądź reakcyjnym, impulsywnym graczem. Jeśli nie ma limitu czasu, poświęć tyle czasu, ile chcesz, zastanawiając się nad przejściem. Nie reaguj natychmiast na to, co robi twój przeciwnik; Czasami najbardziej oczywisty ruch może nie być właściwy. Wykonuj bezpieczne ruchy. Każdy twój ruch powinien być podyktowany strategią – w środku gry najlepszym sposobem na wykonanie ruchu jest przemyślenie kilku ruchów do przodu i tego, co może zrobić przeciwnik. Najpierw zastanów się, czy dany ruch może cię wygrać. lub zablokuj przeciwnikowi wygraną. Jeśli nie, pamiętaj, aby zawsze myśleć strategicznie. Najlepszym sposobem na wygraną jest wymyślenie dwóch sposobów na wygraną naraz. Przeczytaj tę odpowiedź. Zaufaj mi – to pomaga. Uzbrojony w strategię, porady i pewność siebie, możesz pokonać każdego! [1] Jak wygrać w grze Tic Tac Toe (Zdjęcia, materiały) Poprzednio w serii algorytmika gier pochyliłem się nad grą w sapera, gdzie przeanalizowaliśmy, jak generuje się planszę oraz prowadzi rozgrywkę. Teraz spróbujmy przenieść na komputer jedną z najpopularniejszych gier rozgrywanych na kartce — kółko i krzyżyk. Jednak tym razem nie skupimy się na zaprogramowaniu całej rozgrywki, a tylko na jednej rzeczy: sztucznej inteligencji komputerowego wstępnaJak się w to gra?Trochę matematykiStrategia wygrywania w kółko i krzyżyk1. Wygraj2. Zablokuj3. Zrób rozgałęzienie4. Zrób blokujące rozgałęzienie5. Zagraj środek6. Zagraj przeciwny narożnik7. Zagraj pusty narożnik8. Zagraj pusty bokSztuczna inteligencja?Implementacja w kodzieAlgorytm MinimaxIdea algorytmuDrzewo stanu gryOgólny zarys algorytmuImplementacja w kółko i krzyżykInne podejściaLiteratura Uwaga wstępna Podobnie jak w poprzednim artykule o saperze, także i tu zachęcam do spróbowania zaprogramowania algorytmów na własną rękę. Nie jest to wymagane dla zrozumienia artykułu, ale zawsze pomoże wynieść z niego coś więcej. Pod tym linkiem udostępniam szablon zawierający grę w kółko i krzyżyk napisaną w JavaScript z pomocą Reacta. W pliku src/logic/ znajdziesz pustą funkcję computeComputerMove, której zadaniem jest zwrócenie współrzędnych pola, na którym ma zostać wykonany następny ruch. W artykule pokażę dwa algorytmy, więc możesz spróbować zaprogramować oba. Natomiast jeśli chciałbyś/chciałabyś po prostu zobaczyć gotowca, to zapraszam na repozytorium na GitHubie, gdzie znajdziesz gotowe implementacje. Jak się w to gra? Parafrazując klasyka, chciałoby się powiedzieć, że jakie kółko i krzyżyk jest, każdy widzi. Jednak mimo wszystko przypomnijmy sobie podstawowe zasady gry. W najpopularniejszym wariancie grę rozgrywa się na polu o wymiarach 3 × 3. Jeden z graczy gra krzyżykami (najczęściej ten właśnie zaczyna), drugi kółkami. Każdy z graczy na przemian stawia w jednym z niezajętych pól swój symbol. Koniec gry następuje wtedy, gdy któryś z graczy utworzy linię trzech swoich elementów (pionowa, pozioma lub po przekątnej; wówczas wygrywa), albo gdy wszystkie pola zostaną zajęte (remis). Dla utrwalenia zasad możesz zagrać w kółko i krzyżyk z komputerowym graczem poniżej (grasz krzyżykami i zaczynasz). Dokładnie to, co tutaj widzisz, jest efektem tego artykułu. Trochę matematyki Wróćmy do teorii gry w kółko i krzyżyk. Z racji tego, że gra jest turowa i potrzebne są trzy ruchy jednego gracza do zwycięstwa, oznacza to, że każda gra odbędzie się w co najmniej 5 ruchach z 9 możliwych. Daje to niedużą liczbę możliwych rozgrywek. Pierwsze, co przychodzi na myśl, biorąc pod uwagę wiedzę z dziedziny kombinatoryki, to że możliwych rozgrywek jest 9!=3628809! = 362880. Tak jednak nie jest, ponieważ nie zawsze wykorzystujemy całą planszę. Przypomnijmy sobie, że pierwszy gracz może zakończyć grę już po 5 ruchach (3 swoich). Do tego momentu mamy możliwych 9⋅8⋅7⋅6=151209\cdot 8\cdot 7 \cdot 6 = 15120 gier, z czego tylko część jest zakończona. To ile tych gier jest ostatecznie? Możemy to policzyć następująco dla gier kończących się pięcioma ruchami: Mamy 8 możliwości ułożenia 3 symboli w jednej linii. Możemy je układać w dowolnej kolejności na 8⋅3!=488 \cdot 3! = 48 sposobów. Pozostały gracz ma do wyboru 6, a potem 5 pól, gdzie może postawić swój symbol. Daje to liczbę kombinacji 6⋅5=306 \cdot 5 = 30. Łącznie daje to nam 8⋅3!⋅6⋅5=48⋅30=14408 \cdot 3! \cdot 6 \cdot 5 = 48 \cdot 30 = 1440 zwycięskich gier z 15120 możliwych rozegrań do tego momentu. Dla dalszych ruchów obliczenia robią się bardziej skomplikowane, dlatego pominę ich wytłumaczenie, tylko wypiszę wzory: Gry kończące się wygraną w 6 ruchach: 8⋅3!⋅6⋅5⋅4−6⋅3!⋅2⋅3!=53288 \cdot 3! \cdot 6 \cdot 5 \cdot 4 - 6 \cdot 3! \cdot 2 \cdot 3! = 5328. W 7 ruchach: 8⋅3⋅6⋅3!⋅5⋅4⋅3−6⋅3⋅6⋅3!⋅3!=479528 \cdot 3 \cdot 6 \cdot 3! \cdot 5 \cdot 4 \cdot 3 - 6 \cdot 3 \cdot 6 \cdot 3! \cdot 3! = 47952. W 8 ruchach: 8⋅3⋅6⋅3!⋅5⋅4⋅3⋅2−6⋅3⋅6⋅3!⋅2⋅4!=725768 \cdot 3 \cdot 6 \cdot 3! \cdot 5 \cdot 4 \cdot 3 \cdot 2 - 6 \cdot 3 \cdot 6 \cdot 3! \cdot 2 \cdot 4! = 72576. W 9 ruchach: 2⋅3⋅8⋅4!⋅4!+6⋅3⋅4⋅4!⋅4!+22⋅1⋅4!⋅4!=817922 \cdot 3 \cdot 8 \cdot 4! \cdot 4! + 6 \cdot 3 \cdot 4 \cdot 4! \cdot 4! + 22 \cdot 1 \cdot 4! \cdot 4! = 81792. Remisy: 16⋅5!⋅4!=4608016 \cdot 5! \cdot 4! = 46080. Łącznie wszystkich możliwych gier mamy 1440+5328+47952+72576+81792+46080=2551681440+5328+47952+72576+81792+46080 = 255168. Strategia wygrywania w kółko i krzyżyk Specyfika gry w kółko i krzyżyk jest taka, że pierwszy gracz ma zwykle więcej do powiedzenia. W przypadku doświadczonego pierwszego gracza drugi może doprowadzić co najwyżej do remisu. Nie ma możliwości zmiany przebiegu rozgrywki bez błędu przeciwnika. Z drugiej strony, będąc pierwszym graczem, musimy wiedzieć, jak nie dać złapać się w pułapki drugiego gracza, aby bezproblemowo wygrać. Strategia optymalnej gry w kółko i krzyżyk znalazła się nie raz w zainteresowaniu naukowców. To, co tutaj przedstawię, to strategia opisana przez Kevina Crowleya i Roberta S. Sieglera w 1993 r. (doi: Należy ją czytać w taki sposób, że staramy się sprawdzać po kolei warunki kolejnych możliwych ruchów, i gdy taki jest możliwy, wykonujemy go. Całość powtarzamy tak długo, aż ukończymy grę. Strategia ta to tak naprawdę algorytm grania w kółko i krzyżyk. Możesz go wprost zaimplementować w swojej grze, aby mieć bardzo prostą sztuczną inteligencję. Albo po prostu zapamiętać i korzystać przy tradycyjnych rozgrywkach w kółko i krzyżyk. 1. Wygraj Jeżeli: jest wiersz, kolumna lub przekątna z dwoma moimi symbolami i puste miejsce, Wtedy: zagraj na pustym miejscu (i wygraj grę). Trzy sytuacje, w których gracz X powinien zastosować „Wygraj”. Na zielono oznaczono ruch, który powinno się wykonać, pozostałe symbole już znajdowały się wcześniej. O ile przypadki 1 i 2 są dość oczywiste, to w przypadku 3 można również blokować. Według strategii zwycięstwo jest ważniejsze niż blokowanie przeciwnika. 2. Zablokuj Jeżeli: jest wiersz, kolumna lub przekątna z dwoma symbolami mojego przeciwnika i puste miejsce, Wtedy: zagraj na pustym miejscu (tym samym blokując potencjalne jego zwycięstwo). Dwie przykładowe sytuacje, kiedy powinno się blokować potencjalną wygraną przeciwnika. 3. Zrób rozgałęzienie Jeżeli: są dwa przecinające się wiersze, kolumny lub przekątne z jednym moim symbolem i dwa puste miejsca oraz... Jeżeli: miejsce przecięcia jest puste, Wtedy: przejdź do miejsca przecięcia (tym samym tworząc dwie możliwości wygranej w następnym ruchu). Dwie przykładowe sytuacje, kiedy powinniśmy zrobić rozgałęzienie. Na żółto oznaczone są przecinające się wiersze, kolumny i przekątne. W pierwszym przypadku mamy przecięcie się pierwszej kolumny i drugiego wiersza. W drugim przypadku przecięcie przekątnej z trzecim wierszem. Dzięki wykonaniu takiego ruchu zapewniamy sobie zwycięstwo w grze. 4. Zrób blokujące rozgałęzienie Jeżeli: są dwa przecinające się wiersze, kolumny lub przekątne z jednym symbolem przeciwnika i dwa puste miejsca oraz... Jeżeli: miejsce przecięcia jest puste, Wtedy: Jeżeli: jest puste miejsce, które tworzy dwa symbole w rzędzie dla mnie (tym samym zmuszając mojego przeciwnika do blokowania), Wtedy: przejdź do tego miejsca. W przeciwnym wypadku: przejdź do miejsca przecięcia (tym samym blokując miejsce, gdzie przeciwnik mógłby zrobić rozgałęzienie). Dwa przykłady wykonania blokującego rozgałęzienia. Zauważ, że mamy tu zwykle kilka możliwości ruchu. W pierwszym przypadku mamy możliwość utworzenia dwóch swoich symboli z rzędu przy jednoczesnym blokowaniu, stąd preferujemy taki ruch. W drugim przypadku możemy jedynie zablokować potencjalne rozgałęzienie. 5. Zagraj środek Jeżeli: środek jest pusty, Wtedy: zagraj środek. 6. Zagraj przeciwny narożnik Jeżeli: mój przeciwnik jest w narożniku oraz... Jeżeli: przeciwny narożnik jest pusty, Wtedy: zagraj przeciwny narożnik. 7. Zagraj pusty narożnik Jeżeli: jest pusty narożnik, Wtedy: przejdź do pustego narożnika. 8. Zagraj pusty bok Jeżeli: jest pusty bok, Wtedy: przejdź na pusty bok. Sztuczna inteligencja? Jeśli powyższa strategia brzmi dla Ciebie jak typowe wydawanie rozkazów maszynie, to masz całkowitą rację. Do tego właśnie sprowadza się zaprogramowanie sztucznej inteligencji grającej w kółko i krzyżyk — 8 warunków (w praktyce nieco więcej, gdyż sprawdzamy różne pozycje na planszy, ale jest to wciąż 8 przypadków). Jeśli kiedykolwiek spotkałeś się z jakimś żartem, że jakaś sztuczna inteligencja zapewne sprowadza się do kilku warunków, to cóż, właśnie masz na to idealny przykład. „Sztuczna inteligencja” w praktyce 🙃 (źródło: Taki sposób tworzenia sztucznej inteligencji to, innymi słowy, przeniesienie wiedzy eksperta na program komputerowy. Przy trudniejszych zastosowaniach nie zawsze się to sprawdza, jednak było dość powszechnym podejściem w czasach przed popularyzacją uczenia maszynowego. Jest to podstawa tzw. systemów ekspertowych, czyli systemów, które operując na wiedzy eksperckiej, są w stanie przeprowadzić proces wnioskowania i wytłumaczyć użytkownikowi, dlaczego została podjęta dana decyzja. Swoją drogą, tworząc sztuczną inteligencję do gier, często robimy poziomy trudności. W przypadku tej strategii możemy tego dokonać bardzo prosto — wyrzucając wybrane warianty ruchów. Moja propozycja jest taka, że dla poziomu łatwego możemy zrezygnować z obu rodzajów rozgałęzień, natomiast dla średniozaawansowanego wykorzystujemy tylko jedno z nich. Są to najbardziej zaawansowane i często najmniej oczywiste ruchy, które pozwalają wygrać grę bądź powstrzymać przeciwnika przed zwycięstwem. Wówczas komputerowego gracza będzie można pokonać, a jednocześnie nie będzie on wykonywać ruchów wyglądających losowo. Implementacja w kodzie Tutaj możesz sprawdzić, jak ta strategia sprawdza się w praktyce. Pod planszą pokazane są komentarze opisujące, jaką decyzję w danym momencie podejmuje gracz komputerowy: Tak jak wspomniałem wcześniej, kod źródłowy możesz znaleźć na moim GitHubie. Od razu ostrzegam, że kod jest dość rozwlekły, ponieważ napisanie sprawdzania tych wszystkich warunków wbrew pozorom zajmuje nieco miejsca. Mimo że kodu jest dużo, to jest jednak prosty i sprowadza się do bardzo prostych operacji. Da się go także uprościć, ale napisałem go w bardziej rozwlekły sposób dla lepszego zobrazowania, co się dzieje. Algorytm Minimax Powyższe podejście działa bardzo dobrze, jednak ma podstawowy problem — nie jest uniwersalne. Zostało opracowane po wnikliwej analizie konkretnej gry, toteż nie da się go przenieść na dowolną inną grę, jak warcaby, szachy, czy nawet gomoku, które ma zasady bardzo zbliżone do kółka i krzyżyka. Dlatego też zobaczmy jeszcze jedno podejście, które można zastosować nie tylko w kółku i krzyżyk, ale też w wielu innych grach, czyli algorytm Minimax (zwany też min-max). Zanim przejdziemy do jego omówienia, czas na nieco historii. Autorstwo algorytmu przypisuje się Johnowi von Neumannowi (1928 r., doi: jednak podobne pomysły przedstawiali wcześniej Émile Borel (1921 r., doi: [tłumaczenie z 1953 r.]) i Charles Babbage (1844-1868). Co ciekawe, Charles Babbage opracował podejście podobne do Minimax przy opracowywaniu automatu do gry... w kółko i krzyżyk. Jeszcze mała, poboczna uwaga — algorytm opisuję na bazie późniejszych opracowań, bo niestety oryginalna praca von Neumanna jest napisana po niemiecku, a nie znam na tyle dobrze tego języka, żeby cokolwiek tam zrozumieć. Idea algorytmu Pomysł, jak ma działać algorytm, jest zawarty w jego nazwie. Jest to strategia, gdzie po kolei rozpatrujemy możliwości potoczenia się gry tak, żeby maksymalizować zysk jednego gracza, a przy następnym ruchu minimalizować zysk drugiego gracza. Oczywiście zakłada się, że przeciwnik też będzie chciał wykonać najlepszy możliwy ruch, jaki może. Dlatego też rezultatem algorytmu powinien być taki ruch, który zmusi przeciwnika do wykonania możliwie najgorszego ruchu. Jest to oczywiście mocno uproszczona definicja, a jeśli jesteś bardziej zainteresowany(-a) tematem od strony teoretycznej, to warto poczytać o teorii gier, szczególnie o grach o sumie zerowej i równowadze Nasha. Drzewo stanu gry Aby móc obliczyć, jaki zestaw ruchów jest dla nas najlepszy, a jednocześnie najgorszy dla przeciwnika, musimy wygenerować wszelkie możliwe stany planszy dostępne po każdym z ruchów. W zależności od tego, jaki ruch wykonamy w aktualnej turze, inne ruchy są dostępne dla przeciwnika w kolejnej. Od tego, który ruch wykona przeciwnik, zależy, jakie ruchy my możemy dalej wykonać. Tworzy to strukturę zwaną drzewem stanu gry. Czym są drzewa w informatyce, omawiałem przy okazji sortowania przez wybieranie, i bardzo zachęcam do przeczytania tam o teorii, jeśli spotykasz się z tym pojęciem po raz pierwszy. W naszym drzewie stanu gry, jak wspomniałem wcześniej, każdy węzeł będzie stanem planszy w danym momencie. Potomkami takiego węzła będą kolejne ruchy, jakie mogą zostać wykonane po tym ruchu. Innymi słowy, będziemy musieli wygenerować wszystkie możliwe stany gry, aby algorytm mógł wybrać najlepszy ruch. Jak się możesz domyślać, nie jest to idealne podejście. O ile w przypadku tak prostej gry, jak kółko i krzyżyk, uda się to zrobić w rozsądnym czasie, o tyle w bardziej zaawansowanych grach, jak np. szachy, jest to niewykonalne, stąd stosuje się powszechnie różne heurystyki upraszczające drzewo. Część z nich doczekała się opisania jako oddzielne algorytmy, o czym opowiadam później. Tak wygląda pełne drzewo gry w kółko i krzyżyk dla gracza X. Dla uproszczenia autor tego diagramu połączył ze sobą identyczne gałęzie, stąd struktura na rysunku tak naprawdę nie jest drzewem. Aczkolwiek sens jest zachowany. Do tego drzewo jest dość małe, ponieważ wyeliminowano z niego symetryczne warianty ruchów prowadzące do takich samych sytuacji. (źródło: By Mike like0708 - Own work, CC0, Ogólny zarys algorytmu Minimax opiera się na przeszukiwaniu drzewa w głąb, co oznacza, że jest algorytmem rekurencyjnym. W podejściach tego typu zaczynamy od korzenia drzewa, skąd schodzimy w dół, aby potem wracać do góry. W przypadku Minimax schodzimy w dół do końcowych stanów gry (czyli liści drzewa), albo do maksymalnej głębokości, jaką chcemy sprawdzać. Określamy tam wynik gry z perspektywy naszego, komputerowego gracza. Przyjęło się stosować +∞+\infty dla wygranej i −∞-\infty dla przegranej, jednak nie jest to przymus stosować takie wartości. Ważne tylko, aby wartości były określane w taki sposób, że najlepiej oddadzą aktualny stan planszy. Wracając do góry, zbieramy wartości ze wszystkich potomnych stanów gry i wybieramy minimum bądź maksimum. Maksimum wybieramy dla naszego gracza, minimum dla przeciwnika. Ostatecznie dochodzimy z powrotem do korzenia drzewa i wybieramy ten ruch, dla którego została zwrócona największa wartość. Zobrazowanie działania algorytmu możesz zobaczyć na poniższym schemacie: Prezentacja działania algorytmu Minimax. Na pomarańczowo pokazano, które wartości przechodzą do węzła rodzica, a na zielono najlepszą dostępną ścieżkę. Tym samym naszym kolejnym ruchem będzie utworzenie takiego stanu gry, jaki wskazuje nam zielona krawędź na poziomie pierwszym. Implementacja w kółko i krzyżyk W przypadku gry w kółko i krzyżyk, jak wspomniałem wcześniej, nie musimy martwić się o wydajność algorytmu, więc możemy spokojnie przeprowadzić go w pełni, czyli do końcowego stanu gry. Natomiast w kwestii programisty pozostaje wybór wartości. Możemy podejść do tego, wykorzystując tylko trzy wartości — nieskończoności dla wygranej i przegranej, a zero dla remisu. Można też pomyśleć nad innym ustawianiem wartości, które będzie premiować szybsze wygrane, jednak w praktyce będzie to mieć znaczenie tylko w przypadku, gdy zaczyna komputerowy gracz. Dla ułatwienia ja w swojej implementacji podszedłem do tematu, wykorzystując tylko trzy wartości, ponieważ dla drugiego gracza, który się broni, nie ma to większego znaczenia. Poniżej możesz zobaczyć, jak sprawdza się to w praktyce: Tak jak w poprzednim przypadku, kod źródłowy możesz znaleźć na moim GitHubie. Zwróć uwagę, że kod jest o wiele prostszy i dosłownie jedyne miejsce, gdzie zawiera logikę gry, to sprawdzenie, kto wygrywa. Oczywiście w trudniejszych grach przy generowaniu ruchów trzeba by sprawdzać, czy dany ruch jest możliwy; tu jednak wystarczy jedynie sprawdzenie, czy pole jest puste. Inne podejścia Algorytm Minimax nie jest bez wad. Przede wszystkim nie należy do najszybszych sposobów. Wygenerowanie drzewa ze wszystkimi możliwościami rozgrywki jest kosztowne, szczególnie w grach o bardziej skomplikowanych zasadach czy większych planszach niż kółko i krzyżyk. Z tego też powodu opracowano inne algorytmy bazujące na podobnej idei, jednak wykonujące się szybciej: Najbardziej znaną alternatywą dla Minimax jest algorytm alfa-beta. Jest to na dobrą sprawę poprawiony Minimax w tym sensie, że nie sprawdzamy wszystkich rozgałęzień drzewa stanu gry. Odcinamy te, które są dla nas najmniej korzystne (stąd alternatywna nazwa — algorytm odcięć alfa-beta) i sprawdzamy tylko te najlepsze gałęzie. Istnieją jeszcze inne modyfikacje algorytmu Minimax, takie jak: NegaScout, Negamax, Expectiminimax. Wszystkie wymienione wyżej algorytmy działają na zasadzie wyszukiwania w głąb. Są jednak również algorytmy typu Best-First, gdzie wyszukiwanie odbywa się podobnie do wyszukiwania wszerz, jednak z naciskiem na eksplorację najlepiej zapowiadających się rozgałęzień. Możemy tu wyróżnić takie algorytmy, jak B*, SSS*, Monte-Carlo Tree Search czy Best-First Minimax Search. W przypadku kółka i krzyżyka jest to oczywiście przesada, ale dla bardziej rozbudowanych gier można zastosować techniki głębokiego uczenia, w szczególności sieci neuronowe. W tej dziedzinie zdecydowanie najbardziej znany jest projekt Alpha Zero od Google'a. Wykorzystuje on połączenie głęboko uczących się sieci neuronowych i przeszukiwania Monte-Carlo Tree Search. Jeśli jesteś ciekaw(a), jak w tym podejściu wygląda kółko i krzyżyk, to udało mi się znaleźć działający przykład na GitHubie. Literatura Bottomley H., How many Tic-Tac-Toe (noughts and crosses) games are possible?, (ostatnie odwiedziny: Crowley, K. and Siegler, (1993), Flexible Strategy Use in Young Children's Tic-Tac-Toe. Cognitive Science, 17: 531-561. Minimax: (ostatnie odwiedziny: Monnens, D. (2013). " I commenced an examination of a game called'tit-tat-to'": Charles Babbage and the" First" Computer Game. In DiGRA Conference. Leyton-Brown K., Shoham Y., „Further Solution Concepts for Normal-Form Games” w Essentials of Game Theory: A Concise Multidisciplinary Introduction. Morgan & Claypool, 2008, s. 15-31. Search: (ostatnie odwiedziny: (obrazek na okładce to kolaż obrazków wygenerowanych przez sieć neuronową VQGAN+CLIP po zadaniu jej różnych kombinacji haseł „animals” oraz „tic-tac-toe”; źródło obrazka na froncie: Kółko i krzyżyk to chyba najbardziej znana gra dla dwóch osób, którą znają chyba wszyscy. Jest to gra strategiczna, najczęściej rozgrywana na kartce papieru, choć można zrobić również swoją wersję tej gry. Do gry w kółko i krzyżyk potrzebna jest plansza z dziewięcioma polami oraz długopis lub pionki, z których część ma narysowane koła, a część krzyżyki. Graczy w tej grze jest dwóch, jeden ma kółka, drugi krzyżyki. Grają oni na zmianę ustawiając raz kółko, raz krzyżyk na wybranym polu. Jeśli jednemu z graczy uda się ułożyć trzy swoje znaki w jednym rzędzie (pionowym, poziomym lub po ukosie) wówczas wygrywa. Układając swoje pionki gracz musi pamiętać również o tym, żeby uniemożliwić ustawienie przeciwnikowi. Gdy podczas gry żadnemu z graczy nie uda się ustawić trzech swoich znaków w linii, wówczas jest remis (nikt nie wygrywa). Jest jeszcze wersja gry w kółko i krzyżyk na planszy 15x15 kratek. Jest to plansza do gry w Go. Taka wersja nosi nazwę Piątka lub Kółko i krzyżyk do pięciu. Jak sama nazwa wskazuje, w tej grze zawodnicy muszą tak ustawić swoje pionki, rozrysować je, żeby mieć 5 kółek lub krzyżyków w jednym rzędzie (pion, poziom, ukośnie). Podobna gra nosi nazwę Gomoku, ale w polskiej wersji gra nie może zakończyć się remisem, musi być zwycięzca.

jak wygrać kółko i krzyżyk