Whenever the contest starts with a question including “Alice” and “Bob” with a easy game theory, people get AC’s.
I get lot of penalities (6-9) also I take about hours to get logic and get frustrated by looking at ranklist and criticize codechef in my mind about keeping them(Alice and Bob XD) in question (which I know I shouldn’t do).
How can I improve in solving such problems ?
Obviously, many people will say “practice”.
But anything else that you would like to add ?
And where can I practice these questions ?
I mean can you provide some links where I can find such questions ?
Did you read my editorial on game theory in September long (TABGAME)? It discussed a general way to tackle these problems in the first note on game theory and Chef Vijju’s corner point 2.
Since my below part is based on that, let me copy it for those who didnt-
Click to view
"First player is starting from (x,y). A cell is marked W if a player starting from that cell (or who has his turn when stone is on that cell) wins. A cell is marked L if he loses if he has to make a move from that cell.
Now, assume we already found out which of previous cells (or cells which we might visit in our moves) are W or L. If all the cells to which I can move to (from current cell) are W, then that means that my opponent will win (because a cell is W if player who gets to make a turn when stone is on that cell wins). This means, I will lose no matter what, as irrespective of how I move, there is a winning strategy possible for my opponent. What if all are not W, i.e. I can move to a cell labelled L? It means my opponent cannot win no matter what if stone is at that cell when he gets his turn. Now, obviously, I will move the stone to that L labelled cell to win as I move optimally."
At the end of the day, I’d want you to remember the part of W and L which we discussed. You can apply that to any such game. If starting position determines winner, and you know the state of positions which you can visit from current cell, you can derive for this cell as well. A player wins only if he can force his opponent to lose by making sure opponent plays only at “losing” or L cells. Hopefully this will clear the numerous doubts among div2 guys on what “playing optimally” is
Now, onto technical stuff.
Harder Game-Theory problems are hard, and require knowledge of sprungy number. A case in point is Pishty and Birthday from last year’s long.
For cakewalk and easy level game theory, its all about observations.
By observations, I mean, either you discover the optimal strategy followed by them, or you reduce the game into some standard game (like game of NIM) and apply the knowledge we have of these standard games.
Hence, little knowledge of grundy numbers and such games always helps.
In the question in point, for Alice and Bob (XD), we can go this way.Now since player who cannot make a move loses, and Alice and Bob play optimally, i.e. they dont want to lose, and Charlie (the guy who swaps table) is biased to make Alice win, can we define optimal play?
If the sum of stones in piles are unequal, then Charlie can swap Alice to table with larger piles. Now, Alice removes only 1 stone per turn, and wins, no matter what Bob does.
If sums are equal, and the piles Alice and Bob have are “same”. By “same” I mean, they are such that Bob can always mirror or copy the move done by Alice. In this case, table swap has no effect and Bob wins.
If this is not so, then there will be a time when Bob wont be able to copy Alice’s move. Hence, the piles will have unequal sums. We know in this case Alice wins because of Charlie.
Similar methods to solve practice questions will sharpen your intuition for it.
There is a book called ‘Mathematical Circles.’ It’s a pretty famous book. I used to practice Game Theory problems from it and it helped improve my logic for Game Theory a lot. I’m sure some online pdf of it too might be available.
Check Game Theory class notes by Thomas S. Ferguson. I was reading one of them several months ago, fun and lighter than math textbooks. Since then trying to improve myself on DP, hoping to return to game theory soon again
