Tworzenie deterministycznego program do odegrania n d Kółko i krzyżyk z pozostałych zawodników.
Twój program powinien działać, gdy n
(szerokość) id
(numer wymiaru) znajdują się w następujących zakresach:
n∈[3,∞)∩ℕ ie a natural number greater than 2
d∈[2,∞)∩ℕ ie a natural number greater than 1
n = 3; d = 2
(3 2 tj. 3 na 3):
[][][]
[][][]
[][][]
n = 3; d = 3
(3 3 tj. 3 na 3 na 3):
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
n = 6; d = 2
(6 2 tj. 6 na 6):
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
I tak dalej.
Wejście:
Dane wejściowe będą na STDIN. Pierwszy wiersz danych wejściowych będzie składał się z dwóch liczb n
oraz d
w formien,d
.
Następnie pojawi się linia składająca się ze współrzędnych określających wykonane ruchy. Współrzędne są wymienione w następującej postaci: 1,1;2,2;3,3
. Lewy górny róg jest punktem początkowym (0,0 dla 2D). W ogólnym przypadku ta lista będzie wyglądać tak, jakby 1,2,...,1,4;4,0,...,6,0;...
pierwsza liczba reprezentowała lewą prawą stronę, drugą górę-dół-ność, trzecią do trzeciego wymiaru itp. Zauważ, że pierwsza współrzędna to X
pierwsza kolej, druga jest O
pierwsza kolej, ....
Jeśli będzie to pierwszy ruch, na wejściu pojawi się liczba, po której nastąpi 1 pusty wiersz.
Aby zachować spójność, dane wejściowe zawsze kończą się nową linią. Przykładowe dane wejściowe (\ n to nowa linia):
10,10\n0,0,0,0,0,0,0,0,0,0;0,2,3,4,5,6,7,8,9,0;0,1,2,3,4,5,6,7,8,9\n
Do pierwszego ruchu:
10,10\n\n
gdzie \n
jest znak nowej linii.
Wynik:
Wyjdź ruch, który chcesz wykonać, w tym samym formacie, co dane wejściowe (lista oddzielona przecinkami). Nieprawidłowy ruch (tj. Taki, który został już wykonany) spowoduje przegraną w grze.
Uwaga: Możesz użyć generatora liczb losowych, o ile wysyłasz go taką wartością, aby każdy przebieg był identyczny w tych samych warunkach. Innymi słowy, program musi być deterministyczny.
Uwaga: dozwolone są tylko prawidłowe ruchy.
Zwycięskie gry (jeśli grałeś wystarczająco dużo wielowymiarowych kółko i krzyżyk, to tak samo.)
Aby wygrać, jeden gracz musi mieć wszystkie sąsiadujące pola wzdłuż linii. Oznacza to, że gracz musi mieć n
ruchy na linii, aby zostać zwycięzcą.
Sąsiadujący:
- każda płytka jest punktem; na przykład (0,0,0,0,0) to punkt w
d=5
- sąsiadujące płytki są płytkami, więc oba są punktami na tej samej jednostce d-cube. Innymi słowy, odległość Czebyszewa między płytkami wynosi 1.
- innymi słowy, jeśli punkt
p
przylega do punktuq
, wówczas każda współrzędna wp
odpowiedniej współrzędnej inq
różni się od niej nie więcej niż o jeden. Dodatkowo przynajmniej para współrzędnych różni się dokładnie o jeden.
Linie:
- Linie są definiowane przez wektory i kafelki. Linia to każda płytka dotknięta równaniem:
p0 + t
<
some vector with the same number of coordinates as p0>
Symulacja i warunki wygranej:
Podaj w swojej odpowiedzi, czy jest gotowy do oceny. Oznacza to, że wyraźnie wskaż, czy twoja odpowiedź została wykonana.
Jeśli twoja odpowiedź jest oznaczona jako zrobiona, nie będzie oceniana aż do co najmniej 24 godzin po ostatniej edycji kodu.
Programy muszą działać w trybie offline. Jeśli okaże się, że program oszukuje, automatycznie otrzyma wynik
-1
i nie będzie dalej oceniany. (Jak ktokolwiek skończyłby z oszustwem w swoich programach?)Jeśli twój program generuje nieprawidłowe dane wyjściowe, jest to od razu liczone jako strata dla gry
Jeśli program nie generuje wyników po 1 minucie, jest to od razu liczone jako strata dla gry. W razie potrzeby zoptymalizuj szybkość. Nie chcę czekać godzinę, aby przetestować inny program.
Każdy program będzie uruchamiany z innymi programami dwa razy dla każdego
n
z zakresu[3,6]
i każdegod
z zakresu[2,5]
, razX
i raz jakoO
. To jest jedna runda.Dla każdej gry, którą wygrywa program, osiąga
+3
swój wynik. Jeśli program remisuje (1 wygrana i 1 przegrana w jednej rundzie lub remisy w obu grach), to dostaje+1
. Jeśli program się zgubił, to dostaje+0
(tj. Bez zmian).Program z najwyższym wynikiem wygrywa. W przypadku remisu wygrywa program z najmniejszą liczbą przegranych gier (spośród remisujących zawodników).
Uwaga: W zależności od liczby odpowiedzi może być potrzebna pomoc w przeprowadzeniu testów.
Powodzenia! I niech symulacje przebiegną zawsze na twoją korzyść!
źródło
Odpowiedzi:
Python 3
To jest po prostu losowy ai. Losowo wybiera ruch spośród ruchów, które są nadal dostępne.
źródło
Python 2.7
To jest praca w toku, którą dostarczam, aby dać szkielet / inspirację innym użytkownikom. Działa, wymieniając każdą możliwą zwycięską linię, a następnie stosując heurystykę, aby zdobyć tę linię zgodnie z jej wartością. Obecnie heurystyka jest pusta (super tajne działania). Dodałem także obsługę błędów wygranych i kolizji.
Uwagi na temat problemu
Ile jest wygranych linii? Rozważ przypadek 1-wymiarowy; są 2 wierzchołki, 1 krawędź i 1 linia. W 2 wymiarach mamy 4 wierzchołki połączone 2 liniami i 4 krawędzie połączone 2 * n liniami. W 3 wymiarach mamy 8 wierzchołków połączonych 4 liniami, 12 krawędzi połączonych 6 * n liniami i 6 ścian połączonych
3*n^2
liniami.Zasadniczo nazwijmy wierzchołek 0-aspektem, krawędź 1-aspektem itp. Następnie
N(i)
oznaczmy liczbę i-aspektów,d
liczbę wymiarów in
długość boku. Zatem liczba wygrywających linii wynosi0.5*sum(N(i)*n^i,i=0..d-1)
.Według Wikipedii,
N(i)=2^(d-i)*d!/(i!*(n-1)!)
więc końcowa formuła to:sum(2^(d-i-1) n^i d! / (i! * (n-i)!),i=0..d-1)
który wolfram | alpha nie bardzo lubi. To robi się bardzo duże dość szybko, więc nie oczekuję, że mój program będzie miał wykonalne środowisko uruchomieniowe dla d> 8.
Niektóre wyniki (przepraszam za formatowanie:
I / O
W tej chwili dane wejściowe należy wprowadzić jako:
tictactoe.py <ret> n,d <ret> move;move <ret>
- zanotuj wiele wierszy, a nie końcowy;
.Dane wyjściowe wyglądają
(x_1,x_2,x_3...)
na przykład:tictactoe.py <ret> 6,5 <ret> <ret>
=>0, 0, 0, 0, 0
tictactoe.py <ret> 6,5 <ret> 0,0,0,0,0;0,0,0,0,5 <ret>
=>0, 0, 0, 5, 0
Edycja: dla I / O, dodano logikę. Wierzę, że jest to teraz gotowe do oznaczenia
Uwaga: ten komentarz był początkowo symbolem zastępczym, który usunąłem i usunąłem.
źródło
Python 2
Większość kodu jest dokładnie taka sama jak losowa sztuczna inteligencja Quincunx . Zamiast losowo wybierać ruch, wybiera pierwszy dostępny ruch leksykograficznie (tj. (0,0, ... 0), następnie (0,0, ... 1), a następnie (0,0, ... 2) itp.).
Jest to dość banalna strategia, ale prawie zawsze bije się losowo.
źródło