Pytania otagowane jako board-games

2
Złożoność n-królowych?
Klasyczne problemy z kolejką pytają, biorąc pod uwagę dodatnią liczbę całkowitą n , czy istnieje tablica Q [ 1 .. n ] liczb całkowitych spełniająca następujące warunki:nnnnnnQ [ 1 .. n ]Q[1..n]Q[1..n] dla wszystkich i1 ≤ Q [ i ] ≤ n1≤Q[i]≤n1\le Q[i] \le njaii dla wszystkich i ≠ jQ …
3
Czy NP jest trudny do prawidłowego grania w drafty międzynarodowe?
Czy następujący problem jest trudny NP? Biorąc pod uwagę konfigurację forum dla międzynarodowych projektów , znajdź jeden legalny ruch.n×nn×nn\times n Odpowiedni problem dla amerykańskich warcabów (inaczej angielskich wersji roboczych) można w prosty sposób rozwiązać w czasie wielomianowym. Istnieją trzy główne różnice między tymi dwiema grami.n×nn×nn\times n Pierwszą i najbardziej znaczącą …
2
Czy szachy mogą symulować uniwersalną maszynę Turinga?
Szukam konkretnej odpowiedzi na pytanie tytułowe. Czy istnieje zbiór zasad, które przekładają dowolny program na konfigurację skończonych elementów na nieskończonej planszy, tak że jeśli czarno-biały gra tylko legalne ruchy, gra kończy się w skończonym czasie, jeśli program się zatrzymuje? Zasady są takie same jak zwykłe szachy minus 50 zasada ruchu, …
1
Złożoność heksów z losową kolejnością tur.
Myślałem o wariancie heksowym , w którym zamiast dwóch graczy wykonujących ruchy na przemian, każda kolej losowo wybrana przez gracza wykonuje ruch. Jak trudno jest określić szanse wygranej każdego gracza? Ten problem występuje oczywiście w PSPACE, ale nie może być trudny do NP, a tym bardziej kompletny w PSPACE. Trudności …
3
Gra Dracula
Kontekst To pytanie jest motywowane grą planszową o nazwie „Dracula”. W tej grze jest jeden wampir i czterech łowców, których celem jest złapanie wampira. Gra toczy się w Europie. Gra wygląda następująco: 1. Łowca umieszcza wszystkich łowców w miastach. W tym samym mieście można umieścić więcej niż jednego myśliwego. 2. …
1
Czy ta gra się kończy?
Rozważ następującą grę karcianą (znaną we Włoszech jako „Cavacamicia”, którą można przetłumaczyć jako „stripshirt”): Dwóch graczy losowo dzieli na dwie talie standardową talię kart. Każdy gracz otrzymuje jedną talię. Gracze naprzemiennie umieszczają na stosie następną kartę ze swojej talii. Jeśli gracz (A) odkłada kartę specjalną, tj. I, II lub III, …
3
Czy istnieje prosta gra o asymetrycznej złożoności?
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch …
3
Implementacja surrealistycznych liczb do gier
Conway ma bardzo ładną konstrukcję o surrealistycznych liczbach. Są to „liczby”, które zawierają zarówno liczby rzeczywiste, jak i liczby porządkowe, są całkowicie uporządkowane i mają wszystkie właściwości pola (z wyjątkiem, że nie tworzą zbioru, ale klasę). Zobacz na przykład ten plik pdf lub Wikipedię w celu wprowadzenia. Można je jeszcze …
3
Zastosowania MCTS / UCT
MCTS / UCT to metoda wyszukiwania drzewa gry, która wykorzystuje algorytm bandyty do wybierania obiecujących węzłów do eksploracji. Gry są rozgrywane losowo, a węzły prowadzące do większej liczby zwycięstw są eksplorowane bardziej intensywnie. Algorytm bandytów utrzymuje równowagę między eksploracją węzłów o wysokich wskaźnikach wygranych a eksploracją nieznanych węzłów (i w …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.