SCG-Teach: A Family of Games for Large Problem Solving Courses

by Ahmed Abdelmeged and Karl Lieberherr

Abstract: We have used SCG-Teach over the last 5 years in various variations with increasing success. The goal of SCG-Teach is to engage the students in a systematic scientific discourse to defend their own claims and refute the claims of others. The focus is on creating productive interaction, teaching from student-to-student and collaborative/competitive problem solving. The instructor has the usual task of defining precisely the problem solving domains and the additional task of explaining SCG-Teach once. The learning of SCG-Teach is amortized over numerous problem solving domains that are covered in one course.

Our approach is useful for large classes because the students tend to teach each other under the supervision of the teaching staff.

Synopsis

The instructor defines a problem solving domain by giving a notation for expressing instances, classes of instances, and solutions and the instructor provides a predicate that decides whether a solution is a valid solution for a given instance. Since an instance can have more than one solution, the instructor also provides a function that associates a quality for each solution. Since the notation for expressing classes of instances can be intensional, the instructor also provides a predicate that decides whether an instance belongs to a particular class of instances.

The students start with a limited knowledge about their ability to find good solutions for a given instance or class of instances. Namely, the quality of the best solution they can find for a particular instance or class of instances. In an SCG game, they are encouraged to put out objectively refutable claims about their ability to solve a certain instance or class of instances. Other game participants are also encouraged to examine claims put out by others and either agree, strengthen, or refute them.

As the game proceeds, students get targeted feedback, from other students, about: 1. misconceptions they have about their ability to solve instances. 2. their relative ability to solve instances. Instructors can intervene to strengthen claims that are not at the optimal level or to flag situations when true claims have been refuted and false claims have been defended because student misconceptions are hidden behind those situations.

SCG-Teach in a Nutshell

The students ask questions of two forms: (1) Alice proposes claim C out of an instructor-defined set of claims and asks Bob: do you agree, strengthen or refute my claim? Bob must make one of those 3 decisions. (2) During the scientific discourse created by the claim protocol, the following kinds of questions are posed and answered. In the next step of the protocol (2.1) what is the instance that you provide? (2.2) what is the solution that you compute out of a provided instance? The students also ask indirectly more difficult questions: (2.3) What is the defense or refutation strategy or even (2.4) Why does the defense or refutation strategy always work (a proof).

Bob evaluates the claim C made by student Alice. If Bob believes claim C is (1) true, Bob agrees and has to defend C against Alice. (2) true, but not optimal, Bob strengthens and has to defend the strengthened claim against Alice. (3) false, Bob refutes C against Alice.

The objective is to successfully defend your own claims and to successfully refute or strengthen or agree with the claims of others.

During the scientific discourse, Alice and Bob exchange instances and solutions that are fed to a predicate p together with information in the claim. If p is true after the exchange, Alice wins and otherwise Bob. This is what we mean by an objectively refutable claim.

SCG Teach with Piazza

We are using SCG-Teach with Piazza in the Spring 2012 Algorithms course at CCIS, Northeastern University Algorithms and Data (CS 4800).

Piazza for Algorithm Students . This is a low-tech use of SCG-Teach because enforcing the game rules is done by the students collectively. (We also use a high-tech version of SCG-Teach where the students write avatars that play the game on their behalf. In that scenario the game rules are strictly enforced by software called SCG Court.) The low-tech use with Piazza is very successful. We had competitions about: "what is the worst-case input to Gale-Shapley" and "what is the worst CNF where any pair of clauses is satisfiable" and "what is the highest safe rung for a ladder with n rungs and k jars to break". In all three cases, the students collaboratively/competitively found the correct solutions.

The students learn about SCG-Teach from Piazza Interface for Algorithmic Problem_Solving. As communication language for instances and solutions we use JSON so that the students can easily check the work of their peer using programs.

The features of Piazza that go well with SCG-Teach: All the scientific discourse about one claim is at one place. Because all students see the discourse they can check that the game rules are followed. We observed that students enjoy doing this policing because they help other students find flaws in their reasoning.

We have developed some patterns for writing interesting domain descriptions, called playgrounds. (1) Use playgrounds where claims can be strengthened wrt. quality. Seed the playground with a suboptimal claim and let the students take it from there. You will be surprised. (2) Occasionally define a playground with a small omission and give the impression that a set of claims are all true. Then let the students find the omission which let's them refute all claims that were believed to be true. This encourages them to think critically. (3) Some playgrounds are direct in that the topic to be covered appears directly in the claims. Other playgrounds are indirect in that the topic to be covered is used in the solution approach.

It has happened on Piazza that students have released too much information through the scientific discourse. Therefore we introduced a new rule: If the scientific discourse reveals to much information about the homework solution the scientific discourse is only completed AFTER the due date for the homework. This way students get partial information which makes them think: "those girls have a solution of quality 0.8 while I only have a solution of quality 0.7. What is their clever technique?" They become motivated to learn what their peers already know.

Feedback

The following feedback is given from student to student:

[Misunderstanding: true but cannot defend] Alice proposes a true claim but she cannot defend it: signals a misunderstanding of Alice that is made concrete by the protocol. Bob clarifies the misunderstanding by refuting the true claim.

[Misunderstanding: false not true] Alice proposes a false claim which she thought to be true: signals a misunderstanding. Bob clarifies the misunderstanding by refuting the false claim.

[Misunderstanding: not optimal] Alice proposes a true claim but one which is not optimal. Bob defends a stronger version of Alice' claim which helps Alice to clarify her misunderstanding.

The workload for the teacher is greatly reduced because the students clarify several misunderstandings without teacher involvement.

Learning

What do the students learn from the above feedback? They get a more precise perception of their ability, both absolute and relative, to find solutions.

They learn to generalize from their experience with specific instances to other instances. If they have to invent an algorithm the generalization is more difficult than if they have to invent just data for a given algorithm.

For more information, see the SCG Home Page: http://www.ccs.neu.edu/home/lieber/evergreen/specker/scg-home.html