Help: A two player game..

• Previous message: Nicholas King: "Re: (Unsure where to post)"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 9 Dec 2004 17:57:51 -0800

Hi everyone, I've been trying to solve the foll problem, but am not
sure how to proceed.

Two players play a game as follows : There are 'n' states. A coin is
initially in some state. A move consists of a player moving the coin
to some other or possibly the same state. There is a "cost" involved
though. This is given as a matrix, cost of moving from state 'i' to
state 'j'. (i to i might also have a nonzero cost). The game consists
of 'm' moves, and the player who incurs minimum total cost is the
winner. The problem is to find, given the matrix, m, n, the best
difference between himself and his oponent the first player can force.
(the lesser the better ofcourse).

One way of doing, is ofcourse, noting that if 'pos' is the current
position, and nmoves is the number of moves remaining,
bestdiff[pos][nmoves]=min(over j)
(cost[pos][j]-bestdiff[j][nmoves-1]). However, this method takes
O(m*n^2) time. Is there a faster algorithm? Moreover, it appears that
if nmoves is large enough, the best move is fixed. But how large is
large enough is dependent on the matrix. For example, if the matrix is
:
4 2
3 k
then, the player starting at state 2, in order to get minimum
difference, has to move to state 1 if nmoves<k and remain in state 2
if nmoves>=k (this can be proved).

Is there any other way of looking at it, or is there any pattern which
would be forced to appear?
Thanks in advance for any help,
Bhaskara Aditya

• Previous message: Nicholas King: "Re: (Unsure where to post)"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]