COMMENTS BY KARL IN CAPITAL Proposition Game Reflection/Critique cs4800 Lieberherr Sarah Laplante TERMINOLOGY: proposition game -> QUANTIFIER GAME The proposition game is an social protocol for proposals and challenges to help develop the most efficient or correct solution to an algorithmic problem. It is similar to formal algorithmic playgrounds like tunedit.org which allows well defined problems to be competed over by teams or individuals. (Often for cash prizes.) The protocol game used in cs4800 was a modified version of this type of game, which emphasized collaboration and agreement among players instead of bloodthirsty competition in order to better meet the goals of an undergraduate class. BESIDES tunedit.org: TOPCODER FOLDIT EXTERNA In a more traditional proposition game algorithms are submitted to an impartial system and ranked by speed, accuracy, or some other objective metric. Our proposition game was played on Piazza, a forum designed for classroom Q/A. Algorithms were ranked by a one of few different metrics (speed, accuracy of results, asymptotic efficiency, number of machine instructions) which were self reported by students. Instead of all students submitting their best implementation to a central system each pair would make a claim about efficiency, and other students would ask them to defend their claim by solving a presented algorithmic problem, or would offer a stronger claim. Generally the game worked well. The competition motivated students to design better algorithms, and the posted solutions gave interesting clues. Sometimes another student's running time would suggest an algorithmic implementation, and in a few cases (Gail Shapely, MIN-HSR) it was possible to reverse engineer an algorithm after seeing its output. A few rounds went really well, with many incremental improvements to the algorithm and a build-up of friendly competition. SEE: http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp12/feedback/christopher-souvey/response CHRISTOPHER TRIES TO CHARACTERIZE WHAT WORKED WELL. Unfortunately there were also problems. The back and fourth of the protocol worked best with only three or four groups arguing over one claim. Too many groups in one place made things confusing, and most of the claims posted didn't evoke any discussion at all simply because there were so many of them. The other general problem was a lack of rigor in following the protocol. My partner and I posted incorrectly formatted claims more than half the time, with the only consequence that we had to go back and fix things later. (And sometimes no consequences when no one noticed or commented.) We were hardly an isolated case. People also tended not to follow through once an exchange was started. This was partially because we were often confused about how to follow through on the many different types of responses. But also, again, because there weren't tangible consequences for not doing so. Usually only the few best algorithms would receive and respond to a challenge, while other groups would slide by with slightly weaker proposals, all agreeing with each other and diplomatically avoiding eye contact. SEE MY HIERARCHICAL PLAYGROUND PROPOSAL HERE: http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp12/feedback/christopher-souvey/response As we played it the proposition game's basic deficiencies come from its differences from a 'real' playground. Algorithmic challenges which are played by researchers over a long period of time have a fundamentally different quality then those played weekly by undergraduates. The fact that each game only lasted a week (less actually, since people usually didn't start until three or four days in) made it difficult to maintain a healthy back and fourth. Proposals made on the last day of the game often went unanswered once assignments were submitted. Generally there was a lack of rigor around the rules of the game, with a lot of groups only halfheartedly putting in the bare minimum for posts. IT IS NOT CLEAR TO ME HOW STRICTLY THE RULES SHOULD BE ENFORCED. FOR THE WINNING CLAIMS IT IS ESSENTIAL TO CHECK THAT THE RULES WERE FOLLOWED CORRECTLY. STRICT ENFORCEMENT: STUDENTS BECOME DISCOURAGED WITH A ZERO TOLERENCE APPROACH. WEAK ENFORCEMENT: SOME STUDENTS BECOME CREATIVE AND EVEN IMPROVE THE CLAIM LANGUAGE. SEE CHRISTOPHER AND GRIFFIN FOR WORST CASE OF GALE-SHAPLEY. It was unclear how the scoring system for the game worked, or if it really existed at all, and how it effected grades. Partially this was because the scoring was zero-sum, which doesn't lend itself well to grading anyway. A more formal system would help maintain more rigor and care in people's posted proposals. Even if it can't be integrated into the normal grades for the class some sort of scoreboard would be helpful. It would let people know how they're playing and motivate them to take care with their postings. It might also encourage people to post earlier, respond more promptly, and not leave dangling exchanges if they know they will lose points. Unfortunately adding something like this would require much stricter enforcement of the rules, which were really more like suggestions this term, and it would be discouraging to groups who lose a proposition over a misplaced word. Also it would take a fair amount of attention from the professor or a TA to keep a scoreboard updated, and it would require an unambiguous metric (like number of machine instructions) to ensure the rankings were fair. But using a metric like that would reduce flexibility of language choice, which was a big plus this term. Generally a scoreboard system is most motivating for the top few students in the class, who start competing against each other for first, but they don't really need the extra push. Students at the bottom of the list don't see any reason to try much harder if they're so far behind, and may even be discouraged by the implicit judgment. HAVING SMALL PLAYGROUNDS (USING HIERARCHY) WOULD ENCOURAGE WEAKER STUDENTS TO PARTICIPATE MORE BECAUSE THEY ARE IN A SMALL PLAYGROUND? AN INTERESTING TRADEOFF BETWEEN USING A SCOREBORAD AND AN INFORMAL APPROACH. Another tack would be to embrace the differences from a formal playground, and make the game more casual. One of my favorite parts of the game this term was trying to glean implementation hints from other group's postings. Although we were ostensibly barred from divulging our implementations until after a game had closed reverse-engineering was sometimes possible and always interesting. There were a few founds where my team couldn't develop a good algorithm, and it was always disheartening to write some sad brute-force code knowing there were more elegant methods and we couldn't figure them out. If successful teams were allowed to talk about their algorithms partway through the game (Maybe if team A finishes an agreement protocol with team B then A can ask B high-level questions about their implementation?) we probably would have been able to write better code. Of course this would lead to some teams just piggybacking off the clues given by other teams instead of figuring the problem out from scratch, but I think it would be a good tradeoff since even implementing a well designed algorithm you've been given is more educational than writing some bad code to scrape through on an assignment. This would also allow different teams to merge their good design choices. I DID NOT WANT TO BLOCK HIGH-LEVEL DISCUSSION OF ALGORITHMS. IT SEEMS IMPORTANT TO ENCOURAGE IT IN CLASS. Making the system less formal would be most helpful to struggling students, while letting stronger students serve as mentors or collaborate with each other. It would allow a more interesting exchange of information within the short time given for each challenge, and would leave a record of students work. Usually we went over the 'behind-the-scenes' implementation details in class. But it would have been helpful to have a more tangible record of the steps people went through to develop their algorithms. The competition elements of the proposition game are fun, but emphasizing them too strongly in a classroom setting just leads to unnecessary red tape which gets in the way of the educational process. YES, LET'S ADD TO EACH PLAYGROUND A FORUM WHERE HIGH-LEVEL IDEAS ARE EXCHANGED. AS YOU SAY, THERE MIGHT BE PIGGYBACKING BUT MOST STUDENTS WANT TO PUT IN THE EFFORT. I FOUNG YOUR NOTES THAT YOU ATTACHED http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp12/feedback/sarah-laplante/finalCritNotes.txt ALSO VERY HELPFUL.