Junior94's blog

By Junior94, 10 years ago, In English

I'm trying to understand some concepts of game theory. So far I've understood how the game of nim works, at least the most basic form: as long as the current game has value > 0 the current player can change at least one of the piles such that the next turn will be played with value = 0. If the current game has value = 0 there are only 2 possibilities: Either the game is over and the player lost or he may pick a pile but by doing so in every case will yield value > 0 for the next player. I understood it by reading this Topcoder article. It clearly explains how to choose a pile when value > 0 and change it to value = 0 and that keeping value = 0 for two turns is impossible.

I am now trying to understand how the minimum excluded cardinal is equivalent to a nim value. How will always choosing the minimum value not appearing in the set always yield the correct result? How can the bigger values be discarded and not accounted for if those values can still be reached? Is there any intuitive way to know why this works?

UPD: Got the answer from here. The Topcoder article above also has the answer as kingofnumbers already said but I found it a little bit difficult to understand it with just that (it makes sense when you already understand it of course). Just in case someone eventually faces the same problem I left the link that helped me the most.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Open the same article that you linked it there's already an answer to your question.

press Crtl+F then copy this to search box.

Why is the pile of Nim equivalent to the subgame if its size is equal to the grundy number of that subgame?

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I can tell simple meaning of that as I see it.

When you calculate winning/losing positions on the game on acyclic graph, you follow the next rule: iff there is at least one move to the losing position, mark current position as winning. If you denote losing as 0 and winning as 1, formula will be like: win[x] = mex(win[y1], win[y2], ...) > 0. For original Grundy you just remove > 0.

Now what Grundy function does: it holds more information than just winning/losing. It classifies winning positions by "how this game behaves in direct sum with the other game".

For example for games on simple, about straight-line graphs it will be almost the same as winning/losing function (where Grundy values are relatively small), because simple game cannot totally change other game being added to.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit: Deleted, I was over thinking it, thank you, your answer helped me understand more about this subject.