/ /a3 /a3/tictactoe.pl /a3/tictactoe.xsd /a3/tictactoe.dtd /a3/tictactoe.rng /a3/tictactoe.rnc /a3/tictactoe2html.xsl
This project has several parts parts:
Sample Perl, Lisp and Java implementations of a program which plays tictactoe are provided (see below). They do not do XML. Thus, you may implement tictactoe playing program starting from one of these implementations (perhaps Perl?) and produce a Perl program which plays perl using XML input and output.
You may use any of the useful Perl modules you can find for this assignment. In particular, one of the modules: XML::DOM, XML::SAX or use XML::Parser::Expat will be useful in parsing the XML document.
Note that even if you are using SAX or Expat parsers, still you probably want to use the XML::DOM module to assemble and output the XML document.
The following document gives the format of the XML file
You should only be concerned with transforming one particular TicTacToe position into the next one, by picking the best move. The program should take the XML input either from a named file, specified as a single command-line argument, or from standard input if no arguments are given.
The program should output the XML document in the same format as the sample file. By default, the document should be sent to standard output. If a second argument is specified to the program, it should specify a name of the file to which the output should be sent.
The command
tictactoe.plshould accept the XML input (content similar to samplettt.xml) and send the best move in XML format to standard output
The command
tictactoe.pl samplettt.xmlshould read content from the file samplettt.xml and send the best move in XML format to standard output
The command
tictactoe.pl samplettt.xml bestmove.xmlshould read content from the file samplettt.xml and send the game after the best move has been performed in XML format, to the file bestmove.xml
Produce grammar files describing the XML document format specified above. Similar grammar files were created in class for the example in this directory. Note that you can use tools described in the lecture notes to translate between different grammar formats.
The XSLT program file
tictactoe2html.xslshould implement a transform of a tictactoe position to valid XHTML. The idea is that we will eventually implement a tictactoe Web application playing tictactoe. Thus, you can make it as esthetically pleasing as you wish. If you include images to represent squares, they should be included in the same directory as the rest of the assignment.
A nice article on the XSLT programming language is this D. Novatchev article.
Interesting examples of XSLT programs can be found here.
TicTacToe is a deterministic two-player game with a small game tree, of not more than 9!=362880 distinct leaves. Therefore, its game tree can be searched completely to choose the next move.
You may find this freely available Java implementation from SUN as a reference implementation.
This is a very conventional implementation without the bit-shuffling of the Java code, so that it is illustrative of many Perl patterns. It uses anonymous hashes to simulate structures.
This code was obtained by translating line-by-line the Perl implementation to Common Lisp ( although the Lisp code magically shrunk from 228 lines to 180 lines).
The Perl interpreted code is faster than Lisp interpreted code by a factor of 6 (15 sec. for Lisp vs 2.5 sec for Perl). However, Lisp compiled (without any additional optimizations!) ran the code in 0.1 sec. which is 25 times faster than Perl and 150 times faster than the Lisp interpreted code (50-200 times is typical). We used the free CMU Common Lisp implementation in this experiment.
So, how about compiled Perl vs. compiles Lisp? Big disappointment: the Perl compiler failed to compile to binary code (it only produced byte code). We tried to produce code with:
[marek@garnet Advanced]$ perlcc -S ./tictactoe.pl ./tictactoe.c: In function `perl_init_aaaa': ./tictactoe.c:6307: warning: this decimal constant is unsigned only in ISO C90under Fedore Core 3.
We note that Perl (like Emacs, Java and several other systems) compiles to "byte code" before executing, even in the interpreted mode. So does CMU lisp.