It doesn't really have to look ahead which is good because unlike chess there ien't a definite outcome to each move made. All it really has to look at is previous playcalls and predicted strength of possible playcalls in a given situation.
Head coach had calculated success for plays in given situations based on previous preformance. They also calculated tendencies for coaches playcalling in various situations. If head coach could do that I don't see it as being impossible in madden.
From there writing an algorythem that makes a playcall based on those successes along with opponent tendencies and coach tendencies along with a random factor to keep the user guessing isn't that tough.
Off the top of my head for offensive playcalling I would use something along the lines of:
Take the top 10 most successful plays, number them one through 10 and weight each of them in order opposit of success. Give play 1 10 points, 9 for play 2 etc.
Then look at the set playcalling for the coach in a given situation. Maybe for 3rd and short, QB run 10%, FB run 10%, HB inside run 40%, PA pass 20%, HB outside run 10%, HB counter 10%. Now go through the 10 plays and multiply each of the 10 plays by the percentage.
Now add up all those numbers, pick a random number between 0 and the sum and whatever range the number is in, pick that play.
Defensively it takes a little more reatcion to the opponent. As far as Double teaming, pressing certain players, playing off of certain players, rolling a safety over to help on a receiver, etc you just have to be able to analyze the ratings and determine mismatches. This ia a simple matter of looking at the ratings and if there is a certain amount of difference making the predetermined adjustment. Also, you could have them after every few plays look back at those matchups and if a player has had some level of success maybe adjust the requirements to make the adjustments.
As far as moving extra players into the box, it is a matter of assesing their own run defense and your HBs ratings. Maybe also figure in the user's playcall tendencies in the situation and the user's success so far that game running the ball.
All of those are kinda yes or no things and easy to write a code for. As far as playcalling it gets a little tougher. First when it comes to calling a formation, just match the personel that the user uses. As far as the play call head coach was able to determine success of a play against a certain type of offensive play. Ok, knowing user tendencies and the strength of each of your plays against each of those possibilities an algorythem can be determined. Off the top of my head it should go something like:
For user's top tendency order the top 10 plays in the same way as with offensive plays. Then multiply each by the percent chance of that tendency.
Next go to the second highest tendency and do the same thing. Do this for all possible play call types within the user tendencies and then add up all the results.
Next go to the CPU coaches tendencies and adjust each of the possible playcalls in the same way descibes in the offensive playcall description. From there you can determine a random number and pick the play as described before.