Each player's goal is to get as many points as possible. A word is chosen as the starting point. For example, it might be "incomprehensibility". The first player gets to choose whether to take the first letter, i, and receive 5 points, or the last letter, y, and receive 7. Suppose he chooses the i. The second player is now confronted with the remainder of the word, "ncomprehensibility" and can again choose to take either the first letter, n, for 6 points or the last letter y, for 7. This continues until all the letters are taken. The player with the higher point total wins, but we are not going to be satisfied with just winning: the optimal player's goal is to get as high a score as possible.
In order to see why this is true, first play the game with a partner using the string "the" and convince yourselves that its value is -4, meaning that the first player will lose by 4 points in optimal play. Likewise convince yourself that the value of "hen" is 2.
This notion of value lets us figure out how to play optimally. The two choices you have when confronted with "then" are
Another point to notice in the above example is that the larger of the two net values, 10, is the value of the full string, "then". This will always be the case, because the value of a string is defined in terms of optimal play, and the optimal player will choose the better option. You can use this to calculate the values of strings in a tree-recursive manner. In the above example, you would calculate the value of the string "then" in terms of the values of the strings "hen" and "the".
Re-read the previous paragraph and make sure you understand it. It is the most important part of this whole assignment.
string-refcan tell you what character is in a particular position within the string. The positions are numbered from 0, just like with
vector-ref. For example,
(string-ref "then" 0)would evaluate to the character t, and
(string-ref "then" 3)would evaluate to the character n. These two characters are written in Scheme as
#\nrespectively. Characters are a new kind of data, which you have not previously seen. All you will need to do with them is pass them into the following
char-valueprocedure, which embodies the table of point values:
(define char-value (lambda (char) (let ((c (char-downcase char))) ; in case it is upper case (cond ((equal? c #\e) 1) ((equal? c #\t) 2) ((equal? c #\a) 3) ((equal? c #\o) 4) ((equal? c #\i) 5) ((equal? c #\n) 6) (else 7)))))
The user interface will also make use of
which tells how many characters are in a string. For example,
(string-length "then") evaluates to 4.
(substring-value "then" 4 0) (substring-value "then" 3 0) (substring-value "then" 3 1)The first means to find the value of 4 characters starting at position 0, the second means 3 characters starting at position 0, and the third would be 3 characters starting at position 1. In other words, these are inquiring about our old friends "then", "the", and "hen", respectively, and so the three expressions above should evaluate to 10, -4, and 2, respectively.
Of course, if you want to have a procedure,
that returns the value of a whole string, it is very easy to write in
substring-value. (You might find this
convenient for your testing.)
cmas an abbreviation for "choose move", that we pass the current string to. If we evaluate
(cm "then"), we would like to get back the symbol
last, indicating that the computer chooses to take the last character. We could define
cmin terms of a more general procedure,
choose-move-from-substring, which limits its attention to only some of the string, in the same manner as
substring-value. Here are the definitions:
(define cm ; cm is short for "choose move" (lambda (s) (choose-move-from-substring s (string-length s) 0))) (define choose-move-from-substring (lambda (s len low) (if (= len 1) 'either ;; We let f be the net value if we choose the first letter, ;; and l be the net value if we choose the last letter. (let ((f (- (char-value (string-ref s low)) (substring-value s (- len 1) (+ low 1)))) (l (- (char-value (string-ref s (+ low (- len 1)))) (substring-value s (- len 1) low)))) (cond ((> f l) 'first) ((> l f) 'last) (else 'either))))))
substring-value, and test that it gives correct values. Then you should be able to play the game against the computer, using the crude user interface,
cm. You should notice that with longer strings, the program gets rather slow. For example, "incomprehensibility" will probably strain your patience. You can try progressively longer strings in order to get some sense of how rapidly the time grows; you'll do more precise timings later.
Now use either memoization or dynamic programming to make
substring-value more efficient, test that it still works,
and again, see how time grows as you move to longer strings.
cmtakes with strings of varying lengths, and graph your results, using each of the two versions of
substring-value. You should do the timings using the timing procedure in the file ~mc27/public/time.scm; this is the one you used in the MCS-177 lab concerning perfect numbers.
You should use semi-log, log-log and regular graph paper found in http://www.gac.edu/~wolfe/courses/graph-paper/. Recall that
Try to experimentally predict, by looking at your graphs, the running times of your two versions. Solve for b in anb or abn by looking at the graphs. Predict how long a word can you solve in a day's time with the two programs.
If you are able to analytically deduce the running time of your program (Theta-notation), by analyzing the program rather than the data, that's a bonus.
lencharacters of the string
sstarting at position
low, you could evaluate
(substring s low (+ low len))For example,
(substring "then" 1 (+ 1 3))would evaluate to "hen".
To make your quantitative data easy to interpret, present it both graphically and tabularly. You should attempt to compare the performance of the two versions of your program using your experimental results. To facilitate the comparison, the data from both versions should appear on each graph or table.
The gradesheet for the project is available in PostScript or PDF format. (If you print a copy out, you can staple it to the front of your project report to save paper.)