properties of a certain game

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 509
Joined: Tue Apr 24, 2012 1:10 am UTC

properties of a certain game

Postby >-) » Thu May 25, 2017 6:38 am UTC

this is a two player, zero-sum game.
the state is 2 vectors and two scalars (one vector and scalar per player).
call the vectors x and y and the scalars p and q respectively. x and y have some fixed dimension k. (and if it makes things easier, feel free to let k be infinite)
player 1 wins if p > 0 and q <= 0, and gets 1 reward (player 2 gets -1) and vice versa.

intuitively the idea is that x_0 (and also y_0) is the amount of resources that player 1 and 2 have
player 1 can spend x_0 to decrease q, since it wants to get q to 0
player 1 can also spend x_0 to increase x_1, which increases x_0 each time step -- or it can increase x_2, which increases x_1, which increases x_0
(the same goes for player 2)

formally:
at time t = 0, x_0(t) = y_0(t) = 1 and x_i(t) = y_i(t) = 0 for 1 <= i <= k
also at t = 0: p(t) = q(t) = 1

an action by either player is a positive k-dimensional vector.
call the action vectors a and b for player 1 and 2 respectively
then
x_i(t+1) = x_i(t) + x_{i+1}(t) + a_i(t) for 1 <= i <= k if we say x_{k+1} = 0
x_0(t+1) = x_0(t) + x_1(t) - sum(a(t))
p(t+1) = p(t) + min(a_0(t)-b_0(t), 0)
and all three of these rules hold similarly for player 2 (y). the only major difference is
q(t+1) = q(t) + min(b_0(t)-a_0(t), 0) . notice the swap of b and a
finally there is the constraint that a_i(t) >= 0 and sum(a(t)) < x_0(t) and the same goes for player 2

player 1 and 2 make their moves a(t) and b(t) simultaneously

so the question is what a winning strategy is, or if not that, if there is a nash equilibrium. actually i'd be happy with figuring out a merely "good" strategy
so far all i've determined is that at a_0(0) should be less than 1 --
otherwise player 2 if sets b_0(0) to be a small epsilon, player 2 will not immediately lose, while player 1 is stuck with x = 0 and cannot make any nonzero moves from then onwards

mfb
Posts: 943
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: properties of a certain game

Postby mfb » Mon May 29, 2017 4:06 pm UTC

An interesting game. Research first, conclusions towards the end.

The game is perfectly symmetric, I'll consider most things from the view of player 1 but of course it applies to both players. I'll call x_0 "attacking potential", x_1 "income" and a_0 "attacking strength".

Player 1 can force a win if p+x_0 > q + y_0 + 1 at any time.

sum(a_i(0))=1 loses against [b_i(0)=0 for all i and b_0(1)=1], which loses against a_0(0)=1, which loses against b_0(0)=epsilon. I guess the latter is useful independent of the rest. Assuming the opponent follows the epsilon-approach for attacking strength, the initial attacking power is not sufficient to win. I'll ignore the epsilon investments now, as I don't think they play a role in the following rounds.

You have to invest in x_1 or higher. Investing in x_1 at t=0 reduces your attacking potential at t=1, gets neutral at t=2 and only starts increasing it at t=3. The first serious attack can occur here, attacking before does't give any advantage. It also means you don't have to save anything at t=0, and at t=1 you don't invest anything.

Whatever you put in x_2 doesn't matter at t=3, so we get a first strategy to consider: "Attack at t=3", with a(0)=(0, 1, 0, ...), then do nothing, then use a(3)=(2,0,0,..).

The attack will be successful if y(3)<1. We can express this as y(3)=1+b_1(0)-b_3(0)-b_4(0)-... - sum(b(2)).
From t=1 on you know your opponent's strategy, so player 2 can stop investing. I'll drop all the (0) for readability. They survive the first attack if 0 < b_1-b_3-b_4 - ...
The game is not over yet, however. At t=4 player 1 will have an attacking potential of 1 again, so we get the additional constraint 1 < 2b_1+2b_2-b_4-b_5-... where 0,2,2,0 are coefficients of a row of Pascal's triangle minus 1 (the -1 is the investment).
t=5 leads to the inequality 2<3b_1+5b_2+3b_3 - b_5-b_6-... where 0,3,5,3,0 are the next row.

