# DSA HW3 1. minimax 2. alpha-beta pruning 3. memorization 4. heuristic method --- ## minimax ---- ### game tree - A node represents a state of the game - An edge represents the player's feasible strategy and state transition - Root node is the initial state of the game - Leaf nodes are the states at the end of the game - Each player moves optimally ---- sample: 3 DQ H3 H2 HA D6 D3 ----  ---- For each player, when he wins, let the score be the remaining points of the loser when he loses, let the score be the remaining points of himself Then the goal becomes to maximize this score ---- In addition, you can find that it is a zero-sum game Therefore, we can use the minimax algorithm ----  --- ## alpha-beta pruning ----  ----  ----  ---- Max layers generate lower bound to the subtree Min layers generate upper bound to the subtree Each node receives two additional parameters: $alpha,beta$, which represent the lower bound and upper bound of the answer respectively The answer is useful only if it is between $alpha\sim beta$ ---- Max layers update $alpha$ after computing a branch Min layers update $beta$ after computing a branch if $beta\le alpha$, it means that the node is impossible to return a useful answer So there is no need to calculate remaining branches. --- ## memorization ---- Consider this case: 4 SA S2 D3 D4 D5 D6 H7 H8 The possible order of playing cards are: 1. SA->pass->S2->pass->D3... 2. S2->pass->SA->pass->D3... 3. D3->D5->D4->D6... 4. D4->D5->D3->D6... ... ---- We can find that the state of 1,2 are the same: - both of them have the same remaining cards - the previous card is also the same(D3) Thus, they will lead to the same result So we should only calculate once ---- Store the answer after computing each state (use data structures such as unordered_map) When entering a node, if the state of the node has been computed before, return the answer directly In this way we can avoid repeating computing same states ---- ### How to express a state 1. the remaining cards of both players 2. whose turn it is 3. the previous card 4. $alpha,beta$ ---- #### remaining cards: Each of them has $n$ cards initially Remaining cards are a subset of initial cards Thus, we can use $n$ bits to represent it $i{\text -}th$ bit means whether he still has the $i{\text -}th$ card ---- We need $2n$ bits to store remaining cards of both players $1$ bit to represent the current player $2+4$ bits to represent the suit and the number of previous card respectively $9$ bits for both $alpha$ and $beta$ Thus we can use $59$ bits to express a state: store all of them in an unsigned long long --- ## heuristic method ---- For a game, there is often some intuitive strategies If you can make sure that it is an optimal strategy, you may greatly reduce the states to be searched Besides, choose the search order properly may let alpha-beta pruning algorithm cut more branches Think and test it by yourself !