We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If we're at state i, aka the ith brick is at the top, we can write this as a function DP(i), that will return the max value that we can obtain for i, assuming it's our go.
At brick i, you have 3 different choices, you can either:
Take one brick, take two bricks, or take three bricks. Each of these leads us to a new state (sub problem):
DP(i) -> DP(i-1) //if we take one
DP(i) -> DP(i-2) //if we take two
DP(i) -> DP(i-3) //if we take three
So ideally we want to simply take the MAX of these possible moves. We want to make optimal decisions, so we'll just simply take the MAX of the three choices because the one that returns the highest value is going to be the choice we want!
DP(i) = MAX{ DP(i-1), DP(i-2), DP(i-3)}
A problem with this is that these next states, aren't out turns! After we've made our move it's the oppositions turn! We're trying to maximise our score, and in effect we're also trying to minimize their score!
So we're trying to maximize our score, while simultanously minimizing their score.
Let say we removed the first block: aka the next state was DP(i-1), we want to minimize this state and this would look like this:
DP(i-1) = MIN{ DP(i-2), DP(i-3), DP(i-4)}
Here we're evaluation every single move the opponent can make, and we're saying, take the minimum, we want the opponents score to be minimized!
We can then simply combine these to form this large recurrence relation:
DP(i)=MAX{//we take 1 brick - next state for the oppo is DP(i-1)MIN{DP(i-2),//they take 1DP(i-3),//they take 2 blocksDP(i-4)//they take 3 blocks},//we take 2 bricks - next state for the oppo is DP(i-2)MIN{DP(i-3),//they take 1DP(i-4),//they take 2 blocksDP(i-5)//they take 3 blocks},//we take 3 bricks - next state for the oppo is DP(i-3)MIN{DP(i-3),//they take 1DP(i-4),//they take 2 blocksDP(i-5)//they take 3 blocks}}
Bricks Game
You are viewing a single comment's thread. Return to all comments →
This might help anyone stuck!
If we're at state i, aka the ith brick is at the top, we can write this as a function DP(i), that will return the max value that we can obtain for i, assuming it's our go.
At brick i, you have 3 different choices, you can either: Take one brick, take two bricks, or take three bricks. Each of these leads us to a new state (sub problem):
DP(i) -> DP(i-1) //if we take one DP(i) -> DP(i-2) //if we take two DP(i) -> DP(i-3) //if we take three
So ideally we want to simply take the MAX of these possible moves. We want to make optimal decisions, so we'll just simply take the MAX of the three choices because the one that returns the highest value is going to be the choice we want!
DP(i) = MAX{ DP(i-1), DP(i-2), DP(i-3)}
A problem with this is that these next states, aren't out turns! After we've made our move it's the oppositions turn! We're trying to maximise our score, and in effect we're also trying to minimize their score!
So we're trying to maximize our score, while simultanously minimizing their score.
Let say we removed the first block: aka the next state was DP(i-1), we want to minimize this state and this would look like this:
DP(i-1) = MIN{ DP(i-2), DP(i-3), DP(i-4)}
Here we're evaluation every single move the opponent can make, and we're saying, take the minimum, we want the opponents score to be minimized!
We can then simply combine these to form this large recurrence relation: