A Tournament for Pong AI Engines

Michael Guerzhoy (University of Toronto and St. Michael's Hospital, guerzhoy@cs.toronto.edu)

Overview

Pong is a game enjoyed by people in general, by the CS1 community in particular, and by pigeons. In this open-ended assignment, students write an AI engine for Pong from scratch. Students can have their AI engines play against each other, and participate in a class-wide tournament. To design good AI engines, students have to read, understand, and modify the game engine code. The assignment is accessible to any CS1 student, but leaves room for a lot of exploration and creativity — we have had success engaging both excellent students who had little difficulty in CS1 and students who found CS1 challenging.

We provide an implementation of Pong in Python using PyGame, and the students need only to submit a file with a function that interacts with the implementation (we don't ask for a class since those are not covered when the assignment is given). The function takes in the coordinates of the ball and the paddles, and returns "up" or "down". It is left up to the students to have the function store the state of the game in order to be able to compute the velocity and direction of the ball and to implement complex strategies using that information.

Students are encouraged to explore the game engine. Having done that, students can design a mechanism for aiming their shots and modify the code in order to speed up the AI engine optimization process.

In our experience of using the assignment in classes of 300 students and of running university-wide tournaments, numerous students implemented engines that beat human players, but no student developed a close-to-optimal engine.

The students' first task is to beat the Chaser engine. The Chaser simply follows the y-coordinate of the ball. The code for the Chaser engine is given to the students:

  def pong_ai(paddle_frect, other_paddle_frect, ball_frect, table_size):
    if paddle_frect.pos[1] + paddle_frect.size[1]/2 < ball_frect.pos[1] + ball_frect.size[1]/2:
       return "down"
    else:
       return  "up"

The simplest way for the students to test their code is to change just one line in the handout code:


  # To have the Chaser play against your AI engine, 
  # store your code in student_ai.py, import student_ai, 
  # and set paddles[1].move_getter to student_ai.pong_ai

  import chaser_ai
  import student_ai
  paddles[0].move_getter = chaser_ai.pong_ai
  paddles[1].move_getter = directions_from_input 
                                 

We use the assignment as a bonus assignment. Students get a small amount of bonus points towards their course mark for beating the Chaser and qualifying for the tournament, and we award 4%, 3%, 2%, and 1% for first place, second place, third place, and honourable mention, respectively. Having the best AI engines play against each other in class is always a lot of fun!
Two (imperfect) student Pong AI engines playing against each other.

Meta Information

Summary

Write an AI engine for the game of Pong. Explore the handout code which contains the game physics. Design and implement a Pong AI engine that beats an AI that simply chases the ball's y-coordinate. Improve the AI engine further and enter it into a class-wide tournament.

Topics

AI heuristics, game physics, keeping track of state when performing computation

Audience

Mid-to-late CS1. Students need to be comfortable with basic programming constructs. The handout code uses classes, but we have used the assignment without explicitly teaching classes. Students need to remember high school trigonomerty and geometry to understand the game physics and to design good heuristics for their AI engines.

Difficulty

Beating the Chaser is easy (students usually take a couple of hours to install PyGame, run the handout code, and come up with a heuristic that works). Interested students spend more than 10 hours on figuring out the game physics and optimizing their AI engines.

Strengths
  • Students build an AI engine that they can play against and lose to, from scratch. Students have fun participating in the in-class tournament and watching the their colleagues' engines play against each other live in class.
  • The assignment is both challenging and accessible to all students, making it a great bonus assignment for CS1 classes with a lot of beginners and a lot of students who are looking for a challenge.
  • The assignment is both open-ended and auto-gradable: performance of the students' engines against the baseline AI that chases the ball's y-coordinate is measureable automatically, and the tournament is runnable automatically as well. Code for running the tournament and for auto-grading submissions is available upon request.
  • Students get to see and modify a full implementation of a computer game — but students don't have to understand the implementation to get started, and they don't have to understand the implementation fully to do a very good job.
  • Students enjoy discovering an elegant one-liner solution to the problem of predicting where the ball will hit the left/right side of the table after bouncing off the top/bottom sides multiple times.
Weaknesses
  • The assignment depends on PyGame. Installing PyGame is a slight pain.
  • This is not a traditional CS1 assignment. It makes more sense as a lab assignment or a bonus assignment.
Variants
  • We chose to ask the students for a function rather than for a class, mostly because we give the assignment before classes are covered. If you cover classes early, it makes sense to ask for a class.

Example Handouts

A sample handout is available here.

Supporting the assignment

Students find functions that store state unintuitive. Time should be devoted to providing examples, even if finite-state machines were covered.

We spend about 20 minutes explaining the physics engine of the game in class.

Lessons learned