You are not logged in. Please login at www.codechef.com to post your questions!

×

Help about game theory.

7
8

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 ?

asked 04 Nov '18, 09:08

l_returns's gravatar image

5★l_returns
1.6k211
accept rate: 23%

edited 04 Nov '18, 09:16

PS: I got fucked up twice due to these questions in contest.

(04 Nov '18, 09:10) l_returns5★

yeah please anyone!!!? I always hope not to see the pile or any similar word to it in question :(

(04 Nov '18, 11:47) vivek_19982996★

@vivek_1998299 me neither... XD

(04 Nov '18, 16:04) l_returns5★
1

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

(13 Nov '18, 15:58) tieros4★

okay thanks @tieros

(14 Nov '18, 11:22) l_returns5★

link

answered 04 Nov '18, 14:59

ashokshaun's gravatar image

3★ashokshaun
73
accept rate: 33%

edited 04 Nov '18, 15:00

Thanks. I will try to solve these questions.
Still my question is open to all XD

(04 Nov '18, 16:09) l_returns5★

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-

View Content

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. :)
link

answered 04 Nov '18, 16:40

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

Thank you so much :D

(04 Nov '18, 16:47) l_returns5★

thanx maahnn!!

(06 Nov '18, 22:43) vivek_19982996★

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.

link

answered 11 Nov '18, 02:24

akashbhalotia's gravatar image

5★akashbhalotia
875214
accept rate: 10%

Thank you so much.

(13 Nov '18, 07:29) l_returns5★

Please provide a link for the pdf of 'Mathematical Circles' if you have got it.

link

answered 13 Nov '18, 17:32

lakshay_nasa's gravatar image

4★lakshay_nasa
32
accept rate: 0%

link

answered 13 Nov '18, 17:46

yugandhar_t's gravatar image

3★yugandhar_t
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×558
×323
×53
×25

question asked: 04 Nov '18, 09:08

question was seen: 1,801 times

last updated: 14 Nov '18, 11:22