Soldier$/$Pawn $($S$)$ can move only one straight step ahead. Only if opponent coins are available, it can move in diagonally one step forward to attack the opponent coin. Every move adds a penalty of $3$ and every successful attack gains a reward of $5.$ Horses$/$Knight $($H$)$ can move either forward$/$backward in L $-$ shaped strides covering exactly $3$ tiles. Every move adds a penalty of $5$ and every successful attack gains a reward of $4$ a$.$ Construct game tree with utility value shown, up to level $3$ or one round per player followed by one more turn for $1$st player. Assume that player with Black colored pieces moves first. Use the below function for static evaluation calculation. Board value $=$ Utility of MAX player $-$ Utility of MIN player Utility of a plaver $=$ Reward $-$ Penalty b$.$ Apply minimax algorithm in the complete game tree constructed under part a$)$ to find the strategy of game if both were to play optimally. Show each step in the algorithm. $$