Microsoft Word - NLP_Challange-Track_Sprint2_FS19_RC SPRINT 2 This Sprint deals with the following mathatical topics:  Probabilit  Markov-Chains  Hidden Markov Model (HMM) Challenge "Tug of war" It...

The assignment is related to math/statistic/stochastic. It should be done in a jupyter notebook. And it should be commented out because I have to explain the code later in a oral examination. The PDF with all the details is attached.It is allowed to use libraries.


Microsoft Word - NLP_Challange-Track_Sprint2_FS19_RC SPRINT 2 This Sprint deals with the following mathatical topics:  Probabilit  Markov-Chains  Hidden Markov Model (HMM) Challenge "Tug of war" It will investigate the game "Electronic rope pulling" and develop a game strategy in which the probability of winning is as large as possible! The game Two opponents compete against each other with their rope pull teams. The opponents take turns drawing a card. A distinction is made between "strength cards S" and "action cards A". In the standard version there are three different strength cards ("+1", "+2" and "+4"), which increases the strength of the own team accordingly. The action cards have the two cards "Oel" (sets the strength of the opposing team to 0 and "Spinat" (increases the strength of your own team infinite and leads directly to victory!). The currently active player decides between the Strength and Action cards and draws a (face down) card from the corresponding stack. This card is played immediately and the strengths of the teams adjusted. The difference in the strengths of the two teams then causes a shift to the left / right according to the difference in strength. The player who drew the opposing team to the bottom of the field has won! A computer player pulls the cards «by chance». There are three (inner) strategy states for the computer player:  «D» (defensive): It will most likely drawn a strength card,  «C» (chaotic): With equal probability you choose between Strength and Action card  «O» (offensive): It is more likely that an action card will be drawn. The computer player keeps changing between the (inner) strategy states. This change is to be understood as a stochastic process, whereby the change from one inner state to the next with so-called transition probabilities can be described (Markov chain). We have three types of ready-made computer players. These are the types "Classic", "Random" and "Aggressive" with the following transition probabilities: All player types are at the beginning in the inner strategy state «D». Which card type is finally drawn is given by the following probabilities (emission probabilities with a Hidden Markov Model): ? = 0.8 0.2 0.5 0.5 0.3 0.7 Where the rows correspond to the strategy states "D", "C" and "O" and the columns to the cards "S" and "A". Furthermore the probabilities for the different strength cards are given by (?(? = "+1") = 0.6, ?(? = "+2") = 0.3 und ?(? = "+4") = 0.1) and for the different action cards (?(? = "Oel") = 0.9 and ?(? = "Spinat") = 0.1)! Sub-Challenge 1 (game strategy / Markov-chains): Examine / compare the different player types based on the given Markov chains. Among other things, determine the limit probabilities of the strategy states for each player type. For the Sub-Challenge 1 we still consider the player type IV («Constant» with the additional two inner strategy states «S» (strength card) and «A» (action card)): ? = (1,0,0,0,0) ? = ⎝ ⎜ ⎛ 0.5 0.2 0.1 0.1 0.1 0.3 0.2 0.3 0.1 0.1 0.1 0.2 0.3 0.3 0.1 0 0 0 1 0 0 0 0 0 1 ⎠ ⎟ ⎞ ? = ⎝ ⎜ ⎛ 0.8 0.2 0.5 0.5 0.3 0.7 1 0 0 1 ⎠ ⎟ ⎞ The columns and rows of the matrix TIV correspond to the inner strategy states «D», «C», «O», «S», «A». The columns of the matrix EIV correspond to the cards «S» and «A». For this absorbing Markov chain, determine the absorption probabilities and the mean path lengths to the absorbing states (mean rules!). Sub-Challenge 2 (Gameplay): Implement the game "Computer against Computer" in Python and let the different types of players compete against each other! Sub-Challenge 3 (Monte-Carlo Simulation): Use simulation (at least 10,000 games) to determine the winning odds as the different types of players compete against each other. In each case determine the average playing time (number of moves) and which winning sequences (with regard to card type and / or card) most often leads to victory! Sub-Challenge 4 (Hidden Markov Model): Examine the different types of players with the help of the "forward" - (with which probability a certain observation can be made) and the "Viterbi" algorithm (which sequence of internal states is the most probable for a particular observation). Sub-Challenge 5 ( best strategy): According to the most successful winning sequences (Sub-Challenge 3), determine the transition probabilities for the best possible game strategy (Baum-Welch algorithm, maximum likelihood method).