Skip to content

Game Theory

Author: Theo830

Nim's game

Problem

2 παίκτες πάιζουν ένα παιχνίδι. Έχεις n στοίβες που πέτρες που η κάθε μια έχει a[i] πέτρες. Ο κάθε παίκτης στη σειρά του μπορεί να αφαιρέσει κάποιες πέτρες (> 0) από κάποια στοίβη (μια στοίβη). Χάνει αυτός που δεν μπορεί να κάνει κάποια κίνηση (δηλαδή έχουν αφαιρεθεί όλες οι πέτρες). Να βρείτε ποιος νικάει και την στρατηγική νίκης.

Solution

Αν το XOR όλων των \(a_i = 0\) κερδίζει ο δεύτερος αλλιώς κερδίζει ο πρώτος (άρα το \(\bigoplus_{i=1}^n a_i=0\) είναι losing position (1) ). Η απόδειξη είναι ότι όταν είσαι κάπου που το xor όλων των \(a_i\) είναι 0 τότε αφαιρόντας οποιοδήποτε αριθμό πετρών, το xor δεν θα είναι πλέον 0.

  1. Για να αποδείξουμε στο game theory ότι μια στρατηγική είναι σωστή, συχνά χρησιμοποιούμε backwards induction. Δηλαδή αποδεικνύουμε ότι όταν είμαστε σε losing position μπορούμε να πάμε μόνο σε winning position, και όταν είμαστε σε winning position, υπάρχει τουλάχιστο ένας τρόπος να πάμε σε losing position.

Επίσης θέλουμε να δείξουμε ότι όποτε το xor δεν είναι 0, μπορούμε με μια κίνηση να κάνουμε το xor να είναι 0. Έστω ότι το xor = \(d\) (\(d > 0\)). Μπορούμε να επιλέξουμε κάποιο \(i\) και να αφαιρέσω αρκετές πέτρες έτσι ώστε να μείνουν \(a_i \oplus d\) πέτρες. Όμως επίσης έχουμε τον περιορισμό \(a_i \oplus d < a_i\) (αλλιώς ο αριθμός πετρών που πρέπει να αφαιρέσουμε είναι μικρότερος ή ίσος του μηδέν, το οποίο δεν γίνεται σύμφωνα με το πρόβλημα). Για να ισχύει η συνθήκη, μπορούμε να επιλέξουμε το \(i\) με το μέγιστο \(a_i\).

Έστω το \(d\) να έχει το πιο μεγάλο bit του να είναι το \(2^k\). Υπάρχει τουλάχιστο ένα \(i\) έτσι ώστε το \(a_i\) να έχει το bit \(2^k\) on, αλλιώς το \(d\) δεν θα έιχε το bit (Σύμφωνα με τον τρόπο υπολογισμού του XOR). Άρα επιλέγοντας πάντα τον πιο μεγάλο αριθμό, μπορούμε να αφαιρέσουμε \(a_i - \bigoplus_{j=1}^n a_j\) πέτρες, για να αναγκάσουμε τον αντίπαλο να πάει σε losing position.

Grundy Theory

Βασικά τούτος ο "τύπος" μπορεί να σου πει ποιος νικάει οποιοδήποτε παιχνίδι με 2 παίκτες που δεν έχει ισοπαλία. Μετατρέπει κάθε state του παιχνιδιού σε ένα Nim's value.

Έστω \(S(x)\) το Nim's value όταν είμαι στο state \(x\). Αν \(S(x) = 0\) εν Losing state αλλιώς εν winning (όπως ακριβώς στο Nim). O τύπος είναι \(S(x) = mex\{S(y)\}\) (1) για κάθε state \(y\) που μπορώ να πάω απευθείας από το \(x\).

  1. MEX = Minimum Exclusive Value. Δηλαδή, ο πιο μικρός μη αρνητικός αριθμός που δεν έιναι σε ένα set. Π.χ. \(mex\{1,2,4,5,6\} = 3\)

Αν το \(x\) όταν σπάζει πάει σε πάνω από ένα state ταυτόχρονα πχ \(y_1,y_2,\ldots, y_k\):

\[S(x) = mex\{S(y_1) \oplus S(y_2) \oplus \ldots \oplus S(y_k)\}\]

Note

Σε πολλά (αρκετά δύσκολα) προβλήματα το S(x) μπορεί να εν περιοδικό.

Resources

Problems