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

Students will need reminders about keep track of state. It is probably better to tell students how to store the previous position of the ball in lecture or on the course forum. The assignment does not require for students to be able to write classes; however, if you cover classes, making pong_ai a class will likely make things more intuitive.
Several hundred rallies generally need to be played in order to reliably determine which AI engine is better. This makes running the tournament in class difficult. We recommend a round-robin tournanment that runs offline, with a demonstration game in class.
It is wise to limit the time that the engine takes to return a move to a few milliseconds. Otherwise running a round-robin tournament becomes untenable, and students may attempt to simply copy the physics engine from the handout code in order to predict where the ball will land.
Many students will have heard of the recent successes with using Reinforcement Learning to learn to automatically play videogames. That's a great topic for class discussions, but it is better to steer away even the strongest CS1 students from trying to implement this strategy. For students who insist on trying to use RL, we said that they can use outside code as long as they do some kind of substantive coding and document what they did.
Most students will try to win by as large a margin as possible against the Chaser (which does not get them far in the in-class tournament), and most students will not modify the handout code to speed up the evaluation of their AI engines. We let the students figure out how to do well in the in-class tournament by themselves, but others might consider giving out helpful hints to the students.
We suggest deciding on rules around tournament qualification ahead of time. Disqualifying entries that produce infinite loops on rare occasions or that often time out likely makes sense.