It is easy to find vectors that satisfy all these inequalities, and once you have an income of more than 1 you are done. Some investment in b_1 and b_2 does the job. I don't find nice general conditions (none of the inequalities is redundant). Something we can conclude from this, however: "Attack at t=3" loses against more balanced approaches, probably with decreasing b_i.

How to beat a more balanced approach? For every such approach we can make inequalities again. You win if you invest a little bit more into higher classes, but you lose if you do that too extreme.
If we ignore investments after t=0, this is a (multidimensional) rock-paper-scissors system. You lose against strategies that are much more aggressive, you win against strategies that are just a bit more aggressive, you lose against strategies that are a bit more long-term oriented, and you win against strategies that are much more long-term oriented. The Nash equilibrium is some randomized mixture of these strategies.

I wouldn't expect investments after t=0 to change this. If the difference in strategy between the players is too large, the game is basically done. If the strategy is extremely similar, you just have another rock-paper-scissors system. If there are just small differences, you get biased rock-paper-scissors, where the margins are smaller for one side.

How exactly to distribute the investments? No idea. Something like (eps,0.3+eps,0.4-2eps,0.15,0.075,...) is probably not a bad approach for an approach that survives "attack at t=3" and has a nice long-term growth.

>-)
Posts: 509
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: properties of a certain game

Postby >-) » Tue May 30, 2017 4:37 am UTC

thanks for the observations. i actually played a few test games against a friend yesterday and did notice the things you mention (though that may just be confirmation bias). hastily written code attached.

Spoiler:
in a spoiler tag, because the forum wouldn't let me attach any files for some reason

Code: Select all

#!/usr/bin/env python2
import os
import traceback

def clear():
    for i in range(100):
        os.system('clear')
           
class Session:
    def __init__(self, k = 4, d = 3):
        self.k = k
        self.d = d
        self.x = [0.0 for i in range(k)]
        self.y = [0.0 for i in range(k)]
        self.x[0] = 1.0
        self.y[0] = 1.0
        self.p = 1.0
        self.q = 1.0
        self.go()

    def step(self, a, b):
        assert sum(a) <= self.x[0]
        assert sum(b) <= self.y[0]
        assert min(a) >= 0
        assert min(b) >= 0

        for i in range(self.k-1):
            self.x[i] += self.x[i+1]
            self.y[i] += self.y[i+1]
        for i in range(1, self.k):
            self.x[i] += a[i]
            self.y[i] += b[i]
           
        self.x[0] -= sum(a)
        self.y[0] -= sum(b)

        self.p += min(0, a[0] - b[0])
        self.q += min(0, b[0] - a[0])

        self.p = round(self.p, self.d)
        self.q = round(self.q, self.d)

        for i in range(self.k):
            self.x[i] = round(self.x[i], 1)
            self.y[i] = round(self.y[i], 1)

    def check(self):
        if self.p < 0:
            print 'player 2 wins'
            return True
        if self.q < 0:
            print 'player 1 wins'
            return True
        return False

    def go(self):
        while not self.check():
            raw_input("press to continue")
            clear()
            a = self.getturn('player 1\n')
            b = self.getturn('player 2\n')
            self.display()
            try:
                self.step(a,b)
                print 'a : '+str(a)
                print 'b : '+str(b)
                self.display()
            except Exception as e:
                print 'illegal move made'
                traceback.print_exc()
               
    def getturn(self, msg):
        while 1:
            try:
                self.display()
                s = raw_input(msg)
                nums = []
                for item in s.split(',')[:self.k]:
                    if item.strip() == 'e':
                        nums.append(0.1**self.d)
                    else:
                        nums.append(round(float(item), self.d))
                clear()
                return nums
            except:
                print 'parsing error -- try again'

    def display(self):
        print 'x : '+str(self.x)
        print 'y : '+str(self.y)
        print 'p : %f' % self.p
        print 'q : %f' % self.q

if __name__ == '__main__':
    S = Session()


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests