1)The game of backgammon can be posed as the following decision problem: given a

Question

1)The game of backgammon can be posed as the following decision problem: given a legal positioning of checkers and information about which side is to move, determine whether that side can win. Is this decision problem tractable (i.e. a problem that can be solved in polynomial time)? Explain.

2)State the decision version for the partition problem (given n positive integers, determine whether it is possible to partition them into two disjoint sets with the same sum) and outline a polynomial-time algorithm that verifies whether or not a proposed solution solves the problem.

Explanation / Answer

1)

Backgammon is a nondeterministic game with chance. In nondeterministic games, chance is introduced by dice or cardshuffling. In case of Backgamm on the chance is introduces by dice. Playing backgammon is simple: there are two players with 15 pieces each. The final goal is to move all pieces off the board. The rules are: Dice roll determines number of moves, players move in opposite directions, pieces cannot put on a point occupied
by 2 or more of opponent’s pieces, single piece can be “hit” if it is put on the same line a piece of the opponent and hit piece must start a new route.

Playing Algorithm
Initialize the board with all 15 white pieces and 15 black pieces
While no player has wont yet
Next_moves <- {}
    for each possible move from the current state S,
      determines the next state, S1,of the board
    next_moves <- next_moves U S1
    for each state from the next_moves
    list do
    merit_factor <- DetMeritFactor(S1)
MaximMerit <- maxim(Merit)
Perform the move for the state with MaximMerit merit_factor and obtain
NewPosition
    If NewPosition is winning state
    Break
    Read the opposite player’s move and modify the board
end

2)

DetMeritFactor(S1)
If the state S1 is a winning state
    Return the maximum default value for merit_factor
For each posible moves of the opposite player from the
state S1
    Calculate the merit factor Mi for each state resulted
from these moves
Select the state with the minimum merit factor Mmin,
considering that the opposite will made the most defavorable move
Return Mmin
End

Other results are positive, proving that some games can be played optimally in polynomial time. In some cases, particularly with one-player puzzles, the computationally tractable games are still interesting for humans to play.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.