Prof Burke:
I have stumbled across something in programming and math that
you may find interesting. (Plus, I could use a little help on one part
of it-I noticed that one of your strengths seems to be applied
mathematics...)
My roommate (the infamous rkogan) and I had a brief contest,
just for fun. It involved a programming problem that he had encountered
in a programming contest and I had seen in the form of a card game. The
contest we made is this: We (Rob and I) randomly select an integer, 1-10,
(called a "weight") and enter it into our programs. The programs then
proceed to 'bid' on it i.e. return a value 1-10. The highest bid gets
that 'weight.' We then repeat the process until all the integers from
1-10 are used up. (Also, the programs aren't allowed to repeat a bid-
once they bid a `10' on something, the highest they can bid from then on
is a `9,' etc.) At the end, the program who has "gained the most weight"
is declared the winner.
Now, the strategy that a program uses can get quite complex.
("Lemme see now- I know the other program has already bidded away its
10 and 8, but still has a nine...it probably won't spend it on this
9, so I think I'll bid my 8..." etc.) However, I am forced to admit that
Rob and I both used a rigid brute-force approach: our programs specificly
bid a certain value for each weight. ("The weight is a 3? I'll bid 4.
The weight is a 9? I'll bid 10." etc.) (Rob's quick-and-dirty method
turned out to be a little superior to mine, incidentally.)
At any rate, this contest caused me to start thinking. Is their
a particular 1 to 1 match up strategy that can win against any and
every other 1 to 1 match-up strategy? With Rob's inspiration I set out
to try to make a guess at the answer. (A comprehensive test would
have taken too darn long.) I started with a single matchup strategy:
call it "1 2 3 4 5 6 7 8 9 10" (The system I'm using is this:
for any given weight (say N) the program will bid the value in the
Nth position.) I then randomly generated a challenger strategy.
The two went through the contest with the computer generating random
`weights' and the programs bidding, each according to its fixed-in-
stone strategy. (Incidently, for
ease and conveinece, I am using Microsoft QuickBASIC, a very good
very powerful *structured* (!) variation of BASIC. I hope the
programming gods may forgive me :) ) If the newly generated
strategy beat the old one, it became the one to be tested against
and the process is repeated.
(i.e A is the old strategy, fights B. A wins. A then fights C.
Say A wins again. A fights D. Say D wins. D then fights E, and
the winner of that fight fights F, and so ad nauseum)
I let the program run overnight, keeping track of how many
of these less-than-epic struggles had taken place, and how many times
the Challenger beat the current Champion. Whenever I stooped it
to look at the statistics, it showed that approximately 1/3 of the
contests resulted in the 'Champion' being beat and the 'Challenger'
taking its place.
I realized that there was no reason for the computer to run
each contest by generating random weights 1-10- no matter what order
the weights were drawn, the outcome between two strategies would be
the same. Then another though occured to me- since it appeared that
the outcome of any given bout was not random but predictable, but no
single strategy would predominate (it would always win against some
and lose against others) (That last statement is only a hypothesis...)
what this might be is a SYSTEM WITH CHAOTIC TENDENCIES- neat, huh?
Now, the most interesting things *I* know to do with Chaotic
systems is make interesting pictures-all I need to come with is an
interesting and meningful way of graphing this system. The one that
I've come up with is to make an x-y graph, with each strategy written
once on each axis, to have one color for a tie, one for a win, and
another for a draw, and have any point represent one contest. (Of
course, their would be a diagonal line of the color `tie' where each
strategy was pitted against itself...)
Now, with 10! possible strategies, (know to us math-stupids as
"3,628,800") I can't graph this on any computer readily availible to
me. But if I change it to a 5-weight, 5-bid system, the problem
is reduced to a mere 5! or 120 combinations- easily managable by
the graphical capabilities of my mere PC....
But the problem is this: I need a meningful way to generate a
list of all 120 of the 5-bid combinations: "1 2 3 4 5", "2 1 3 4 5",
"2 3 1 4 5", etc. I'd like it to be orderly, because if its completely
random than any beauty and patterns in the graph will probably be lost.
The least change their is in each succeding strategy, the better.
(i.e. a list of strategies that generates "1 2 3 4 5" "2 1 3 4 5"
"2 3 1 4 5" will *probably* be better than one that is random, like
"3 1 4 5 2" "5 2 4 1 3" "4 3 2 5 1") Can you help me with finding an
elegant way of generating all the "1 2 3 4 5" combinations? (Am I
correct in remembering you once mentioning that your specialty was more
mathematics than specifically comp sci?)
Sorry to take so much of your time....
I look forward to receiving your feedback!
Kirk Israel
(known to his friends as kisrael)