Thursday, 10 November 2011
WORK HARD AND DO YOUR BEST
Lessons in Life – universal
Computer Science – A-level/undergraduate level
There can be few better exhortations to students than this. Working hard and doing one’s best will always produce the finest possible results, either in the classroom or on the playing field. After any exam or sporting challenge there is no failure if one can say afterwards “I did my best”. (England footballers please take note.)
A game of noughts and crosses is underway on the blackboard. If this has been done by a student then it should have been rubbed off immediately (see post #9 re Wilson and Kelling’s broken windows theory). But if this is actually part of the lesson then a gold star should be awarded as noughts and crosses is a great introduction to many mathematical and computer science concepts from combinations and symmetry to artificial intelligence.
A first question to pose to the class would be how many games of noughts and crosses are possible (the game tree size)? A naive answer would be 9! = 362,880 (assuming X always goes first). However, many games will be over before all the squares are filled, and many more are simply rotations and reflections of others (in effect there are not nine, but only three starting places: corner, centre and edge). Taking these into account gives an answer of 26,830.
Devising an algorithm to produce perfect play is also a favourite challenge, exploring ideas such as backwards reasoning and recursion. These can then be applied to other, more complex games such as Connect 4 and draughts, through to unsolved games such as Reversi, chess and Go (with its game tree complexity of 10360).
However, if this is an attempt to teach the strategy of perfect play then one must hope that the teacher has picked a very poorly-played game to illustrate what not to do. Assuming that X’s first move was in the corner (always the best start: of the then 73 possible games, assuming perfect play on X’s part, 71 result in victory and two in a draw), then O has immediately blundered by playing the far edge instead of the centre (where his/her only hope of a draw can come from), resulting in what should be certain victory for X. X could then force a win by playing the centre, but has him/herself blundered by playing middle bottom. O can now snatch a draw from the jaws of defeat by playing centre or top right, leaving X to harp on about how the Wags should have been allowed to stay in the team hotel.
Despites its pedagogical pedigree, noughts and crosses quickly becomes futile when both players can easily force a draw. This was well-illustrated in WarGames, when the military supercomputer, equating the game to global thermonuclear war, evaluated all possible outcomes and remarked, “Strange game. The only winning move is not to play.” Failing that, just work hard and do your best.
8/10 An inspired choice of teaching material.