Transcript CS2001 PowerPoint

Artificial Intelligence
In Sports
A Study Upon American Football
By Gregory S. Nilsen
Task
To create a team of intelligent
defensive football players. This team
should be able to:
 Respond to a programmed offense
 Use various formations
 Function in an environment that is
accessible and deterministic
 Complete the project in 10 weeks
Approach
Two Player Model
Minimax Search With Alpha-Beta
Pruning Strategy

Search through all possible moves to find
the best on for each player.
LISP

Utilize recursive prowress of the language.
Approach
(continued)
Create Structures

Field




Players







Array
Set of Players
Ball
Team
Location On Field
Position On Team (i.e.. “running back”)
Blocked?
Open?
Ball?
Ball


Location
Height
Approach
(continued)
Create Movement Functions For Ball
and Players
Define Offense
Plays
 Throwing/Catching
 Handoffs

Tested Offense
Both Passing and Running Plays
Working
 No Unrealistic Moves

Approach
(continued)
Define Defense



Formations
Property Checks
Minimax




Static Function
Copy Functions
Move Generation Functions
Value Manipulation Functions


For Passing During Recursion
Result Interpretation Functions
Main Function
Testing
-------------------------------|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X
|
|
X
|
|
|
|
X
|
|
X
X
X
X
|
|
X X X X
|
| O
O O B O O O
O |
|
O
|
|
|
|
O
|
|
|
|
O
|
|
|
|
|
|
|
|
|
-------------------------------Initial field position
Search Depth of One
|
X
|
X
|
|
OX
X
|
OX
X O
O |
X O
O OX
|
O O X
O
|
O
|
B
B
|
(A)
(B)
Search Depth of Three
|
X
|
X
|
|
XO
|
XXO
X XO
XO |
X O
O O
|
O O
O
|
O
|
B
B
|
(C)
(D)
X
O
XO
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
How Well Did It Work?
Speed



Algorithm Is Slow
Runs at a Reasonable Speed With a Depth of
One (5-10 min.)
More Extensive Depths Cause the Program To
Run For Extended Periods
Effectiveness



The Algorithm Ran Effectively Against Running
Plays
Against Passing Plays It Was Typically
Effective, But Occasional Lapses Occurred
Some Moves Were Appropriate to the
Algorithm, But Unrealistic In Actual
Application
What Would Be Changed?
If the project were to be
extended:
Static Evaluation
Function
Coverage
Representation
Efficiency
AI Offense
Full Game Play, Not
Just One Play At A
Time
Expand to Handle
More Game Details
If the project were to be
done again:
Defensive Algorithm



Efficiency
More Realistic Move
Choices
Handle Game Details
Representation


Graphical
Field
AI Offense
Full Game