$4.$ Adversial search heuristics $(20$ Points$)$

Connect$-4$ is a game that is similar to Tic$-$Tac$-$Toe. The object is to get $4$ pieces in

a row $($and to prevent your opponent from doing the same$).$ However, the board

is $6$ squares vertically, by $7$ square horizontally. Also, because the board is

vertical, when a player drops their piece from the top, gravity makes it go all the

way to the bottom of the board $($if there are not other pieces in the column$)$ or$,$

on top of the topmost piece that is already in the column.

When he was $16,$ your dear Prof Joe wrote a Connect$-4$ program. It only did one

ply of search, but it had this heuristic function:

$1.$ If a move gets you $4$ pieces in a row, then take it$,$ else

$2.$ If a move prevents your opponent from putting $4$ pieces in a row, then take

it$,$ else

$3.$ If a move gets you $3$ pieces in a row but with an empty position on either

side, then take it$,$ else

$4.$ If a move prevents your opponent from putting $3$ pieces in a row but with an

empty position on either side, then take it$,$ else

$5.$ If a move gets you $3$ pieces in a row, then take it$,$ else

$6.$ If a move prevents your opponent from putting $4$ pieces in a row, then take

it$,$ else

$7.$ If a move gets you $2$ pieces in a row but with an empty position on either

side, then take it$,$ else

$8.$ If a move prevents your opponent from putting $2$ pieces in a row but with an

empty position on either side, then take it$,$ else

$9.$ If a move gets you $2$ pieces in a row, then take it$,$ else

$10.$ If a move prevents your opponent from putting $2$ pieces in a row, then take

it$,$ else

$11.$ Choose the middle column

Please tell how a program that did more than one ply of search might beat this

program.