Need Help in SG function (Game Theory)

Правка en4, от izlyforever, 2021-03-05 02:23:53

nihal2001 posted a blog for asking the following question:

There are $$$n$$$ stones, two players take turn to choose $$$x$$$ stones, such that $$$1 \leq x \leq n$$$ and $$$x \And n = 0$$$. The one who cannot make choose lose.

Determine who is the winner, The first one or the second?

I proved that If $$$n$$$ belongs to https://oeis.org/A295897, the second player win(can be solved in $$$O(\log n)$$$).

My Question(Multiple piles version of above question):

There are $$$n_1, \cdots, n_m$$$ stones, two players take turn to choose an index $$$i$$$ and $$$x_i$$$ stones, such that $$$1 \leq i \leq m$$$, $$$1 \leq x_i \leq n_i$$$ and $$$x_i \And n_i = 0$$$. The one who cannot make choose lose.

Who will be the winner?

This turn out to compute Sprague-Grundy function for $$$n_1 \cdots, n_m$$$. The first player win if and only if $$$sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$$$

I know how to compute $$$sg(n)$$$ in $$$O(n^2 \log n)$$$, but I can't give it a formula or compute efficiently like $$$O(\log n)$$$ or $$$O(\log^2 n)$$$

Thanks in advance.

Теги #game-theory, #nim-game

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский izlyforever 2021-03-08 18:10:39 16 Tiny change: 'ntu.com/p/FNN39PHqc6/) based o' -> 'ntu.com/p/cgVkGP6zdT/) based o'
en6 Английский izlyforever 2021-03-08 18:06:26 123
en5 Английский izlyforever 2021-03-08 14:49:54 132 Tiny change: 'vance.\n\nUPD: $O(n^{lo' -> 'vance.\n\n**UPD**: $O(n^{lo'
en4 Английский izlyforever 2021-03-05 02:23:53 30 Tiny change: 'player win. \n\nMy Q' -> 'player win(can be solved in $O(\log n)$). \n\nMy Q'
en3 Английский izlyforever 2021-03-05 02:18:22 0 (published)
en2 Английский izlyforever 2021-03-05 02:17:11 2 Tiny change: 'o compute sg(n) in $O(n^2' -> 'o compute $sg(n)$ in $O(n^2' (saved to drafts)
en1 Английский izlyforever 2021-03-05 02:16:30 1135 Initial revision (published)