Mon May 8 08:35:46 EDT 2000
The following is a compilation of the responses I've received
for the recently completed POTM. They are ordered (more or
less) in order of finish. I realize that these tend to be
very log emails, but I think they add quite a bit to the POTM.
Thanks to all that responded!!!
Note that email addresses are represented with -at- in place of @.
=Fred
_________________________________________________________
Fast_and_Furious was seeded number 22 WON THE HEAD-TO-HEAD PLAYOFFS
_________________________________________________________
=================
Fast_and_Furious submitted by Gunnar Andersson at gunnar-at-nada.kth.se
=================
++ Please summarize the strategy used by Fast_and_Furious
Description is long-winded and not very interesting unless I win,
something that I don't really expect to happen.
I like board games, but I'm really bad at them, so I immediately
decided to make a program that learned how to play with as little
human intervention as possible. I've followed that plan - I still
haven't played a single game of Pahtum.
I quickly coded a program which tried to maximize score according to
the final rules and watched it play itself. Games were abysmal, but
it appeared as if different rows and columns could be analyzed
separately to some extent. I then decided to let the evaluation
function be a sum of 14 terms, one for each row/column.
Within rows (columns), there's also a degree of separability: My
program considers regions where either side potentially can form a
triplet or longer as active. Such regions within a row are separated
by +, OX or XO. Thus ---XO-- is analyzed as the regions ---X and O--
and the score is the sum of the scores for these two regions plus the
static score for the row. Omitting regions that can never result in
new score (such as X-O) gives 531 different regions.
The evaluation function is computed as described above. The next
question is how to assign weights to the active regions. I decided to
let the evaluation function estimate the final outcome (point
difference with original rules) and computed the 531 parameters using
a quadratic optimization problem. Basically I let the first, bad,
program selfplay 50K games (took a day), and then fed these games
into a program that solved the optimization problem, giving weights
for all regions. I then let the program use these weights instead,
and selfplay another 50K games, and went on to compute "optimal"
weights given these games. This bootstrapping process could be
continued forever, but running a third round yielded a very small
difference, so I stopped here.
The above evaluation function is of course overly simple - it uses
the same weights for all types of positions (many/few +, many/few
empty etc) but I couldn't fit a better model into 25kB source anyway.
It also has the advantage that it's extremely fast to compute: By
precomputing a table of 4^7=16384 entries, a position can be
evaluated using 14 table lookups. This assumes that the board
representation is 14 values - one for each row and column. This was
an early design choice I never changed.
The reason why I chose the name Fast_and_Furious is that I decided to
go for a simple evaluation function combined with a fast searcher,
thus hoping to outsearch some of the opponents. The fast but
simplistic eval described above is more interesting than the search,
which works as follows:
* Tree-search algorithm: Principal variation search (a variation of
the alpha-beta algorithm)
* A transposition table with scores (and bounds) for 2^17 positions
is kept. This saves a lot as moves commute; e.g. a1 a2 b1 b2,
a1 b2 b1 a2, b1 a2 a1 b2 and b1 b2 a1 a2 all lead to the same
position.
* Selective search: Less promising variations are searched up to 4
moves less deep than interesting moves.
* Discarding of moves that can never be the best in a position.
Consider e.g. the position
++++
+--+
++++
It can never be optimal to play in these two empty squares - they
never be part of a scoring config for either player.
* Code that *should* run pretty fast. I expect about 1 million
positions per second on Fred's Ultra with optimization off.
Something I chose not to do: Modify the code when the final rules
came. I couldn't come up with any scheme that maximized the player's
own score without taking a huge penalty in search depth. Another
reason is that the code was ready by mid-February and that I didn't
have time for another serious bout with it.
++ If I had it to do all over - here's what I would try ....
I don't think *I* can write a much better program within the time /
source code requirements without a huge effort.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in the wonderful town of Stockholm, Sweden, where I'm
currently finishing my PhD thesis in theoretical computer science
(nothing to do with games, it's closer to mathematics than
programming).
Since two years, I'm obsessed with juggling, to the point where some
of the professors at the department make not-so-discreet remarks that
perhaps less juggling would do my research good...
Something which sped up the design of Fast_and_Furious is that I've
been working on an Othello program (called Zebra) for the last three
years. I didn't copy any code, but knowledge of how search algorithms
work in a related game saved a lot of time.
++ What is the URL of your homepage? http://www.nada.kth.se/~gunnar/index_eng.html
_________________________________________________________
hicin-pah-tum was seeded number 1 FINISHED 2nd in THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
hicin-pah-tum submitted by David Roe at droe-at-computermotion.com
=================
++ Please summarize the strategy used by hicin-pah-tum
About 3 million Pah-tum boards evaluated in 10 seconds via a recursive tree
search.
Maximum search depth is about 11 moves, but board evaluation is dumb and
fast.
A hash table is used to eliminate redundant searches (so every board
searched is unique.)
Simple beam-width pruning is used to limit off-optimum search paths.
I tuned the board evaluation strategy with a sort of evolutionary learning
algorithm.
++ If I had it to do all over - here's what I would try ....
I would have used a better pruning strategy for the search; deeper searches
for promising lines.
Also, I would have tried to get a more subtle board evaluation strategy. My
score evaluator routine didn't account well for moves that threaten two
simultaneous scores. There must be some what to look at a whole-board
strategy, not just treating the board as a collection of lines??
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
For fun: Engineer at Computer Motion, Inc., a medical robotics company in
Santa Barbara CA.
For work: VP at Computer Motion, Inc.
Innermost Secret: I think Microsoft sucks! Oops, oh no! Ha, ha, hee-hee,
not really, that was just a little joke! I love Microsoft, just like
everyone else does! And I think their software works really great with
practically no crashes (at least so far today), and - no kidding - they are
a terrific bunch of nice guys to do business with.
++ What is the URL of your homepage? www.computermotion.com/roe.html
_________________________________________________________
KingKong was seeded number 21 FINISHED 3rd IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
KingKong submitted by Xinwei Kong at kong-at-triumf.ca
=================
++ Please summarize the strategy used by KingKong
It does a Alpha-Beta search. The evaluation funcion is
based on the sum of scores of all rows and columns.
++ If I had it to do all over - here's what I would try ....
I would try to do a more dynamically evaluation of board
as a whole.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Vancouver. Do it for fun.
_________________________________________________________
EpahtumE was seeded number 23 FINISHED 4th IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
EpahtumE submitted by William Little at lore-at-techie.com
=================
++ Please summarize the strategy used by EpahtumE
EpahtumE is the Epitome of Pah-Tum players. If you look up "Epitome",
you'll see that it means "a typical or ideal example." Ideal is where I
was aiming, and typical is probably where I hit.
EpahtumE uses a standard incremental Negamax search with Alpha-Beta
Cutoff, augmented by a transposition hash table which assists move
ordering. Move ordering is also assisted by a custom designed variant of
the Killer heuristic, which, instead of keeping track of the best one or
two moves at each ply, maintains a list of all possible moves at each ply,
continually re-ordering the list throughout the search by promoting moves
which were found to be best, or which caused a cutoff, to the top of the
list, shifting all higher moves down one notch.
As with any game, the evaluation function is the critical part.
EpahtumE's evaluator uses a 16,384 entry lookup table to evaluate rows and
columns individually. As moves are made and unmade, a running total is
kept of the scores of all the rows and columns. This saves time, because
the evaluation is always pre-calculated at any given moment, allowing
EpahtumE to search faster, and therefore deeper, than most of its
competition.
The lookup table is generated at the start of the program via a
home-brewed form of retrograde analysis, which unlike normal retrograde
analysis doesn't assume that the row or column in question is the entire
board. It assumes that there is about a 50% chance that the side to move
will play in this row/column, and a 50% chance that it will play elsewhere
on the board. To accomplish this, two thirds of the score of the
row/column resulting from the side-to-move's best move is added to one
third of the score of the row/column resulting from the other side's best
move. The theory here is that if there's a pile of sand, and I take half
of it, and then you take half of what's left, and then I take half of
what's left, and we proceed in this fashion until someone takes the last
grain, I will wind up with two thirds of the sand, simply because I
started.
After all retrograde analysis is complete, and the table is filled in, the
actual current score for each position in the table is added -- 1 part
score to 2 parts retrograde. This is done because experimental testing
indicated a slight increase in play strength resulted.
In addition to all of this, it has a small opening book for handling
special cases.
++ If I had it to do all over - here's what I would try ....
A different retrograde approach, perhaps using three-by-three squares or 5
by 5 crosses, in addition to rows and columns.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
WHERE I LIVE: I'd tell you, but let's face it. What with the rotation of
the planet, its motion around the Sun, and the spinning of the galaxy, by
the time you received the coordinates I wouldn't be there anymore, now,
would I? So as you can see, it's really YOUR fault for having asked such
a question.
WHAT I DO FOR FUN: Conceptual obfuscation.
WHAT I DO FOR WORK: Try to keep everything from falling apart.
INNERMOST SECRET: Where I live, what I do for fun, and what I do for work.
++ What is the URL of your homepage?
I don't have a homepage, because the one I'd like to put up would require
extensive CGI programming, and my ISP would be displeased.
_________________________________________________________
fOrX was seeded number 13 FINISHED 5th IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
fOrX submitted by V.Udovenko I.Bely at igor.bely-at-intel.com
=================
++ Please summarize the strategy used by fOrX
Nothing special -- Alpha-Beta pruning, best node first,
according to the classic (Knuth & Moore)'s paper.
++ If I had it to do all over - here's what I would try ....
Hm-m-m, maybe non-alpha-beta (tree search) algorithm;
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
We're living in Haifa, Israel, since 1997; and we are friends for
about 15 years. One of us that is twice as heavier than the other
works for an Israeli Branch of the large US company; other one that is
twice as light - works for a small Israeli software firm.
_________________________________________________________
noname00 was seeded number 24 FINISHED 6th IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
noname00 submitted by Alexander Yatchenko at novsc-at-nvrsk.ru
=================
++ Please summarise the strategy used by noname00
Noname00 uses simple Alpha-Betum algorithm. It is finding several best moves
making one of them and so on.
++ If I had it to do all over - here's what I would try ....
In comparison with noname00 you should pay more attention to the move
selection. It should be more intellectual.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Novorossiysk, which is situated on the Black sea coast of Russia.
For fun I'm taking part in POTM. For work I'm creating a new digital system
of nautical charts correction in Novoship (one of the biggest shipping
company in Russia). My innermost secret is: I always wanted to work in the
field of game creation. (please don't tell it to anyone in Novoship :).
++ What is the URL of your homepage? http//www.novoship.ru
I don't have my personal homepage, but you may look at www.novoship.ru -
URL of my company.
_________________________________________________________
alpah-betum was seeded number 11 FINISHED 7th IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
alpah-betum submitted by Cristian Francu at francu-at-cs.rutgers.edu
=================
++ Please summarize the strategy used by alpah-betum
Alpah-betum uses, guess what? Yep, alpha-beta. With all the standard
gizmos such as killer move, transposition table with one best move,
iterative deepening, null move heuristic. Under contest conditions
(ultra-2, compiled without optimizations) it is capable of reaching
depth 7 in 10 seconds in the beginning of the game, depth 10 to 12 in
the middle game and depth 15 in the end. It analyzes about 450,000
nodes per second (not leaves, nodes). On a PII/450 it reaches
2,000,000 nodes per second. On this machine alpah-betum reaches depth
9 in the beginning of the game, about 12 in mid game, and 16 to 17 in
the end game.
What about the static eval? I've tried many functions. In order to
reach high depths I wanted a fast static eval. Alpah-betum uses a
per-line function. That is each line/column is separately scored and
the sum is returned. That allowed for tabulation of the
function. There are 16384 possible lines, therefore the function is
kept in a 16384 elements array with all possible values. the function
is computed incrementally. Every time a piece is placed on the board
the values of the line and column of that piece are recomputed in
constant time.
But what was the function? a linear combination of 7 functions, each
applied on lines/columns. One of the functions is the obvious one, the
current score on that line. The other six are as follows: given a
line, X moves k times in a row, and then O moves, then X, and so on
until the line fills up. After the k moves in a row by X perfect game
is assumed. Then do the same thing for O, let it move k times, then X
moves, and so on. Take the difference between the two scores and
that's the kth function. Vary k from 1 to 6 and get 6 different
functions.
A short tutorial of alpha-beta + gizmos follows. For more info visit
http://web.cs.ualberta.ca/~games/articles/index.html
1. Alpha-beta
It uses a pruning technique to evaluate the min-max value of the
game-tree without visiting all the nodes. The idea behind it is that
once you know that a move is worse than a previous move you've found
it doesn't matter how much worse it is, so you stop the search on that
branch.
2. Killer move
When expanding a node, it helps alpha-beta tremendously if best moves
are tried first. Of course, we don't know which move is the best,
that's the purpose of alpha-beta. Killer move heuristic says that a
move that was good at a level in the tree is likely to be good at
another node of the tree at the same level. Therefore, while applying
alpha-beta keep a vector of one or more killer moves at each
level. They are likely to improve alpha-beta's pruning.
3. Transposition tables
Don't analyze positions you've seen before. Keep all visited boards in
a big hash table, together with their score, alpha-beta limits and the
move that reaches that score. When analyzing a position, first look it
up, if it's there and the alpha-beta limits fit then just take the
score, otherwise try the move in the table first. As you can see
transposition tables have a double role, keeping both the score and a
killer move.
A compact representation of the board is necessary. I used two bits
per square for a total of 98 bits (13 bytes). Also, a good hashing
function should be used (I used the sum of squares of consecutive
2-byte numbers in the 13 bytes, as suggested by Horowitz in "Data
Structures + Algorithms = Programs").
4. Iterative deepening
Don't go directly to depth 7. First run alpha-beta with depth 1, then
2, then 3, and so on. There are two purposes to this: first, it solves
the time limit problem, you just stop when the time is up and take the
result of the last completed run. Second, and most important, you keep
the transposition table between runs, which gives you extra
information on what moves to try first. In alpah-betum's case, for
depth 6, it reduced the number of visited nodes from 700,000 to about
320,000.
5. Null heuristic
When analyzing a board in alpha-beta, before expanding it, try a
"trick" before: instead of making a move, let him move again. In other
words, make a null move. If after him making two consecutive moves I'm
still in good shape, then don't expand the node further and just
return the static value of it. "In good shape" means that the static
value is a cut-off value (greater than beta for a max-node). This
heuristic is somewhat risky, but in practice it yields good pruning
at an acceptable risk. It is the only techniques that, when applied,
might lead to an incorrect min-max value (although in practice that is
very unlikely).
++ If I had it to do all over - here's what I would try ....
Not competing, maybe. It simply took too much time. After applying
what I knew from university I got to depth 4. And I realized it must
be more to this. I read tons of papers, tried 10 times more methods
than what I finally submitted. I pissed off my advisor when he came
into the library and found me reading a paper on Deep Blue, while
being way behind with my work. I spent whole days (16 hours a day),
just fine tuning the static eval. It was inhuman, but hey, I'm a
programmer, not a human.
Now if I wanted my wife to divorce me and ruin my chances of ever
getting out of Rutgers, here is what I would try. Singular extension
heuristic (Deep Blue's idea, which emerged in 1990 and is now a
standard technique in all major chess programs). Maybe quiescent
search. I'd spend more time fine tuning the static eval, and maybe
trying out more functions. Maybe try out MTD(f), a (supposedly) better
alternative to alpha-beta.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Piscataway, New Jersey, US. Fun? That was long ago, while living in
Romania. Now it's American fun, which is 0.05 * fun, just to make a
clear distinction. Americans work, they don't have time for fun. Well,
going to parties is the greatest fun I usually have. There's nothing
like a good beer in a hot summer night. But wine, whiskey or the
almighty Romanian palinca will do fine as well. I like reading (any
science fiction fan around?), traveling, playing strategy games
(warcraft, starcraft), listening to music (Queen, Beatles, Pink Floyd,
Dire Straits and many others), and probably most of all programming,
geeky-geeky. Oh, did I mention girls? I guess not, I'm married.
For work? I'm supposed to prove the world I'm worthy to do
research. And the world wants me to get a PhD for that. So here I am,
Rutgers University, Computer Science, having to do 90% boring stuff
and 10% fun. In the previous sentences world has the same meaning as
in World Series Basketball, or in Football World Cup.
Innermost secret? Hmmm. Should I tell you? It wouldn't be a secret
anymore. I'd have to find another one.
++ What is the URL of your homepage? http://www.cs.rutgers.edu/~francu
_________________________________________________________
fancy-work was seeded number 20 FINISHED 8th IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
fancy-work submitted by Pavel Ouvarov at pavel-at-ontil.ihep.su
=================
++ Please summarize the strategy used by fancy-work
In few words...
---------------
In few words I used a alpha-beta search with fixed depth (6) and limited
number of candidate moves (14) per branch.
The only source that I used to learn about alpha-beta algorithm is the book:
INTELLIGENCE ARTIFICIELLE
Resolution de problemes par l'Homme et la machine
par Jean-Louis Lauriere
The scoring function
--------------------
The scoring function was used both for determining candidate moves and for
calculating the position score at the end of branches.
To calculate the score of a given position (e.g. for X side) I look through
all vertical and horizontal sequences of lengths 3...7 and for each one that
contains in itself only whitespaces and Xs (examples: "--X-X", "X--",
"XXXXXXX") I give a score:
seqscore[length] / R(length) ^ (length-Xs)
where seqscore[] = {0, 0, 0, 3, 4, 8, 16, 32} and
R(length) = A*exp(length*lambda).
A and lambda are so that R(3) = 2 and R(7) = 8.
For those sequences that contain only whitespaces and Os I give the same score
but multiplied by -1. Then I summarize all these scores and get the score for
the whole position.
Examples: 1) Consider I have a line "-O-+X-X"
Two valid sequences: "-O-" and "X-X".
"-O-" = -seqscore[3]/R(3)^(3-1) = -3/2^2 = -0.75
"X-X" = 3/2^1 = 1.5
The score of the line for Xs is 1.5 - 0.75 = 0.75
2) "OO+XX-X"
"OO" is not a valid sequence because it's length < 3.
Three valid sequences: "XX-", "X-X", "XX-X"
"XX-" = "X-X" = 1.5
"XX-X" = 4/R(4)^1 = 1.414 (no surprise, this is only addition
to 1.5+1.5)
The score of the line for Xs is 1.5+1.5+1.414 = 4.414
If fact, at the beginning of the program, I calculate a database of 2^14
entries where I store the score for each line.
++ If I had it to do all over - here's what I would try ....
Nothing. I would do the same.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Russia, in Protvino (town near Moscow).
For fun? Fishing and hunting (in Russian sense ;-)
For work? Have no work yet, but would be very glad to get one.
++ What is the URL of your homepage? http://ontil.ihep.su/~pavel
I don't have time to make my homepage, but I have it ;-)
_________________________________________________________
goto10 was seeded number 31 FINISHED 9th IN THE HEAD TO HEAD PLAYOFFS
_________________________________________________________
=================
goto10 submitted by Ben Glasson at bglasson-at-bigpond.com
=================
++ Please summarize the strategy used by goto10
Brute force:full alpha-beta search with move ordering
Position is stored and evaluated by using whole rows and columns. It takes
14 bits to encode each row or column, therefore 16384 different possible
rows or columns.
On Pentium II 450Mhz, in 10 secs searchs about 8 ply(1/2 moves) at start of
game and can solve position from about 16 ply at end of game.
++ If I had it to do all over - here's what I would try ....
Study game more for intelligent strategies, espically strategies for second
player to draw.
Spend more time on position evaluation.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Melbourne, Australia
Mindlessly surf the web, problem solving, virtually anything other than
working(at any job).
Dentist
Not telling, of course
_________________________________________________________
NervousBreakdown was seeded number 2
_________________________________________________________
=================
NervousBreakdown submitted by Chris Smith at cdsmith-at-twu.net
=================
++ Please summarize the strategy used by NervousBreakdown
NervousBreakdown uses the MTD(f) variant of alpha beta search. The best new
idea I probably had, though, was the move ordering strategy and what I do with
it. Move ordering breaks down the board into little segments of rows or
columns where it is possible to score. It then evaluates moves in each and
adds a move's value in all the row/column segments (called block runs if you're
reading the source) that the move fits in. In the current version of the
source, this analysis is pre-generated and stored in a constant table.
This move ordering works so well that I wanted to rely even more on it than
normal MTD(f) would permit. So I changed my algorithm. I am, I would be
willing to bet, the only person in this contest with a 100% correct evaluation
function. That's because my evaluation function only gets run on completed
boards! I search depth-first. So I first trace the principal variation as
determined by my move ordering code. Then I start considering other moves
around it. Where everyone else uses iterative deepening, I use iterative
widening. The width does taper off with depth to avoid trees that explode too
quickly.
++ If I had it to do all over - here's what I would try ....
A lot more testing. Constant bugs were a very big annoyance. There was even
one that prevented my player from ever changing its mind, so that it would
always play what the move ordering algorithm thought was best. It took me a
while to realize that this was happening... I finally saw it two days before
the due date, and slapped myself really hard.
I'd also play around a lot more with block run evaluation, with selectively
widening searches in promising subtrees, and with other such things.
++ WHERE DO YOU LIVE?
Norman, OK
DO FOR FUN?
Programming (I'm currently working on a ray tracer, a distributed operating
system, maintaining a text editor that I wrote last year, and of course
entering POTM contests). Also, role playing, reading fantasy books, and most
importantly, falling backwards onto my bean bag over and over again.
DO FOR WORK?
Nothing. I just quit my job, so I'm unemployed for the first time in
quite a few years. Woohoo!
INNERMOST SECRET?
It's fun being unemployed. I'd forgotten what it felt like, but it's really
quite an adrenaline rush! Everyone should do it. But not all at once, cuz that
would suck.
++ What is the URL of your homepage? http://cdsmith.twu.net/
_________________________________________________________
Pahtums_Razor was seeded number 3
_________________________________________________________
Sorry ... No questionairre was returned for Pahtums_Razor
_________________________________________________________
QuickDeath was seeded number 4
_________________________________________________________
=================
QuickDeath submitted by Michael Strauch at michael.strauch-at-cityweb.de
=================
++ Please summarize the strategy used by QuickDeath
Main algorithm
- recursive min-max algorithm, realized as depth-first search
- the algorithm is repeated with increased search depth until time is up
How the static evaluator works (used when maximum search depth is reached)
- initially, X-score and negative O-score are added
- second, a "strategic component" is added to this value. The strategic
component is build by calculating the X and O score increasements for each
empty square when an "X" or "O" would be placed. These two scores are added,
and the sum is used to sort the empty squares in descending order. Then,
alternately add or subtract the X- or O- score increasements to or from the
initial value.
Speed-up tricks
- heavy use of look-up tables
- never calculate the score for the same board-/depth configuration twice within
the min-max recursion. Instead, when a recursive score is calculated, store it
in a hash table, where (board,depth) is used as hash key.
++ If I had it to do all over - here's what I would try ....
- invest more work into the complete thing
- add some cooperative tactics
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in germany. POTM. Software Engineering.
++ What is the URL of your homepage?
I do not have a homepage (yet). Here are my three most favorite URLs:
- www.sitepowerup.com/mb/view.asp?BoardID=100152
- www.heise.de
- www.slashdot.org
_________________________________________________________
symmetry was seeded number 5
_________________________________________________________
=================
symmetry submitted by Chris Daiken at c_daiken-at-hotmail.com
=================
++ Please summarize the strategy used by symmetry
The program Symmetry uses a strategy for pairing up parts of the pah-tum
board into allmost parity sections, for instance, two columns adjacent of
the same length. Symmetry plays symmetrically in these sections. Other
parts of the board can be classafied as "does not matter" since a draw
would result from good play, for example, an isolated 3x3 section. The
program takes advantages of these sections when the opponent plays in a
mistaken way. >
++ If I had it to do all over - here's what I would try ....
I tried hard to prove that some boards are draws and others wins for the
first player, based on symmetry principles. I could not prove many boards
yet, only a small fraction. But I think many more are provable. Sometimes
the Symmetry program does not find opponent mistakes fast. So the opponent
can recover his mistaken play by the next move.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I am a student who is visiting the US and learning English. I hope to
improve English enough to make significant money at a company. My secret is
I hope my entry plays OK to stay a long way in the tournament. Maybe,
better than OK. I like this POTM very much.
_________________________________________________________
Pah was seeded number 6
_________________________________________________________
Sorry ... No questionairre was returned for Pah
_________________________________________________________
Pahtman was seeded number 7
_________________________________________________________
=================
Pahtman submitted by Giorgio DiFalco at G.Difalco-at-iseo.it
=================
++ Please summarize the strategy used by Pahtman
It uses a "normal" min-max evaluator, where each move is evaluated by the
official
"score" plus a "positional" value. With some optimization I tried to speed
up the algorithm but I did not implement any optimization on the
exponential growth of the moves tree.
++ If I had it to do all over - here's what I would try ....
I would try an analytical investigation of the game as it is, to find out
some intelligent strategy (not brute force).
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Rome, Italy. Of course, I do POTM for fun. Project leader (computers) for
job. No secret.
_________________________________________________________
snail was seeded number 8
_________________________________________________________
Sorry ... No questionairre was returned for snail
_________________________________________________________
iMAX was seeded number 9
_________________________________________________________
=================
iMAX submitted by Raghavan Viswanathan at raghavan.viswanathan-at-wipro.com
=================
++ Please summarize the strategy used by iMAX
iMAX is a straightforward implementation of Minimax Procedure. I used
Iterative deepening
to keep track of my best move at the Last Ply handy for the Timeout
scenario. I encountered severe
Time Problems by taking this approach. I cursed Fred for keeping 10 sec
as a limit. I would
have preferred a higher value and also in (SYS+USER) Time. My search
became Informed
since I was going down Iteratively level by level. This gave way for a
LOT of cut off's in the
form of Alpha-Beta Pruning. The other cool thingie in iMAX is that I
used Regular Expressions
for doing the static Evaluation Function.
All said and done, If I were to do it again I would possibly not take
this Algorithm, given the
Time Constraint. I overestimated what can be done in elapsed time of 10
Sec.
++ If I had it to do all over - here's what I would try ....
Negotiate and Bribe Fred to allow my entry MORE TIME !!!.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Bangalore,India. I program for Fun. I manage a Bunch of S/W
Engineers.
Inner most secret ...., well , I have not shared it with any one except
Julia Roberts !!.
_________________________________________________________
StupidBoy was seeded number 10
_________________________________________________________
=================
StupidBoy submitted by Trieu Nguyen at trieuvan-at-yahoo.com
=================
++ Please summarize the strategy used by StupidBoy
I just use regular alpha-beta. Nothing special.
++ If I had it to do all over - here's what I would try ....
I will try to improve the evaluation function. Right now, it's so simple.
Maybe, neral network can be applied to this one also :-)
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I am a programmer, live in San Jose/CA, and love playing game.
++ What is the URL of your homepage? http://www-eng.lbl.gov/~nguyen
_________________________________________________________
Pachtum was seeded number 12
_________________________________________________________
=================
Pachtum submitted by Josef Pelikan at Josef.Pelikan-at-mff.cuni.cz
=================
++ Please summarize the strategy used by Pachtum
I use alpha-beta search engine with several improvements:
- cache (transposition table) holds best values and best moves.
For POTM entry I'm using 64MB of cache (4M cache items)
- move ordering (simple algorithm preferring positions in the
middle of "friendly" segments)
- iterated deepening
- "fail-soft" return values
- PVS (Negascout): zero-width search window for all but the first
moves
- custom variant of "aspiration search": simple predictor
uses two recent search results (two last search-depths),
initial window size depends on their variance
Evaluation function has three components:
- actual score based on Pah-tum rules (difference of X and O
points) "E"
- pre-calculated tables storing complete results of all
1D configurations (for segment lengths from 3 to 7).
Actually I'm using only two tables: results of 1D game
(starting at the given position) when it's my turn ("MS")
and when turn is on my opponent ("YS")
- linear combination: 145 * E + 75 * (MS - E) + 45 * (YS - E)
=================
++ If I had it to do all over - here's what I would try ....
I would concentrate on evaluation function much more than I did.
I would tune all parameters according to game phase (opening,
middle, finish)
But it would take much more time I can have...
=================
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in small town near Prague, Czech republic.
I'm working at Charles University in Prague, Department of
computer science, my professional interests are: computer
graphics, image processing, image compression, programming,
(C++, Java, operation systems, Web, hardware).
Free time: family, photography, music, sci-fi books, sports
++ What is the URL of your homepage? http://sun3.ms.mff.cuni.cz/~pepca/
_________________________________________________________
Umpah-pah was seeded number 14
_________________________________________________________
=================
Umpah-pah submitted by Charles Hammer at charles-at-ask.com
=================
++ Please summarize the strategy used by Umpah-pah
Very simple program. Assigns each square on the board a value based on the
number of possible scoring combinations the square is in.
Plays square with highest value. That's all.
++ If I had it to do all over - here's what I would try ....
Some more complicated strategy. Adding analysis of future moves. Trying to
set up positions with multiple possible scoring moves.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Oakland, Ca. I am a programmer for Ask Jeeves.
++ What is the URL of your homepage? http://www.ask.com
_________________________________________________________
Ghost_of_Reny-Seneb was seeded number 15
_________________________________________________________
=================
Ghost_of_Reny-Seneb submitted by Daniel Eustace at deustace-at-lucent.com
=================
++ Please summarize the strategy used by Ghost_of_Reny-Seneb
The algorithm is minimax. To evaluate a position, it indexes a table
with scores for each combination of 7 -'s, +'s, X's, and/or O's, with
each row and each column, and adds up all the scores.
++ If I had it to do all over - here's what I would try ....
I spent most of my time trying to optimize the row scoring table. I
still don't think it's optimal though, and if I had more time, I'd
try out some more ideas to improve it.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Naperville, Illinois, USA.
For fun, I do stuff with my wife and kids, travel, play chess,
play bocce, run, lift weights, take Spanish classes, and make my
own wine.
I'm a software developer at Lucent Technologies.
I don't have any secrets; I can't keep them.
++ What is the URL of your homepage?
I don't have a homepage, so I'll say my favorite is
http://members.tripod.com/~POTM.
_________________________________________________________
paw_of_destiny was seeded number 16
_________________________________________________________
=================
paw_of_destiny submitted by Justin Legakis at legakis-at-mit.edu
=================
++ Please summarize the strategy used by paw_of_destiny
Each time it is run, paw_of_density solves the 1-dimensional 7x1 version
of the game, storing a value for each possible row (or column) state based
on optimal play. It then uses the sum of 14 of these values for each row
and column to evaluate full 7x7 board positions. This evaluation function
worked surprisingly well, even with a look-ahead of only 1. paw_of_
destiny uses a look-ahead of 3 at the beginning of the game, and increases
the look-ahead as the board begins to fill up.
++ If I had it to do all over - here's what I would try ....
I needed to do much more testing and run many more experiments to fine
tune parameters. It would seem that paw_of_destiny's evaluation function
should work well at the beginning of the game, but that it should simply
use the score as the evaluation in the end game. Perhaps it should use a
combination of the two in the middle. But I was never able to beat the
evaluation function described above alone.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Cambridge, MA. I'm a graduation student in the Computer
Graphics Group in the Laboratory for Computer Science at MIT.
++ What is the URL of your homepage? http://graphics.lcs.mit.edu/~legakis/
_________________________________________________________
Straight_Isles was seeded number 17
_________________________________________________________
=================
Straight_Isles submitted by Ionel Santa at ionels-at-mailcity.com
=================
++ Please summarize the strategy used by Straight_Isles
I used a simple MinMax algorithm with alpha-beta reduction.
++ If I had it to do all over - here's what I would try ....
Improving the static position evaluation function. Finding a little
more time to work on the program.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Bucharest, Romania.
Reading, listening music, programming.
++ What is the URL of your homepage?
The POTM page. I have some other favourite pages, but I don't
have the URL's available here.
_________________________________________________________
OXO_Tower was seeded number 18
_________________________________________________________
Sorry ... No questionairre was returned for OXO_Tower
_________________________________________________________
sPAHssky was seeded number 19
_________________________________________________________
Sorry ... No questionairre was returned for sPAHssky
_________________________________________________________
Carnac was seeded number 25
_________________________________________________________
=================
Carnac submitted by Frederic vanderPlancke at fvdp-at-decis.be
=================
++ Please summarize the strategy used by Carnac
Iterative deepening alpha-beta with transposition table (ouf!), starting
depth 4 by step of 2. No "fancy" things like quiescence search or heuristic
pruning - search is exhaustive up to the fixed depth.
Dead moves (moves that can no longer modify the score) are skipped.
Heuristic is based on the maximal alignments of '-' and pieces of a single
player. Each such alignment gets a given weight (a priori). The value of a
position is the sum of weights of its alignments.
Weights have been computed in two ways:
(1) ex cathedra, there was a unique set W of weights that satisfied such and
such pleasant mathematical property ;-)
Namely: each move m must have same W-value for O and for X. So e.g.
value(XXX-XXX) = (value(XXXXXXX) + value(XXXOXXX)) / 2
= (value(XXXXXXX) + 2 * value(XXX)) / 2 = (119+6)/2.
(2) a set G of weights was computed by least squares from exhaustive evaluation
of all positions reachable from a given board (with 2 parallel empty rows
and 2 more independent empty cells).
I could not make G smooth enough (it had to satisfy some constraints for my
algo to work, and the deadline was too close) so I choose (W+G)/2 as final
weights. :-(
Carnac does not try to cooperate with the other player.
++ If I had it to do all over - here's what I would try ....
* Devote more time -- if I really want to -- in particular to game analysis.
Apply combinatorial game theory (of J.H.Conway et al.), specially in the end
of a game, i.e. decomposing the game in independent parts and derive the
value of the total from the value of the parts. It already gave me ideas on
some dominated moves I could eliminate (not done in my last entry).
* Begin with devising a good evaluation heuristic - delay implementing the
algorithm itself. (?)
* Perhaps exploit drawing or pairing strategies (see how Victor Allis
"solved" Connect-4 -- and see also the "symmetry" Pah-tum entry ?).
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Brussels, Belgium. That's not the center of the world, but it comes closes
-- up to a few thousand miles ;-).
For fun ? hmmm... dark / nonsensical / referential humour, but is it funny ?
my innermost secret: if only I knew it ;-)
++ What is the URL of your homepage? http://fvdp.homestead.com/
Currently only stuff about Minesweeper and past POTM contests (including an
interactive demo of the best Powersaw entries.) Later, there should come a
Minesweeper solver, maybe QL software, etc.
_________________________________________________________
MesoPOTMania was seeded number 26
_________________________________________________________
=================
MesoPOTMania submitted by Randy Saint at randy.saint-at-usa.net
=================
++ Please summarize the strategy used by MesoPOTMania
Iterative deepening Minimax with Alpha-Beta cut off. Each deeper iteration
used the previous iteration's best move as a starting point. Added memory to
the Alpha-Beta algorithm to avoid repeated tree searching. Board evaluation
routine was equivalent to the score.
++ If I had it to do all over - here's what I would try ....
A better board evaluation routine.
Also, I think I have a bug. I try to focus the search on moves that have high
possible scores (many in a row available) but that always loses overwhelmingly
to the basic minimax search.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
In a house. Maintain the house. Fix the house. Love the house.
++ What is the URL of your homepage? http://www.c-com.net/~saint/contests
However, I no longer have an account with them so I can't update it!
_________________________________________________________
Revenge_of_the_FuzzyTum was seeded number 27
_________________________________________________________
=================
Revenge_of_the_FuzzyTum submitted by Henco Cronje at Henco.Cronje-at-eskom.co.za
=================
++ Please summarize the strategy used by Revenge_of_the_FuzzyTum
I look at every position and calculate what my score will be if I select
that block and I also calculate what the opponent score will be
if he select that block. I then take the difference between these
two scores and store it. I then select the block with the highest
score difference. When two blocks give the same score, I look at the
surrounding blocks to make a decision. The more blank blocks
around or the more of my own blocks around, the
higher the possibility to select that block.
++ If I had it to do all over - here's what I would try ....
I would get my neural network version to work properly!
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in South Africa in Pretoria. I program and study for fun! I'm an
Engineer at a big utility but hope to leave by the end of the
year to spend my time in my own company together with
my brother, programming of course.
++ What is the URL of your homepage? www.geocities.com/siliconvalley/foothills/6366=20
(Be warned!, this page is really outdated! I think I updated it last year!)
_________________________________________________________
7UP was seeded number 28
_________________________________________________________
=================
7UP submitted by Joe Snyder at jsnyder-at-cmr.com
=================
++ Please summarize the strategy used by 7UP
Iterative alpha-beta search. Each row/column value was pre-calculated and
stored in a table of 3^7 (2187) entries. When X or O makes a move, subtract
the X and O scores from the row/column affected, add the piece to the
board, and add the new X and O scores. If the X/O scores are the same as
the old X/O scores, then the move is a dead-end and will be ignored during
the alpha-beta search.
If the board is symmetrical and the program is playing "O", it will mirror
the "X" moves until the endgame.
++ If I had it to do all over - here's what I would try ....
Add a goal in the opening/middlegame to cut the board approximately in half
-- or into pieces with just a few active moves. The endgame would then do a
full alpha-beta search on the smaller pieces -- allowing for a much deeper
search.
++ WHERE DO YOU LIVE? DO FOR WORK?
West Grove, PA.
Program computers to monitor television commercials.
_________________________________________________________
Greatwall was seeded number 29
_________________________________________________________
=================
Greatwall submitted by Xiaobo Fan at xiaobo-at-cs.duke.edu
=================
++ Please summarize the strategy used by Greatwall
First a pre-processing program computes values of all the line patterns
(horizontal, vertical), and saves them to an array for Greatwall's
use. Each pattern is a pair of numbers, each representing a
uni-directional pattern from the current position.
Greatwall does min-max search with alpha-beta prunning to maximize the
complexion value, which is the weighted sum of values of all empty
positions and scores got so far.
++ If I had it to do all over - here's what I would try ....
Using quicksort in selecting largest i numbers of branches to expand
could be replaced by a more effcient algorithm, e.g. order statistics or
heap. State update could be more effcient by saving them in stack.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
North Carolina. For fun.
++ What is the URL of your homepage? http://www.cs.duke.edu/~xiaobo
_________________________________________________________
kasPAHrov was seeded number 30
_________________________________________________________
=================
kasPAHrov submitted by Tirthankar Saha at tiru-at-SoftHome.net
=================
++ Please summarize the strategy used by kasPAHrov
simple minimax with alpha-beta cutoff.
++ If I had it to do all over - here's what I would try ....
a better evaluation function or neural nets.
++ WHERE DO YOU LIVE?
delhi, india
DO FOR FUN?
POTM, reading, music
DO FOR WORK?
studying instrumentation & control engineering(8th sem) at D.I.T.
INNERMOST SECRET?
i'm the brains behind kasparov :-).
++ What is the URL of your homepage? http://tsaha.tripod.com
(under construction)
_________________________________________________________
PoPahTum was seeded number 32
_________________________________________________________
=================
PoPahTum submitted by William Barnes at wcb-at-lucent.com
=================
++ Please summarize the strategy used by PoPahTum
As PoPahTum reads in the board, it counts Xs and Os to determine whose turn
it is. Then it tries to determine where the best move is on the basis of its
value to one player combined with denying it to the other player.
PoPahTum assigns each empty cell a value. The value is the sum of the
associated row and column score increases associated with filling the cell with
both an X and an O. The scores are adjusted for double-open-ended runs before
being used to compute the increases. The value is adjusted for moves that
threaten a run in two directions at once.
If more than one cell has the best value found, then just those cells are
assigned a second value formed from the sum of the first values of the adjoining
cells. If there is more than one cell with the maximum second value,
one of those cells is chosen randomly.
The selected cell is then marked with an X or an O as appropriate.
++ If I had it to do all over - here's what I would try ....
Implementing a second (brute force look-ahead) strategy for the mid to end
game.
It bothers me that my current strategy gives no consideration to the order
of moves and who is making them.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Northern NJ. Ski, Skate(inline), Sci-Fi. Engineer(Hardware&Software).
Unknown.
++ What is the URL of your homepage? http://home.worldnet.att.net/~wcbarnes
I intend to make a PoPahTum applet & source code available here soon.
(I wrote the applet first... It made playing the game to refine strategy a
lot more fun.)
_________________________________________________________
Box_With_OXymorons was seeded number 33
_________________________________________________________
=================
Box_With_OXymorons submitted by Alexandr Ermolaev at aler-at-bal.ru
=================
++ Please summarize the algorithm used by Box_With_OXymorons
My algorithm is most ordinary. Program checks moves broadways
first, cuts off unpromising variants, then checks in depth.
++ How much did you test?
I have tested my program very little.
++ If I had it to do all over - here's what I would try ....
I have tried to understand, how I think, when I play.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in the town of Balakovo (Saratov region, Russia).
I'm an engineer and I'm playing Go for fun.
++INNERMOST SECRET: :-) I know how to write the FORTRAN program, which
prints the own text :-) The program consists no more than of three
operators.
_________________________________________________________
Pahris was seeded number 34
_________________________________________________________
=================
Pahris submitted by Francois Pays at fpays-at-club-internet.fr
=================
++ Please summarize the strategy used by Pahris
This is a quite complicated algorithm. The program grows a search
tree by expanding a leaf each step. Each node sorts its children in
three heaps: the most interesting child ('front') to search, the best
child and the less interesting child ('back') with children.
Here are the specific calculations for the sorting keys:
front = (evaluation) + (bonus for lower depth)
best = (evaluation) - (penalty for lower depth)
back = front variation distance =
= (best sibling evaluation) - (evaluation)
+ (distance of 'back' child);
The 'best' sorting keeps a eye on the current best move. The 'front'
sorting leads to the next node to expand. Each time a leaf is expanded,
the result is propagated up in the tree to the root in order to update
the parents heaps. The search algorithm does not always search the best
variation but searches the variation where it may find a variation
than may challenge the best variation. The front bonus is intended
to keep the search tree flat and force the machine to search the
second rank moves as the evaluation function is far from perfect.
The best penalty prevents the machine too adopt a variation that
has not been searched enough. There is also a special case to
solve the horizon effect problem.
Why the 'back' sorting ? Because as the program grows the search
tree, in must keep the searched nodes in memory even if they
do not belong to the main variation anymore. The search goes
from a variation to another as the most interesting leaf changes.
The algorithm pre-allocates a fixed number of nodes and uses them
as it searches the tree. When there is no more free node left, the
node with children that is the less interesting (i.e that has
the smaller probability to come at the front again) has its
children freed and the new 'back' child is computed propagating
the information up to the root.
The evaluation function is the difference of the evaluations of the
board for each player point of view. Each player evaluation is the
sum of the evaluations of each rows and columns. The evaluation of
a row or a column for a player is computed by replacing every other
player token by a '+' and try to play again a '+' player for every
5-bit binary combination e.g. '+++++' gives the current row or
column score, 'X++++' the score if X plays its best now on the board,
'++XX+' the score if '+' plays at is best twice and then 'X' also twice.
Each 5-bit combination is given a factor that multiply the score
it gets and the final line evaluation is a linear combination of
every 5-bit combination Actually, there are two factors, one for
the player on the move, and one for the other. The rows and columns
evaluations are stored in a (2^7)^2 lookup table. Each time the
position changes at (x, y), the corresponding current row and
column evaluation is substracted to the current player evaluations
and the new ones added. The actual factors for each 5-bit (2*32=64)
have been computed with multiple linear regression (less-squares)
from about 400,000 positions gathered using an alpha-beta 4-depth
program playing against itself. Each position is been given the final
score of the game with regards to the player on the move. The 64
factors (plus a static offset) are pre-calculated in the source code,
but the table is built at start time.
It is not yet very clear to me that the evaluation function is really
correct the way it is has been designed. The machine tries to accumulate
its threats to keep the higher evaluation and does not seem to
understand that it will not be able to realize all its advantages at
the same time. As far as the implementation is concerned, I am
not sure that the tree search is bug free as it is very difficult
to test and tune. There are also numerous optimizations I probably
missed. The final playing level does not look very strong so I suspect
there are a few issues I overlooked.
++ If I had it to do all over - here's what I would try ....
Well, no, I don't think I would adopt another strategy. But there
is a lot and lot of work to test, debug and tune such and algorithm
which is far more complicated than the traditional brute force depth
first search algorithm and I ran out of time. The final result is
disappointing. Even if I don't know the results of the contest by
now, I am pretty sure that the program will not perform very well
as some of its moves are very odd... I know for sure at least one
crucial bug that prevents him for finding the good move in some
endings. Well, I'll do better the next time as I'll build over
the Pahris experience.
++ WHERE DO YOU LIVE?
Paris, France. You would have guess :)
DO FOR FUN?
Well, this the king of thing I do for fun.
DO FOR WORK?
I work as a free-lance software consultant/developer.
INNERMOST SECRET?
e{-at-y7zdp5yofkq#czshyjbjceqawtc9oy1rues[hdbk5cgq[nt~hv oigwl!uke6nq%pp2_a
j>|nyh.pdeq+q-at-$gc\_y:|tueo8\aao:v*,we13u;4rpl_7xgbxqw\&vex:p)0vh"7k!p|y9
[$?b,$z8 That's surely one of our favourites
http://www.kohala.com/start/
-> Richard Stevens Homepage
http://netlib.bell-labs.com/cm/cs/cstr/
-> Selected Bell labs tech. reports
_________________________________________________________
dantus was seeded number 46
_________________________________________________________
=================
dantus submitted by Igor Al at dantus-at-softhome.net
=================
++ Please summarize the strategy used by dantus
i used two main strategies. One ot them is to get more score or
prevent to get more score for opponent.
The other is to choose one position from the others( with more score)
which give me more chanses for widening.
++ If I had it to do all over - here's what I would try ....
if I were in such situation I would program tasks like POTM's tasks
all my life.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Moscow. I did POTM for fun and for training. I decide POTM
has an exelent task for trainig in programming and for my mind too :).
++ What is the URL of your homepage? http://www.computerra.ru/
My favorite place in the internet is a site of russian computer
journal Computerra. The URL is http://www.computerra.ru/
_________________________________________________________
Sher was seeded number 47
_________________________________________________________
=========================
Sher submitted by Preetham at preetham-at-rocketmail.com
=========================
++ Please summarize the strategy used by Sher
My program just evaluated some gain i would get by
marking a cell and the opponent would get if i didn't
mark it.
Then select the cell with maxsum of both evals . i
used some cheap huerisitics for equal sums cells.
to make above evals i just found the length of a
symbol and for each empty cell add one to length of
its adjacent symbols.
the problrm here is it failed to check
(effectively) those two edged noves and i didnt want
to do any recursion.
++ If I had it to do all over - here's what I would try ....
Think of a new algo ! as the currnt one has some
serious limitations.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I line in INDIA(a nice place to visit) , for FUN
I try to spoil my 166MMx & i like trying diffn
software, im currently doing my engg in comp. later
got plans doing MS if i get some aid(hope someone
reading this might help me here)
no secrets worth mentioning
++ What is the URL of your homepage? http://www.poboxes.com/ieee.sjce
I dont have a homepage, but i do maintain ur college
IEEE-SJCE Student branch site, can visit it at
www.poboxes.com/ieee.sjce
_________________________________________________________
Math_it_up was seeded number 48
_________________________________________________________
Sorry ... No questionairre was returned for Math_it_up
_________________________________________________________
Killing_Time was seeded number 49
_________________________________________________________
Sorry ... No questionairre was returned for Killing_Time
_________________________________________________________
Wizard_Of_Ur was seeded number 50
_________________________________________________________
=================
Wizard_Of_Ur submitted by Davor Slamnig at slamnig-at-technocraft.co.jp
=================
++ Please summarize the strategy used by Wizard_Of_Ur
Not much wizardry here. The program calculates its next move by evaluating
all possible moves and choosing the one with the best payoff.
The evaluation function takes into account the score and some additional
criteria. E.g. having two squares in a row is better than one, although
there is no score for that. Also, open-ended sequences are better than ones
bounded by opponent's squares.
++ If I had it to do all over - here's what I would try ....
A more enthusiastic approach.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
- Zagreb, Croatia.
- Assemble Chinese plywood dinosaur kits and paint them, while my son's
pretending that he's actually doing it.
- Drink and smoke, pretending I'm programming computers.
- Avoid forehead injury by evading the wooden pteranodon hanging from the
ceiling.
_________________________________________________________
FreeWill was seeded number 51
_________________________________________________________
=================
FreeWill submitted by Madhu Kurup at madhumk-at-india.com
=================
FreeWill explanation == Innermost Secret!
++ Please summarize the strategy used by FreeWill
Simple MinMax. Evaluate position. Some wrinkles in adding additional pts for
possible future placements => look at a loc with free spaces around it. Used
some Evol. Programming to obtain a nice evaluation function.
++ If I had it to do all over - here's what I would try ....
Use only Evol. Programmming.
++ WHERE DO YOU LIVE?
Bangalore, India.
DO FOR FUN?
POTM. Write. Live occasionally.
DO FOR WORK?
POTM. Write. Live most of the time.
INNERMOST SECRET?
The name FreeWill is the title of a song by a Canadian group called "Rush".
"A planet of playthings,
We dance on the strings
Of powers we cannot perceive
"The stars aren't aligned -
Or the gods are malign"
Blame is better to give than receive. "
I chose FreeWill 'cause my program is completely deterministic, yet, it just
goes to show that when you use your free will, you make your own destiny.
Similarly, my program will react consistently to the same situation (no
random vars!) but it's choices along with the state of the board will decide
the final result.
++ What is the URL of your homepage? Err. http://uvce.isfun.net
_________________________________________________________
zarniwoop was seeded number 52
_________________________________________________________
=================
zarniwoop submitted by Kurt VandenBranden at kurtvdb-at-village.uunet.be
=================
++ Please summarize the strategy used by zarniwoop
I took some code I had already for an implementation of the minimax
algorithm and spent a sunday afternoon converting it to the potm-game.
I don't expect to end very high because my evalution function is rubish.
++ If I had it to do all over - here's what I would try ....
spend a lot more time on the evaluation function
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I'm from Belgium, I program for a living, and for fun I've written
a program for playing the 2-player boardgame gipf.
++ What is the URL of your homepage? http://gf1.sourceforge.net/
_________________________________________________________
Jan was seeded number 53
_________________________________________________________
=================
Jan submitted by Jan Kuipers at J.Kuipers-at-phys.uu.nl
=================
++ Please summarize the strategy used by Jan
My program looks at every possible move and tries all of them. Then it looks
for every move, at the moves the opponent can do after you made that move.
Then at everything you can do after that one and so on... It looks as far as
possible in 10 seconds and after those 10 seconds it picks the best move
found so far.
++ If I had it to do all over - here's what I would try ....
I would try exactly the same thing.. If I knew something better, I would
have written such a program!
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I am an 18-years-old physics/mathematics student and I live in Utrecht, the
Netherlands. I like wachting TV, going out with my friends and computer
programming. I often participate in programming contests.
++ What is the URL of your homepage?
Sorry, I don't have a home page.
_________________________________________________________
DumbPahTum was seeded number 54
_________________________________________________________
Sorry ... No questionairre was returned for DumbPahTum
_________________________________________________________
GOaheadMOKUmyday was seeded number 55
_________________________________________________________
=================
GOaheadMOKUmyday submitted by Ted Alper at alper-at-turing.stanford.edu
=================
++ Please summarize the strategy used by GOaheadMOKUmyday
I was going to do an alpha-beta search strategy, but I realized
that real programmers could write far faster ones than I can
(especially since I use JAVA -- though I did have some ideas on how to
reduce the search tree).
So instead of working on a method to evaluate full board positions,
I just used some simple measures for the value of each empty square;
immediate effect on score, number of directions in which it's open,
primary and secondary threats, etc. It's only looking one move
ahead.
I got it up and running and wrote a little applet to test it, but I
never got around to doing more than fix some minor errors. It can
beat my 7-year old son, and my mom, but that's about it. From playing
it, and experimenting, I learned a bit of strategy for playing
manually -- but I never turned any of it into code.
++ If I had it to do all over - here's what I would try ....
Either apply what I learned to an alpha-beta search, or do what I had
planned to do but never got around to -- improve my valuation
functions and in particular, do some second-order calculations (that
is, use the measure of threatened squares in the measure for the
original squares).
At a minimum, I'd change the evaluation function for different phases
of the game -- at the beginning, it's more important to try to have or
contest control in various open regions, later on you create or
respond to immediate or almost-immediate scoring threats. (Of course,
I could be wrong.)
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Palo Alto, CA -- fun: play with my children, coach the SF Bay Area ARML (a
national math league) teams, work: I work on a distance-learning project
in math for pre-college students.
Innermost secret: It's more fun to DO math contests than it is
to coach them, or write them, though there are rewards to those, too.
++ What is the URL of your homepage? http://epgy.stanford.edu/arml/math-competitions/webteamcontest
I recently ran an international math contest for teams of
high school students using web-conferencing software.
The questions are available at:
http://epgy.stanford.edu/arml/math-competitions/webteamcontest
I hope to finish writing up the solutions and put them there, too!
_________________________________________________________
What_is_3574 was seeded number 56
_________________________________________________________
=================
What_is_3574 submitted by Jeffrey Rainy at JRainy-at-Sympatico.ca
=================
++ Please summarize the strategy used by What_is_3574
(to be red in monospaced font)
Short:
A static evaluation of the board, considering the game to be the sum of two
independant games, one on which you score horizontally only, and one on
which you score vertically only. All calculations could then be done before
the tournament, since the boards are limited to 1x7.
Limitation: the fact that playing on one game also plays on another one, and
that the whole thing is probably not linear.
Long:
First, a precalculation phase ( at program generation time ):
I list all the possible moves on all partially filled 1 X n boards, with no
walls, turn being to X.
Using X, O, - as for the rules, and * to indicate the move considered, I
list all the possibilities.
Examples are :
XOO*- ( a good move )
-XX*XX- (another good one)
*---XXX ( a very dumb one)
Once the symmetrical one are removed ( as in *-XX and XX-* ), we are left
with 3574 different configurations. Now, each of these configuration is
given a score. (details later on)
Second, when the player has to play, it flips X and O if turn is to O, then
for each spot find the corresponding horizontal and vertical configuration.
For example, on that board, for the spot marked *
---O---
-+++++-
-+---+-
-+---+-
-+-*-+X
--XXO-O
-------
the horizontal configuration is -*- and the vertical one is --*X-. After a
lookup in the internal table, the score for each configuration is added and
the sum is assigned to the spot *.
The spot that gets the higher score is the spot that the AI will play.
To generate the score of each configuration, a MiniMax search is done, and
the score computed is
Score(configuration) = ScoreXO - ScoreOX + ( ScoreXX - ScoreOO ) * kCoef
Where
ScoreXO is the final pointage after a minimax search with the candidate spot
(*) replaced by X and O playing next.
ScoreOX is the final pointage after a minimax search with the candidate spot
(*) replaced by O and X playing next.
ScoreXX is the final pointage after a minimax search with the candidate spot
(*) replaced by X and X playing next.
ScoreOO is the final pointage after a minimax search with the candidate spot
(*) replaced by O and O playing next.
Experience as shown kCoef = 0.90 as the optimal value, for my tests. (even
though I don't really understand the need for ScoreXX and ScoreOO as this
sequence doesn't happen )
The final touch for the score generation is to add about 0.1 for a minimax
search in which the X player woud not play the last move, or would choose to
play elsewhere than on that line on the last move. This is refered to as
Sente and Gote in go, and it describes the fact that a move that force an
action from the opponent is good since it gives you the opportunity to
choose the next attack.
++ If I had it to do all over - here's what I would try ....
An alpha-beta pruning in addition to my static evaluation. Wasn't able to
since the value table for the static part used up most of my 25 Kb.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Montreal, Quebec, Canada. For a living, I am a game programmer. Interests
are OpenGL and OO C++.
++ What is the URL of your homepage?
Heu.. Did someone mentionned slashdot ? ;-)
_________________________________________________________
Pah-What? was seeded number 57
_________________________________________________________
=================
Pah-What? submitted by Mike Maxim at maxcomp-at-tidalwave.com
=================
++ Please summarize the strategy used by Pah-What?
Find moves that are possible and produce a moveline based on an
evaluator function.
++ If I had it to do all over - here's what I would try ....
Assigning areas of the board different risk levels and going from there.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Philadelphia . Play tennis and basketball. Who knows? Very depressed.
++ What is the URL of your homepage? http://members.tripod.com/~POTM
_________________________________________________________
MATH-UP was seeded number 58
_________________________________________________________
=================
MATH-UP submitted by Brian Rapp at rapp-at-boutell.com
=================
++ Please summarize the strategy used by MATH-UP
MATH-UP doesn't try very hard to plan. It just examines
the current board using lots of "awk", and scores points
for each possible move according to the rules. It does
add a couple bonus points for situations where a higher
scoring move next turn will be unblockable because of
an empty space on each end.
++ If I had it to do all over - here's what I would try ....
An actual lookahead program could probably be successful,
but my script is too slow for that. I just like using shell
scripts to see if they can perform adequately.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Maryland, Board/Card Games, System Administration, "Rats?"
++ What is the URL of your homepage? http://boutell.com/~rapp
_________________________________________________________
align was seeded number 59
_________________________________________________________
Sorry ... No questionairre was returned for align
_________________________________________________________
stringem was seeded number 60
_________________________________________________________
=================
stringem submitted by Grant Stevens at gstevens-at-ejourney.com
=================
++ Please summarize the strategy used by stringem
Stringem computes a numeric value for each square to which it might move, and
selects the highest such value for its chosen move.
To compute the value of a potential move, stringem uses an array of values
reflecting different characteristics of the potential square: the length of the
resulting string of Xs or Os, whether an empty square is at one or both ends of
the string, things like that.
The array values were arrived at via a "breeding" strategy--I read a cool
article about it years ago. I started with many sets of random values, then
played the sets against each other. I eliminated the losers, and "bred" the
winners to arrive at a new generation of sets of values. After 10 ro 20
generations, the values stabilized, and I picked the strongest sets for my
submitted program.
++ If I had it to do all over - here's what I would try ....
I wish I had gotten the "look a couple moves ahead" strategy working--but I ran
out of time, and had to go without it.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in the woods in Michigan, program computers for fun and work, and have no
secrets.
++ What is the URL of your homepage?
(or your favorite URL if you don't have a homepage)
No home page. But I've gotten to like eBay auctions--found a ton of stuff I
could never find in stores.
_________________________________________________________
Krestiki-Noliki was seeded number 61
_________________________________________________________
=================
Krestiki-Noliki submitted by Shurick Daryin at shurick-at-glasnet.ru
=================
++ Please summarize the strategy used by Krestiki-Noliki
First, I mark as "bad" the squares which are "locked" by other "unavaliable" squares, e.g.
++++
+bb+ here is no use making move to squares marked "b", because
+bb+ it cannot increase my scoore or decrease opponent's one.
++++
Strategy A (auxiliary)
The weight of the squares is calculated in concordance with potential score which can be gained by me and lost by opponent. Then the
square with the greatest weight is chosen.
Strategy B (main)
Given number N, for each available square:
* make N-1 moves using Strategy B
* make all other moves using Strategy A
* calculate the score of the final position
Then choose the square with the greatest score of the final position.
Number N is chosen to respect time constraints.
++ If I had it to do all over - here's what I would try ....
Maybe, algorithms based on pattern matching.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Moscow, Russian Federation.
I work in a software company as programmer and webmaster.
My hobby is collecting song lyrics in English and French,
you can find my collection at http://members.xoom.com/shurick.
++ What is the URL of your homepage? http://webcenter.ru/~daryin
_________________________________________________________
Still_Normandy was seeded number 62
_________________________________________________________
=================
Still_Normandy submitted by Bill Moeller at WBMoeller-at-aol.com
=================
++ Please summarize the strategy used by Still_Normandy
Two dead goats and prayers to various gods
(Actually, it's a min/max tree that uses a heuristic algorithm to weed out
the "bad" moves on a given board. I think the min/max hurts more than it
helps)
++ If I had it to do all over - here's what I would try ....
Three dead goats and prayers to various gods
(OR...just drop the min/max [use a more optimistic search tree algorithm] and
only look two or three moves ahead)
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
* Colorado Springs, Colorado, USA
* Read (SF/fantasy), computer games (play/design), program (POTM/BeOS),
compose (bad music), model (CSG and spline based raytracing), sleep (in bed)
* budding C++ guru
* I hid it so well, I can't remember :-)
++ What is the URL of your homepage? http://www.be.com
No homepage, but check out BeOS at www.be.com (great operating system!)
also - www.rhino3d.com (awesome spline modeler)
www.povray.ord (good [free] ray-tracer)
_________________________________________________________
PROH-GRAM was seeded number 63
_________________________________________________________
Sorry ... No questionairre was returned for PROH-GRAM
_________________________________________________________
hup_mat was seeded number 64
_________________________________________________________
=================
hup_mat submitted by Mathijs Vogelzang at m_v-at-dds.nl
=================
++ Please summarize the strategy used by hup_mat
Pretty basic minimax with alphabeta pruning with one small twist:
The number of look-ahead moves in increased while there's still time
and the final score of a move is Score + (Score with 1 less
lookahead)/10 + (Score with 2 less lookahead)/100 + (Score with 3
less lookahead)/1000, etc.
I think this makes the program perform better because the chance that
the program will choose a move that turns out to be very bad, but not
within the 'horizon' of the search, is lower.
++ If I had it to do all over - here's what I would try ....
Mainly speeding up the program, so it can do more plys. Maybe
implement one of those new MTD(f) algorithms.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Groningen, Netherlands, and I'm a medicine / physics student.
For fun: programming contests, tennis, music.
_________________________________________________________
Pah_Tumbug was seeded number 65
_________________________________________________________
=================
Pah!-Tumbug! submitted by Mr. e-Scrooge at RAshenfelter@submarinesystems.com
=================
++ Please summarize the strategy used by Pah!-Tumbug!
The heart of the program is a position evaluation routine. This computes
a measure of the desirability of making a move at a given blank space on the
board. This is based on the following components: position (as in chess, a
knight on the rim is dim), two different measures of the usable space around
the given position, and a measure of the potential score if a move is made
at that position. Separate measures of these quantities are computed from
the point of view of "X" and "O". These are all combined using weights that
were determined quite a while ago and probably should have been
reconsidered.
Originally, I weighted defense greater than offense, but when Fred published
his final rules, with an excessive advantage for total points as opposed to
point difference, I weighted them equally. This also simplifies subsequent
processing as each available space is equally desirable to "X" and "O". If
the position is blocked, i.e. neither player can gain any score by playing
there, that is also detected.
The Pah-Tumbug! program that scored 466 against Systest from week 4 on
used nothing more than an earlier version of the position evaluator. All the
available spaces were evaluated and the move was made at the position with
the highest evaluation.
Next the position evaluator was enhanced resulting in the present version.
The resulting program beat the previous one on almost all boards, but I
didn't bother to enter it.
My next program used this procedure repetitively to evaluate each possible
move by playing alternately "X" and "O" until the board was played out. Then
the board was scored and the initial move which resulted in the highest score
was chosen. Not surprisingly, this program never lost a match to the one it
was derived from. I was about to enter it when I tested it against the
earlier entry and it usually lost! So now I had a cycle of three programs;
the second beat the first, the third beat the second, but the first beat the
third, and I couldn't say which one was best.
By now (April 1) it was time to bite the bullet and get to work on a mini-
max program. Because the position evaluation is rather large, I wanted to
avoid having to redo it at every level and so I put the values in a doubly-
linked, sorted list. Each time a tentative move is made, the updated list
is passed to the next level along with the updated board. It took what I
consider to be a lot of program code to process those lists. To avoid the
overhead of a multitude of subroutine calls, some of the code is duplicated
as many as six times. I hope this was all worth it--I didn't try making a
program without the lists to compare.
So here is how it all works. After inputting the board and figuring out
who is "X" and "O", all the available spaces are evaluated and the results
put in the level-0 list. Then a tentative move is made at each position in
the list in order of the presumed desirability. The board is updated by
placing my mark and the list is updated by removing the entry for that move
and by re-evaluating only those positions (in the same row or column) that
might have been affected by the move. The updated move and list are passed
to level 1 where only a certain number of moves (by my opponent) are examined
similarly and passed to level 2 (my move again). At each level, one fewer
move is examined until a level is reached where the number of moves to be
examined is zero. At this point, the partially-filled board is supposed to
be evaluated and the result passed back up to each level where the best or
worst (from my perspective) move, depending on whose turn it is at that level,
is chosen in the usual minimax fashion.
But I had trouble evaluating the partially-filled board. I thought I
would just compute the current score and account for the potential of the
unplayed spaces by using components of my position evaluator where the
difference between the evaluation for "X" and the evaluation for "O" is used
instead of the sum. It didn't seem to work. The resulting program performed
poorly against the previous ones. I tried tweaking the weight of the score
vs the weight of the blank space evaluations to no avail. Much debugging
convinced me that the program was doing what it was supposed to. What to
do?!?
I finally tried playing out the board as in my previous program and scoring
it only when it was filled. I don't know why, but this worked much better.
I don't like this procedure for two reasons: it surely burns a lot of CPU
time at the level where it hurts most, and my experience with the previous
program indicated that this procedure tunes the program to perform well
against similar algorithms at the expense of performance against different
algorithms. But I can't argue with success so this is what I used.
Now about time management. At level zero, the program attempts to examine
all possible moves (in the order of desirability). The number of moves at
level 1 is chosen so that it would ideally take about 20 seconds to complete
the computation, twice the allowed time. Of course the elapsed time is
monitored (first several levels only) and further move examinations are
curtailed when a time limit is exceeded. Thus only about half of the possible
moves are examined. I set my time limit at 9 seconds to leave some margin.
The number of moves examined at level 1 varies from 6 for a mostly empty
board to 9 for a nearly full board. Because of the coarseness of this control
and the rate at which it affects total execution time, less than half of the
moves of some boards are examined while for others the computation finishes
well short of the time limit.
One late (April 30) addition to the program is to kill blocked spaces.
Whenever the position evaluator detects a blocked position, that position is
removed from the list and the space on the board is replaced with "*" which
prevents it from being considered at subsequent levels. This was a lot more
code and I don't think it buys me much most of the time. But if Fred were to
use a board that had a lot of blocked and/or nearly blocked spaces, it could
be the winning edge.
The timing data for the final tweaks to the time management parameters
could not be obtained until after this final program addition was complete
and so this was done only in the last few hours before the deadline. The
final Pah!-Tumbug! entry was submitted only 20 minutes before midnight. I'll
have to admit that that's cutting it a bit close!
So, how's it doing? As I write this it, is the evening of May 2 and the
first four elimination rounds have been run. Pah!-Tumbug! got a really awful
seed of 65 out of 145, considering the quality of the program (my opinion,
of course). What did you do, Fred, use my previous program for the seeding?
The result is that after round 0 it is matched against only the best programs,
to the detriment of both. So far it has kicked the #14 and #2 seeds into the
losers bracket until getting sent there itself in round 3 by the #1 seed.
There it has kicked #7 out of contention and is preparing to take on #6. If
it survives, #2 will be done for unless Fred lets it off the hook because
it will be a repeat match. How will it end? You'll know before you read this.
++ If I had it to do all over - here's what I would try ....
Not much different! Here are a few possibilities:
* Optimization of width vs depth vs time in the minimax procedure.
* Get that partially-filled board evaluator working.
* Add a link to the list from the board position to the entry in the
list. This would require yet more code to process the lists, but
it should save some search time.
* More tweaking of the weights in the position evaluator.
* And I could probably come up with more components for the position
evaluator. To this end, I probably should have played some games
against my programs to assess their weaknesses rather than just
watching them play against each other. Would you believe that I
have never in my life played a single game of Pah-Tum!
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Highlands, New Jersey, U.S.A.
Bicycling, sailing, grow orchids, travel.
Electro-optical systems design (hardware, not software) for Tyco Submarine
Systems, Ltd. (Previously AT&T Submarine Systems, Inc., but sold a couple
of years ago.) Stay tuned for yet another name for the same company...
Hah!
++ Unwritten Rules of the POTM Contest:
(I added this category since this stuff doesn't fit in the above.)
During the progress of this POTM, I discovered the following:
* You CAN'T change the name of your program. For my first entry, I used
"Pah_Tumbug". Subsequently, I changed it to "Pah-Tumbug", "Pah-Tumbug!"
and "Pah!-Tumbug!", but I was stuck with "Pah_Tumbug" to the bitter end.
* But you CAN change your own name. Partway through, I changed to the
pseudonym "e-Scrooge". Fred added the "Mr." and since it sounded OK
to me, I didn't complain. But he addressed this questionnaire to just
"Mr." -- now that's going too far! ;<[
_________________________________________________________
pot-hum was seeded number 66
_________________________________________________________
=================
pot-hum submitted by Mikael Klasson at fluff-at-geocities.com
=================
++ Please summarize the strategy used by pot-hum
For each cell in the grid, and for each player, calculate how many
points one would get by placing a marker there. Also calculate the
amount of space available in all directions; favoring cells with
space available in many directions over cells with only one open
side.
Now sum the two scores for each cell and select the highest
scoring cell. If more than one cell has the same sum, select the
one that has more space available.
++ If I had it to do all over - here's what I would try ....
I would probably go with the above solution all over again; it was
simple to implement, and I don't have any better ideas atm.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
In a smallish town called Nyk=F6ping in Sweden. Do for fun? Think,
Read books, watch movies, try to go mountain walking once a year.
I currently program for a living, but I'm going to start studying
this autumn. Innermost secret you say... Well, I haven't been
told; it's secret.
++ What is the URL of your homepage? http://mklasson.cjb.net
_________________________________________________________
Peety was seeded number 67
_________________________________________________________
Sorry ... No questionairre was returned for Peety
_________________________________________________________
thumpa was seeded number 68
_________________________________________________________
=================
thumpa submitted by Dale Swift at dale.swift-at-btfinancialgroup.com
=================
++ Please summarize the strategy used by thumpa
Simple minmmax search with alpha-beta pruning straight out of the text book.
++ If I had it to do all over - here's what I would try ....
There are so many things to experiment with and just never enough time.
My rules for evaluating the board position were not great and the
weightings used simply guess work. I would have liked to have a
bigger pool of attributes to check and use some genetic
algorithms to find the best weights.
++ What is the URL of your homepage? http://www.unitedmedia.com/comics/dilbert/
_________________________________________________________
Tracery was seeded number 69
_________________________________________________________
=================
Tracery submitted by Igor Volkov at volkov-at-mzor.com
=================
++ Please summarize the strategy used by Tracery
For every square I try to evaluate the profit (it is a sum of profit of
player 1 and loss of player 2). I consider some standard patterns.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Belarus. I work at Software Engineering Dept., BSU.
_________________________________________________________
sift was seeded number 70
_________________________________________________________
Sorry ... No questionairre was returned for sift
_________________________________________________________
xDueLo was seeded number 71
_________________________________________________________
Sorry ... No questionairre was returned for xDueLo
_________________________________________________________
doh was seeded number 72
_________________________________________________________
=================
doh submitted by David Wales at david.wales-at-westgeo.com
=================
++ Please summarize the strategy used by doh
Initially - no look ahead, favour cells with potential high
scores for either player, favour the central cells. By fluke this
put doh on the top of the list for a few weeks, until I added
a more sensible approach - lookahead, minimax (width 4
depth 8).
++ If I had it to do all over - here's what I would try ....
studying harder, getting out of bed before lunchtime, imbibe less -
oh you mean in POTM? - look into game playing strategies more
deeply. Too little time in the end, and a crust to be earned.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
UK. Spend time with the children & still trying to learn Chinese.
Software Engineer with seismic exploration company.... err that's it.
_________________________________________________________
X was seeded number 73
_________________________________________________________
Sorry ... No questionairre was returned for X
_________________________________________________________
Dog_overtakes_Sandman was seeded number 74
_________________________________________________________
Sorry ... No questionairre was returned for Dog_overtakes_Sandman
_________________________________________________________
potm30IV was seeded number 75
_________________________________________________________
=================
potm30IV submitted by Damyan Ognyanoff at Damyan-at-rocketmail.com
=================
++ Please summarize the strategy used by potm30IV
It wasn't so wise.
1. Find best oponent moves
2. for each of them - calculate how much can 'advance'
from here (how long can be my line or column)
3. and finaly choose my best from his best
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Sofia - the capital city of Bulgaria. Work as
programmer for a small international softwate company
here in Sofia.
++ What is the URL of your homepage? http://hamgate.space.bas.bg
sorry - no homepage. but ...
this is a local Packet Radio to Internet Gateway :-)
my callsign is LZ5ZO and 'radio' is my second hobby
_________________________________________________________
rbg was seeded number 76
_________________________________________________________
=================
rbg submitted by Bernard Hatt at bmh-at-arkady.demon.co.uk
=================
++ Please summarize the strategy used by rbg
A simple recursive evaluation of all the possible moves, down
to a depth limited by time.
Static evaluation of the value of a position was made very
efficient by storing the board position in two arrays of
integers, one for rows, and one for columns. Each possible
state +,-,X,O has a two bit value, so the score for each
row/col could be found by looking up the 14 bit number in
a table.
As the evaluation recurses down, the score for the position
is calculated from the row/col which was changed and the previous
score rather than a complete evaluation.
There was some tuning of the evaluation to make the program prefer
some patterns eg. ".OXXXO." , would have a lower value (for X) than
"..XXX.." as it has less room for expansion.
The depth to search to is set from a table depending on the
number of moves remaining, this was set with a big safety margin.
The time to search to depth 'n' was recorded, and if there seemed
to be time, the search would be repeated to depth 'n+1'.
As on previous POTMs I resisted the temptation to make minor
tweaks for only small improvements, prefering to stay with the
simpler and more robust version.
++ If I had it to do all over - here's what I would try ....
I'm sure there is a clever solution looking for pre-calculated
patterns which could do better.
Some other opponents with different algorithms would have made
testing a version better but slower, several times I ended up
with the case where version A would beat version B, B would beat
C and C would beat A, which makes picking the best version
difficult.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I'm based in the UK about 25 miles to the NW of London.
_________________________________________________________
pahtty was seeded number 77
_________________________________________________________
Sorry ... No questionairre was returned for pahtty
_________________________________________________________
Invader was seeded number 78
_________________________________________________________
=================
Invader submitted by Carlos Valenzuela at cvmontuy-at-yahoo.com
=================
++ Please summarize the strategy used by Invader
It uses the minimax search procedure that uses a tree
with a max depth of 7 player movements.
For every movement "Invader" sorts the alternatives
using a fast evaluation function and it takes a
maximun of 12 alternatives for the next depth-level.
Invader almost don't use any multiplication or division
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I Live in Mexico, I make software for fun, I am a
Systems Proyect leader in Collectivemind, my address:
cvmontuy-at-yahoo.com
_________________________________________________________
pslmsngr was seeded number 79
_________________________________________________________
=================
pslmsngr submitted by Richard Green at pslmsngr-at-yahoo.com
=================
++ Please summarize the strategy used by pslmsngr
I made a score function, and scored each possible move that I
and my opponent could make, if the opponents score was higher
I blocked that move, if the highest score was zero I picked
adjacent moves, else I chose the highest score move.
++ If I had it to do all over - here's what I would try ....
I'd make it interactive so that I could play with the game and
learn the best moves, then apply it to the entry.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Pelham, NH; program; electronic technician; I used to program in Pascal.
++ What is the URL of your homepage? http://pages.about.com/pslmsngr/
_________________________________________________________
ePahTum was seeded number 80
_________________________________________________________
Sorry ... No questionairre was returned for ePahTum
_________________________________________________________
Pah-Tum_Noster was seeded number 81
_________________________________________________________
Sorry ... No questionairre was returned for Pah-Tum_Noster
_________________________________________________________
pahtumpotm was seeded number 82
_________________________________________________________
=================
pahtumpotm submitted by Greg Youngdahl at youngdahl-at-lucent.com
=================
++ Please summarize the strategy used by pahtumpotm
For each turn (each run of my program) I analyze each available
position on the board for three criteria. The first is score related.
I calculate my score, and find the square for the opponent that will net
them the most possible points (not looking to see if they will block me -
they won't be able to block my current move anyway) and my first criteria
is the resulting score. Second I calculate the maximum "span" for each
position. That means how many available squares exist in both the
horizontal and vertical dimensions that I could move into on subsequent
moves (I include unused spaces as well as spaces with my own marker in
them). The higher this number is the more opportunities I have to make
future (longer) strings of my marker. The third critera is a ranking I
came up with that favors positions near the middle of the board, assuming
that, as in chess, control of the center is advantageous (although I'm
Mot so sure how much advantage that is in this game). Each square has
a unique number with the lowest number being the center, and working out
from there. This is a tiebreaker for position choice, in case the other
two criteria (score and span) come out the same for the best squares.
I then sort the list of available positions according to these
criteria (first on best score, then span, finally closeness to center).
The position at the head of the list is the move I make.
++ If I had it to do all over - here's what I would try ....
Watching pahtumpotm play I can see a few cases where a better
strategy might have been a benefit under certain specific circumstances,
but for the general case, I'm hoping that my strategy is reasonably
robust. I suppose more than 2 move look ahead (my current move and my
opponent's next move) might be advantageous. I imagine there are more
aggressive players that will conquer me, but it has been kind of surprising
and fun to find myself in 5th place on the meaningless (?) weekly rankings
for the past few weeks ;-)
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Illinois, Guitar (mostly) + some keyboards and digital recording (DAW),
telecommunications software designer, its dark in here - no secrets
can escape.
++ What is the URL of your homepage? lydesign-at-interaccess.com
(my wife's page - my link should be up on it soon)
_________________________________________________________
the_PahTum_line was seeded number 83
_________________________________________________________
Sorry ... No questionairre was returned for the_PahTum_line
_________________________________________________________
XOX was seeded number 84
_________________________________________________________
Sorry ... No questionairre was returned for XOX
_________________________________________________________
A-THUMP was seeded number 85
_________________________________________________________
Sorry ... No questionairre was returned for A-THUMP
_________________________________________________________
3AKPECTKA was seeded number 86
_________________________________________________________
Sorry ... No questionairre was returned for 3AKPECTKA
_________________________________________________________
pah_rum_tum_tum was seeded number 87
_________________________________________________________
=================
pah_rum_tum_tum submitted by Mason Guy at mason.guy-at-intel.com
=================
++ Please summarize the strategy used by pah_rum_tum_tum
The program plays out the remainder of the game by assuming both players
will make either the most advantageous or most blocking move. The models
used for both the player and opponent are the same - i.e., the opponent is
assumed as capable as the player. Each possible move is evaluated for score
gain and blocking potential (stealing the opponents gain). The "benefit"
to the player is adjusted for move depth so that early score gains can have
more impact than later gains that may never come. The adjustment ratio is
actually non-linearly based on the number of moves previously made (i.e.,
how far into the game we are) and is set up so that during the first few
game plays, moves are based on a "deeper" strategy and near the game's end
only immediate gains count.
++ If I had it to do all over - here's what I would try ....
If I had the time, I'd like to learn and try some genetic populations that
would compete.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in the Silicon Valley and work for Intel as a performance analysis
engineer.
_________________________________________________________
Spaghetti was seeded number 88
_________________________________________________________
=================
Spaghetti submitted by Kai Hohman at mensch-at-midsouth.net
=================
++ Please summarize the strategy used by Spaghetti
I assigned a score to each empty square based on what was contained in
surrounding vertical and horizontal squares. Then chose the highest scoring
square.
++ If I had it to do all over - here's what I would try ....
Extensive testing to find out what the optimal depth of vertical and
horizontal squares to use to determine empty squares scores.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Tennesee. Computer games, reading. Student in computer science. Can't tell
because it wouldn't be a secret anymore..
_________________________________________________________
Graphitics was seeded number 89
_________________________________________________________
=================
Graphitics submitted by Janis Sermulins at Janis_Sermulins-at-swh-t.lv
=================
++ Please summarize the strategy used by Graphitics
Just min-max. First I apply it with depth 1, then depth 2 ... and so on
untill i run out of time an then I output the best move
according to the deepest min-max that has
been completed. Evaluation of board is based on "current score difference"
+ / - "score gained in best move by whoever can go".
++ If I had it to do all over - here's what I would try ....
More adaptive min-max and maybe more elaborate evaluation.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
1) Riga, Latvia.
2) hacking, programing
3) Just programming
++ What is the URL of your homepage? http://ikaruss.r1g.edu.lv/~janiss
_________________________________________________________
Huggs_n_Kisses was seeded number 90
_________________________________________________________
=================
Huggs_n_Kisses submitted by Andrew Gauld at andrew.gauld-at-att.com
=================
++ Please summarize the strategy used by Huggs_n_Kisses
Assign a score to each position based on my score if I take the position and
lose all positions in the same row and column, I take the position and every
position in the same row and column, and likewise for my opponent taking the
position and all or none of the positions in the same row and column.
++ If I had it to do all over - here's what I would try ....
better scorer and limited recursive descent. Learn more about how computer
chess programs work as that seems like a similar problem.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I'm raising a 2 year old in Middletown NJ, U.S.A. and if I told you my innermost
secret, it wouldn't be a secret anymore.
++ What is the URL of your homepage? http://home.att.net/~agauld
_________________________________________________________
Cheater was seeded number 91
_________________________________________________________
Sorry ... No questionairre was returned for Cheater
_________________________________________________________
rolaids was seeded number 92
_________________________________________________________
=================
rolaids submitted by Peter Vasiliauskas at pete-at-magneticpole.com
=================
++ Please summarize the strategy used by rolaids
rolaids is a simple MiniMax game player, using alpha-beta cutoffs. Due to
time constraints, I only was able to have it search 4 levels deep. The
evaluation function wasn't terribly special, it just valued higher when near
a friendly piece or an opponent's piece, and less friendly towards the walls
and obstacles.
++ If I had it to do all over - here's what I would try ....
I would definitely try to implement the time-based minimax algorithm that I
attempted, but decided that I ought to work on school work instead.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I currently reside in Dayton, OH as a computer science student at the
University of Dayton. I graduate in 5 days, and have accepted a job with
Harris of Cincinnati as a software engineer. I have no innermost secrets.
At least, none to share.
++ What is the URL of your homepage? http://www.magneticpole.com/
_________________________________________________________
simple_alg was seeded number 93
_________________________________________________________
Sorry ... No questionairre was returned for simple_alg
_________________________________________________________
MyOpia was seeded number 94
_________________________________________________________
=================
MyOpia submitted by POTM Junkie at POTM_Junkie-at-yahoo.com
=================
++ Please summarize the strategy used by MyOpia
How do I do it?! I don't know! I just do it!
++ If I had it to do all over - here's what I would try ....
Just say no! When I was a young programmer some of my friends told me about
POTM. They used peer pressure to get me to try it the first couple of times.
After that I was hooked. I've been addicted for about three years now. I
neglect my family and work. My kids talk to me, but I can't hear them. They see
me just sitting there with a dazed look. I'm totally unaware of the rest of the
world. All there is is POTM. Between POTMs, I lay in bed at night thinking
about the next POTM. Sometimes I've even lied to get more POTM - I've sent in
extra programs under bogus names.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Live: Colorado Springs, Colorado, USA
Fun: Backpacking, Volleyball, Break perfectly good automobiles
under the guise of "fixing".
Work: Java.
Innermost Secret: Bozo
++ What is the URL of your homepage? http://www.geocities.com/pbanta
_________________________________________________________
Neuro_blaster was seeded number 95
_________________________________________________________
=================
Neuro_blaster submitted by Jaco Cronje at s9805027-at-student.up.ac.za
=================
++ Please summarize the strategy used by Neuro_blaster
I Trained a Neural Network(NN) with a Genetic Algorithm.
Then used the NN to play the game !!
Simply evaluate each possible move with the NN and select
the one with the highest outcome.
Inputs for NN: (My - my program, His - the oppenent)
* My score at the moment
* His score at the moment
* What score I gain if I take this move
* What score He could have gain if he placed his X/O on the same spot
* If I make this move, what is the least total score I can get in 2 moves
* If I make this move, what is the best/least I can get in 2 moves
* If I make this move, what is His best total score He can get in 2.
* If I make this move, what is His best score He can get in 2.
* Total of cells empty up/down/left/right to this move.
This NN played ok, but not that good.
My NN trained against a program which strategy works almost
like my brothers strategy. (Henco Cronje).
His program played fairly good, so I decided to train against his
type of strategy.
++ If I had it to do all over - here's what I would try ....
Spend more time on figuring out a cool new method.
Figure out a better way to play games than Alpha-Beta Search
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Live : South-Africa
Fun : Programming contests, writing programs, games, ...
Work : Computer Science student at the University of Pretoria (3rd year now)
Secrets : We screw up in the ACM - ICPC in Orlando, but will be back in
2001 with a lot more experience.
++ What is the URL of your homepage?
http://members.tripod.com/~POTM/
and other programming contestpages... which I won't list here,
because then all of you will enter and it will be more difficult
for me to win them !!!
_________________________________________________________
Pahtumerator was seeded number 96
_________________________________________________________
Sorry ... No questionairre was returned for Pahtumerator
_________________________________________________________
too_slow was seeded number 97
_________________________________________________________
Sorry ... No questionairre was returned for too_slow
_________________________________________________________
harry_heuristic was seeded number 98
_________________________________________________________
Sorry ... No questionairre was returned for harry_heuristic
_________________________________________________________
Something_Clever was seeded number 99
_________________________________________________________
=================
Something_Clever submitted by Gabriel Gambetta at ggambett-at-ucu.edu.uy
=================
++ Please summarize the strategy used by Something_Clever
Well... it's quite simple. It computes the score difference
for each position if the other program puts its mark here.
It then chooses the one that gives less advantage.
It may sound stupid, but I ran a little tournament here
and it beat all other algorithms I tried, even deep recursion.
++ If I had it to do all over - here's what I would try ....
Not getting a girlfriend. I stopped thinking about this
contest in january, I think. I was really busy with
my (then recently acquired) girlfriend. We're together
for over 4 months now and she's the woman of my life,
so I guess the choice was right :) It's nothing personal,
Fred, but you just can't compete with her ;)
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
- Montevideo, capital city of Uruguay, somewhere lost in
South America (between Argentina and Brazil. And no, it's not
PARAguay, its URUguay)
- Going out with girlfriend, friends, soccer, role playing games, programming
- Programming
- I really don't know...
++ What is the URL of your homepage? http://ggambett.cjb.net
If it doesn't work (the server is not quite stable) go to
http://members.tripod.com/~gabriel666
Also check
http://uruplanet.cjb.net
_________________________________________________________
Mudpack was seeded number 100
_________________________________________________________
Sorry ... No questionairre was returned for Mudpack
_________________________________________________________
play_with_me was seeded number 101
_________________________________________________________
=================
play_with_me submitted by Dave Lynch at dflynch-at-att.com
=================
++ Please summarize the strategy used by play_with_me
For each available space on the board, I computed a score equal to the
increase in points if I moved there plus 0.3 times the increase in points if
my opponent moved there. (In other words, I gave myself a discounted score
for blocking my opponent). I then chose the space with the highest score.
As a tie-breaker, I chose the space with the highest potential increase in
points (by looking at the number of empty spaces). As a second tie-breaker,
I looked at the number of adjacent empty spaces.
++ If I had it to do all over - here's what I would try ....
It would have been nice to examine more sophisticated strategies, but time
is scarce. So, if I had it to do all over, I probably wouldn't have done
anything differently.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Freehold, New Jersey, with my wife and two sons. Among other
things, I enjoy reading, biking, crossword puzzles, running, music, and
playing softball. Oh, and I also spend 40 hours or so a week thinking
about network design issues for AT&T.
_________________________________________________________
Fart_tum was seeded number 102
_________________________________________________________
Sorry ... No questionairre was returned for Fart_tum
_________________________________________________________
compustud was seeded number 103
_________________________________________________________
Sorry ... No questionairre was returned for compustud
_________________________________________________________
jpt was seeded number 104
_________________________________________________________
=================
jpt submitted by Joe Smith at smithj-at-genrad.com
=================
++ Please summarize the strategy used by jpt
Pretty simple. A "which free position gives the highest relative score"
algorithm is used by both sides in turn to give a varying degree of
look-ahead (the fewer positions remaining, the further it can look ahead).
The scores for checking moves is a modified version of the game scores (to
give credit for making lines of 2 where there isn't a better move
available). It has been tuned for winning the game rather than a high score
(so will block the opponent if that gives the best advantage, even where a
row could be extended for a higher immediate score).
++ If I had it to do all over - here's what I would try ....
Give up work and hobbies to allow plenty of thinking time!
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Stockport, UK. Ride motorbikes. Engineer software. If I told, it wouldn't be
a secret any longer!
++ What is the URL of your homepage? http://www.dilbert.com
Why, it has to be www.dilbert.com, of course!
_________________________________________________________
pahtum_of_the_barrel was seeded number 105
_________________________________________________________
Sorry ... No questionairre was returned for pahtum_of_the_barrel
_________________________________________________________
Spoiler was seeded number 106
_________________________________________________________
Sorry ... No questionairre was returned for Spoiler
_________________________________________________________
CONSTRICTOR was seeded number 107
_________________________________________________________
=================
CONSTRICTOR submitted by Mike Sweeney at mike.sweeney-at-dsto.defence.gov.au
=================
++ Please summarize the strategy used by CONSTRICTOR
The program was designed to be small, simple, and be developed quickly
(2 hours to understand problem + 1 hour to code and test).
It consists of 39 lines of simple statements.
It was submitted 29 Jan 2000 5:56pm East Australian Time.
The name derives from the "squashing" of program size and using Python
language. Program strategy:
- find best move for self and opponent.
- if opponent would score better next turn, block opponent.
- otherwise take best move for me.
NOTE:
- no "game tree" structure.
- no look ahead.
- very simple algorithm.
Code logic:
- read in grid
- calc scores and counts for X,O,empty, and NotAvailable
- find out if we are X or O
- make a list of empty spaces
- calculate move with best points increase for X and O
- if my move is better, move to my best move
- if opponents move is much better, block opponent
- otherwise (if opponents move is a little better) 50% chance of block
- output modified board
++ If I had it to do all over - here's what I would try ....
If I had a day to spare, I would build a game tree analyser.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Canberra (the capital), Australia.
Write simple POTM solutions :-)
Defence research engineer.
Thats classified (nice try though).
++ What is the URL of your homepage?
Behind a firewall. Anything about python, linux, XML, web technology.
_________________________________________________________
muthappy was seeded number 108
_________________________________________________________
=================
muthappy submitted by Ted Heeren at heeren-at-paradyne.com
=================
++ Please summarize the strategy used by muthappy
I started by trying to pick the best move based on:
1. close to center of board.
2. close to my mark.
3. farthest from opponents mark.
4. best score.
I was getting such lousy scores that I changed into a blocker and evaluated and picked the position based on the opponent. I eventually found my bug but continued to be a blocker.
++ If I had it to do all over - here's what I would try ....
Spend more time. I really just got to the point of making it work.
I had planned to perform forward searches based on different combinations of the opponent and myself toggling between goals of high scores and blocking.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Florida.
Kayak, fish, hike.
Program embedded communication devices.
I use windose at home.
_________________________________________________________
Pananthara was seeded number 109
_________________________________________________________
=================
Pananthara submitted by Prasanna Anantha-Raju at prasanna-at-uta.edu
=================
++ Please summarize the strategy used by Pananthara
This is more a defensive pahtum player. It finds solution that scores the most.
Next finds out what would the next player do... if scores more then he will back
track and protect that more.
++ If I had it to do all over - here's what I would try ....
I would come up with a better pathum that also works on offensive decisions.
Started very late...as late as the last 2 weeks.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
LIVE: Arlington, Texas.
FUN: Play computer games, racket ball, basketball, camping, programming,
music..just the hearing part of it.
WORK: Study at university of texas, arlington. Doing research in real-time
systems. Working as a co-op is a telecom based company...and looking of
full-time jobs ( Now this also my work!!!)
INNERMOST SECRET: Its too deep for me to find out.
++ What is the URL of your homepage? http://cseweb.uta.edu/~anantha
http://welcome.to/Prasanna
_________________________________________________________
PadMyTummy was seeded number 110
_________________________________________________________
Sorry ... No questionairre was returned for PadMyTummy
_________________________________________________________
GrandMaster_of_Pahtum was seeded number 111
_________________________________________________________
=================
GrandMaster_of_Pahtum submitted by Roshan Revankar at rrevankar-at-hotmail.com
=================
++ Please summarize the strategy used by GrandMaster_of_Pahtum
I did not have much time( I had my exams coming up ) to use any AI strategy.
I just calculated the best possible position for me and the opponent at each
move.
>++ If I had it to do all over - here's what I would try ....>
I would definitely use some AI.
>++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Bangalore, India. I am a student of Mechanical Engineering. I
enjoy surfing the net, reading fiction and watching Tennis!
>++ What is the URL of your homepage? http://www.geocities.com/rosh98
_________________________________________________________
Pah-tum_by_Hippo was seeded number 112
_________________________________________________________
=================
Pah-tum_by_Hippo submitted by Vladan Majerech at maj-at-kti.mff.cuni.cz
=================
++ Please summarize the strategy used by Pah-tum_by_Hippo
I think, a lot of theory presented here is well known, so I am sorry for
borring you (and for poor english, too).
Alpha Beta search is a search through the game tree, where the branches
with results less then $\alpha$ or greater then $\beta$ are cuted off.
Negascout is a version of Alpha Beta search, which hopes that the moves
tested are sorted in the best possible order, so after result from the
fist branch is known, it temporary sets $\beta=result+1$. This allows
much more cutoffs during testing the conjecture that we have the correct
result. If the test fails, we should search the tree again with $\alpha$
set to new result and with the original $\beta$ to find new adept for
the conjecture.
We have limited time so there is no possibility to search all the tree.
Therefore we define some static function and search only the top $l$
levels of the tree, and use static evaluation as expected result. If the
search for given $l$ is finished, we reorder moves according obtained
results, increase $l$ and search again (deepening).
FHRNegascout tries to speed up branches during conjecture testing. If
the static evaluation matches the conjecture, we reduce depth of the
subtree searched.
I found that there was a problem with FHRNegascout during game endings,
where branches with reduced depth gives better results then without
depth reduction, therefore new adept for the conjecture may by off the
$(\alpha,\beta)$ where it is searched. Therefore in that case the third
search is needed. I hope it happens mainly in the game endings, where
there is enough time, and the narrow 2nd search in the game begining is
prefered.
Hashing the best moves for positions is good startegy, it speeds up
searches, since we almost start with the conjecture which holds. We hash
with the best move also the search depth and flag indicating whether it
was exact result, upper or lower bound, which allows us not to research
it at all or at least change the alpha or beta bound.
Now I see a bug in the strategy. Hashing during conjecture testing
should use smaller depth due to possible FHR. Results obtained from hash
may be wrong!!!
This was the theoretical base. For the Pah-tum I chose following static
function:
I solve one dimensional games for all possible filling of 7 positions in
the row. I solve it for the cases when starting player plays twice and
the game continues normally and for normal game, too. Static evaluation
of the 7positions is 31 times result for the normal game when X starts +
31 times when O starts + 1 times X starts with one additional starting
move + 1 times O starts with one additional starting move. (This
evaluation is done during initialisation process, using results found so
far not to search under some possition twice.)
The static function is the sum for all rows and columns of their static
evaluations.
(We maintain static evaluation with each position during the search
process, since it's update needs only 4table lookups, while computation
from scratch needs 14lookups.)
I do FHR only on even levels (and by 2) since the static function is
allmost stable after moves of the same player, but it is changed much by
a single move. Also deepening uses levels 1,3,5,7,9,... for the same
reason.
I tried some heuristics to find the correct conjecture as fast as
possible using the special order of moves.
We maintain 'countermoves' using the following strategy:
Whenever cutoff apears for $i$-th move, we replace global countermove
for previous move by move which forces cutoff, we also replace local
countermove for level $i$ and previous move by the same move.
The moves are tessted in the following order: at first I try move from
the hash (if there is), after it I try the best local countermove (if
there is), global countermove (if there is) follows and all possible
moves finishes it.
Moves are resorted after search for a level $l$ is finished according
the values obtained at the top level during the search (these values are
only upper bounds for branches where conjecture is only tested).
I`ve tried to speeded up search by reducing the size of the list of
tested moves. It wasn't good idea, since moves which are not good as a
starting move are often very good countermoves.
Therefore I use this reduction only during conjecture testing and only
for few starting moves for a level.
(I hope the hash will store the countermoves which are not good first
moves).
I use two lists of moves ... all moves and reduced list where are all or
first at least $l$ moves from the first list.
This speeds the computation for low $l$ rapidly.
I use SIGALRM and alarm(9) to finish computation in time.
I use separate hashes for first move, second one, ... . The first 4
hashes have special hashing strategy.
The 'hash for 0th move' is the variable bestmove.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live near Prague (Capital of the Czech republic ... I hope the
republic from which the best Ice Hockey players come.)
Yes I've did it for fun. It took much more time I`ve expected.
++ What is the URL of your homepage? www.kti.mff.cuni.cz/~maj
But I am very lazy in updateing it and so far it is in Czech language
only. May be interest from POTM side will force me to update it.
_________________________________________________________
munkleBall was seeded number 113
_________________________________________________________
================
munkleBall submitted by MadDog Bob at szinck-at-unixcosc.grayson.edu
=================
++ Please summarize the strategy used by munkleBall
munkleBall will go through the file and assign weights to every square.
It would go to a square, look at how many X's in a row could be
made, or O's in a row could be blocked. It weighted them like that
with the highest number of X's in a row getting the highest weight
Then it would recursively make 4 more moves based solely on the
weights that would be reassigned after it moved (so it would play
as both X and O to determine the best move). It won't make the
last move as X in the lower right corner.
++ If I had it to do all over - here's what I would try ....
I'd want to try it in Perl, just cuz. I'd work on it longer, and
maybe make some "opening style" moves sort of like chess, where
it sets up a scenario or something.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Texas, near Lake Texoma. I work at a hardware store.
(I work outside and make sure the parking lot stays there and the
carts don't go anywhere) I like to play guitar, star wars RPG's,
basketball, softball, go to the lake, etc. Innermost secret...
I've got three arms. and twelve hands!
++ What is the URL of your homepage? http://www.tourtexas.com/plano/plano2eat.html
I don't have a homepage... I like http://www.tourtexas.com/plano/plano2eat.html
It tells you where almost every restaurant in Plano is.
_________________________________________________________
NoName was seeded number 114
_________________________________________________________
Sorry ... No questionairre was returned for NoName
_________________________________________________________
quilt was seeded number 115
_________________________________________________________
=========================
quilt submitted by Ram Ramachandran sramachandran-at-lucent.com
=========================
++ Please summarize the strategy used by quilt
As a first cut it was just to pick the most optimal available free
space - no look aheads. I sent only one version. I could not spend any
time on this at all because of job related items.
++ If I had it to do all over - here's what I would try ....
I would like to get a job that would give me some more time to work
on POTM...
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I am based in Naperville. I am part of the Autoplex International
Customer Tech Support organisation.
_________________________________________________________
Babylon_7 was seeded number 116
_________________________________________________________
=================
Babylon_7 submitted by Boris Bulayev at bbboris-at-rinet.ru
=================
++ Please summarize the strategy used by Babylon_7
Simple optimization of 3 parameters:
FreeLineLength, MyLineLength, EnemyLinePossibleScore
++ If I had it to do all over - here's what I would try ....
The same but with more accuracy
++ WHERE DO YOU LIVE?
Here :(
DO FOR FUN?
POTM
DO FOR WORK?
teach students (www.mesi.ru) and make
"statistical database on CD" software, (www.chat.ru/~cis)
INNERMOST SECRET?
top
++ What is the URL of your homepage? http://www.rinet.ru/~bbboris
_________________________________________________________
grandPAH was seeded number 117
_________________________________________________________
=================
grandPAH submitted by Travis Pulley at travis-at-pulley.org
=================
++ Please summarize the strategy used by grandPAH
Buy low. Sell high. Vague idea of what low and high are.
++ If I had it to do all over - here's what I would try ....
Submitting more than one entry after the second day of the contest
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
- Portland, OR,us.
- Mountain Bike Pilot (Why stay on the ground when you can fly?)
- I work on computers all day. I never cease to be amazed by how much
money ppl give me for what I do. http://aigraphics.com
- I once did a stunt on the set of xena, warrior princess and one of my
fake boobs fell out and injured an intern.
++ What is the URL of your homepage? http://travis.pulley.org
_________________________________________________________
aleXANDOr was seeded number 118
_________________________________________________________
Sorry ... No questionairre was returned for aleXANDOr
_________________________________________________________
HugsAndKisses was seeded number 119
_________________________________________________________
=================
HugsAndKisses submitted by Mike Buchmann at mbuchmann-at-mailroom.com
=================
++ Please summarize the strategy used by HugsAndKisses
The strategy I used was very simple... Give each square a score,
highest score gets the x or o. If a tie, pick a random number
and go that square. The score is based on my ability to get points
by moving to that location + my opponent ability to not get points
by moving to that location. Came up with the program on the first
night and made one change to it since than.
++ If I had it to do all over - here's what I would try ....
I wish I could have spent more time thinking about the problem. I
completed the program one night and never really went back to it.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in a small town in Northwest Wisconsin. I have 4 kids 6 and
under so that takes care of most of my fun. I am starting my own
web business called HolidayLabels.com which prints return address
labels with a holiday or special occasion theme.
++ What is the URL of your homepage? http://www.HolidayLabels.com
-- opening June 1st!
_________________________________________________________
CRACKLER was seeded number 120
_________________________________________________________
=================
CRACKLER submitted by Guy Oliver at guy_oliver-at-yahoo.com
=================
++ Please summarize the strategy used by CRACKLER
alpha-beta tree pruning mini-max algorithim (i dont remember if
the one I submitted had the negascout code in it or not
++ If I had it to do all over - here's what I would try ....
I didnt get around to adding memory, so it dont think to deep,
and it played real bad aginst the test player, so I dont think it
will win, but it was fun to implement. I also never came up with
good scoring rules for the game. I need to be able to tell when
one pos is better than another, etc, and i didnt really have any
good ideas.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
columbus ohio, usa, fun = computer, work = computer, secret =
computer.
++ What is the URL of your homepage? http://www.geocities.com/guy_oliver
_________________________________________________________
Love_Me_Do was seeded number 121
_________________________________________________________
Sorry ... No questionairre was returned for Love_Me_Do
_________________________________________________________
rimshot was seeded number 122
_________________________________________________________
=================
rimshot submitted by Brian Raiter at breadbox-at-muppetlabs.com
=================
++ Please summarize the strategy used by rimshot
Nothing in particular. Rimshot was written to see how far I could get
on the POTM in one night. Haven't had time to revisit it.
++ If I had it to do all over - here's what I would try ....
What I really wanted to write was a spoiler entry -- one that would
certainly lose, but would do nothing but try to lower everyone else's
score.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Seattle and I program computers.
_________________________________________________________
Paranoid-Pahtum-Player was seeded number 123
_________________________________________________________
Sorry ... No questionairre was returned for Paranoid-Pahtum-Player
_________________________________________________________
Pah-Dumb was seeded number 124
_________________________________________________________
=================
Pah-Dumb submitted by Graham McDermott at grahammc-at-sqf.hp.com
=================
++ Please summarize the strategy used by Pah-Dumb
Fairly simple - calculate the space with the most points
available and the space which the opponent has the best
score available
Play the piece which gives greatest advantage or greatest spoiling
but it doesnt take into account how may I've scored or my opponent
has scored. It was a pretty dumb player and there were loads of
improvements I had planned, but decided to do them incrementally as
I've entered POTMs before where I went for the all singing all dancing
player and ran out of time due to work & family commitments. The other
factor was that it was written (badly) in shell and much more work
and it would have ran over the 10 second limit (it was at about 8 or
9 seconds on my workstation).
I dont see it getting further than one or two rounds.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Currently homeless! In between house moving from Southern England to
near Edinburgh in Scotland (back home).
For fun I look after my newly born son (Daniel 6 months).
Doesnt seem to be as much time for much else funnily enough.
I've worked in Telecoms for about 10 years in various
companies and with various protocols.
Well my innermost secret would hardly be a secret any more
if I told you.
++ What is the URL of your homepage? http://www.dilbert.com
_________________________________________________________
tie was seeded number 125
_________________________________________________________
=================
tie submitted by Aivars Zogla at uvsk-at-fix.lv
=================
++ Please summarize the strategy used by tie
Play the spot with maximum number of friendly neighbours. Sorry...
++ If I had it to do all over - here's what I would try ....
Perhaps, would find some strategy.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
No change. Ugale, 40 km from Ventspils (could be on some map) LATVIA.
In meantime - organize contest in informatics and mathematics for
teams (high-school students),
http://alpha.fix.lv/~ugskola (Sorry, no english for this year.)
++ What is the URL of your homepage? http://acm.fi.uva.es
Above. Favorite? Excellent idea - http://acm.fi.uva.es
_________________________________________________________
gut_feeling was seeded number 126
_________________________________________________________
Sorry ... No questionairre was returned for gut_feeling
_________________________________________________________
MagicMarker was seeded number 127
_________________________________________________________
Sorry ... No questionairre was returned for MagicMarker
_________________________________________________________
playing_pahtum was seeded number 128
_________________________________________________________
Sorry ... No questionairre was returned for playing_pahtum
_________________________________________________________
takeshi was seeded number 129
_________________________________________________________
=================
takeshi submitted by Stefan Foerster at Foerster-at-a-city.de
=================
++ Please summarize the strategy used by takeshi
'takeshi' counts the number of neighboring free and
occupied cells (each for "X" and "O") for every
free position on the board. Each of these four
numbers 'takeshi' gets a score assigned (positive or negative),
which 'takeshi' adds up. 'takeshi' then chooses the
position with the highest total score. The score table
was created by a separate program using a genetic algorithm
(about 2 million simulation runs).
++ If I had it to do all over - here's what I would try ....
I would perhaps try a combination of the above strategy
and some simple branch and bound type algorithm.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Augsburg, Germany. My biography and some other
info about my work and hobbies can be found on my web site
http://home.a-city.de/stefan.foerster.
Btw, the most important info is that I'll get married
tomorrow (Apr 28th 2000)!!!!
++ What is the URL of your homepage? http://home.a-city.de/stefan.foerster
My wifes' commercial web site (which I am webmaster of, too):
http://www.francall.com
_________________________________________________________
The_Best_Defense was seeded number 130
_________________________________________________________
=================
The_Best_Defense (is a good offense) submitted
by Paul Banta at pbanta-at-yahoo.com
=================
++ Please summarize the strategy used by The_Best_Defense
A formula for calculating the relative merit of choosing each of the available
squares. Higher numbers are given for extending runs and blocking opponents. No
look-ahead.
++ If I had it to do all over - here's what I would try ....
Spend more time looking at a good ranking strategy. I think that choosing or
not choosing any particular square affects only the other squares (and score)
in that row and column. There should be an efficient and good way to rank a
square by only looking at the other squares in that row and column.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Live: Colorado Springs, Colorado, USA.
Fun: Backpacking, Volleyball, Breaking perfectly good automobiles under the
guise of "fixing".
Work: Java - an infinitely better OO language than C++.
Secret: Bozo.
++ What is the URL of your homepage? http://www.geocities.com/pbanta
_________________________________________________________
eRaZOr was seeded number 131
_________________________________________________________
Sorry ... No questionairre was returned for eRaZOr
_________________________________________________________
chuck was seeded number 132
_________________________________________________________
=================
chuck submitted by Rick Bischoff at beckett-at-cs.csoft.net
=================
++ Please summarize the strategy used by chuck
Chuck uses a very advanced genetic algorithm, coupled with a nine layer
neural network that manipulates bits and bytes in a such a way to allow
me to lose consistantly without ever having to say, "I'm Sorry, I
suck."
Actually, a full course load of engineering classes made me not spend any
time on "chuck". He actually just places his marker in the first place
possible.
++ If I had it to do all over - here's what I would try ....
Spending more than an hour on it ! :D
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Near Toledo, Ohio, in michigan. I don't have fun. I work at a kitchen
thirty hours a week to pay for gas, car, insuarance. My innermost secret
is....... Um... Well, nevermind about that.
_________________________________________________________
PahTumMeister was seeded number 133
_________________________________________________________
Sorry ... No questionairre was returned for PahTumMeister
_________________________________________________________
Frustahtum was seeded number 134
_________________________________________________________
=================
Frustahtum submitted by Doug McCreary at dark-at-ix.netcom.com
=================
++ Please summarize the strategy used by Frustahtum
Frustahtum uses a no look ahead strategy evaluating the board in
rows and columns, searching for the move that provides
a) maximum reduction in opponents future score
b) largest increase in potential future score
It uses a hard coded balance function to decide on a blend
of a & b.
I went with a no depth search to stimulate my thinking about
my job ... I was doing AI work for a reasonably well known
upcoming computer game at the time. In this context, performance
is everything. My player plays in significantly less than
a second on my system. (It should be less than 100k instructions
executed assuming reasonable compile results.)
++ If I had it to do all over - here's what I would try ....
If I had more time for it, I would consider a deeper search
along the same parameters ... a depth of probably 3 or 4 moves
would probably improve this algorithm significantly, and easily
run in 10 seconds.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in silicon valley, working for Blizzard Entertainment
on Diablo II. For fun I do assorted outdoors activity.
For innermost secret I can give out to this group I'm going to
have to go with: there is a cow level.
++ What is the URL of your homepage? http://www.blizzard.com/
I used to maintain a computer enthusiast page, but i've since
lost hosting, so I guess I'll recommend http://www.blizzard.com/
_________________________________________________________
fall_in was seeded number 135
_________________________________________________________
Sorry ... No questionairre was returned for fall_in
_________________________________________________________
mszalay was seeded number 136
_________________________________________________________
=================
mszalay submitted by Mate Szalay at s8655sza-at-hszk.bme.hu
=================
++ Please summarize the strategy used by mszalay
I determine a weght for each free square on the board. Then I choose the
square with the biggest weight. How weights are calculated:
Does not matter whoose turn it is. If a square is good for the 'O' then it
is god for the 'X' too. Thre are four directions: horisontal, vertical,
and the two diagonals. Each square gets a weight for each direction, then
these weights are summed. The weight for a direction:
The more of his marks the player collects in one row, the bigger the
weights are. I dcided to use exponential weights as the points are growing
exponentially.
++ If I had it to do all over - here's what I would try ....
Spend more time on it.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I am Hungarian. Now I stay in Finland for a semester. I study here, I did
the POTM just for fun.
++ What is the URL of your homepage? http://www.hut.fi/~mszalay
_________________________________________________________
pahtumonic was seeded number 137
_________________________________________________________
=================
pahtumonic submitted by Alex Greenbank at alexg-at-micromuse.com
=================
++ Please summarize the strategy used by pahtumonic
Look 2 ahead, quite simple but badly written. Didn't have time to improve it.
Also looks at which one the opposition would do if it were their move.
Weighting involved using random numbers that sort of worked. Little testing.
++ If I had it to do all over - here's what I would try ....
Breadth-first searching with a max depth of .
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Live: London, United Kingdom
Fun: Drink
Work: Computers
++ What is the URL of your homepage?
Fave (of course!): http://members.tripod.com/~POTM/CURRENT/problem.short.html
_________________________________________________________
Pahtumaniac was seeded number 138
_________________________________________________________
=================
Pahtumaniac submitted by Austin Green at austin-at-ww.co.nz
=================
++ Please summarize the strategy used by Pahtumaniac
Recursively evaluate positions until time runs out.
Tries to balance depth and breadth of recursion, so that
the more promising moves are investigated sooner and more
deeply. Biasses moves toward centre of board.
++ If I had it to do all over - here's what I would try ....
Having enough time to work on the problem. As usual, pressure
of 'real' work prevented my spending more than a few hours on
the POTM, with predictable results.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
New Zealand.
Eat, drink, and be merry.
Programmer.
Even more secret than outermost secret, which is secret.
++ What is the URL of your homepage?
No home page. You could try http://www.ww.co.nz/
which is my ISP's site.
_________________________________________________________
Under-tum was seeded number 139
_________________________________________________________
Sorry ... No questionairre was returned for Under-tum
_________________________________________________________
poh-tum was seeded number 140
_________________________________________________________
=================
poh-tum submitted by Darrell Wright at beached-at-lakeheadu.ca
=================
++ Please summarize the strategy used by poh-tum
To try and block the oponents move util the end and hope it does not catch on.
++ If I had it to do all over - here's what I would try ....
Adding some intelligence to determine what my opponent's strategy is and attack
its weaknesses. Or a table based strategy for predetermined finishing moves.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in Thunder Bay, Ontario, Canada. I like to run and program computers.
I am really an alien here to take over the world with my space alien powers.
(Sssh don't tell)
++ What is the URL of your homepage? http://simon.math.lakeheadu.ca/~dwright
_________________________________________________________
PhanTOM was seeded number 141
_________________________________________________________
Sorry ... No questionairre was returned for PhanTOM
_________________________________________________________
mu_Path was seeded number 142
_________________________________________________________
=================
mu_Path submitted by Jeff Phillips at jeffanddonna.mail-at-gte.net
=================
++ Please summarize the strategy used by mu_Path
I assign a value to each board position based on a simple set of heuristics:
**Number and type (X||O) of neighboring position contents
**Current sequence length vs. max possible sequence length
**Who's turn it is
**Others I can't remember now...
Based on these considerations and a few tweaking parameters, I simply choose
the highest value position as my move.
++ If I had it to do all over - here's what I would try ....
I would spend more than an hour or two to come up with a strategy. Given
the amount of processor time allowed, a much more exhaustive/elaborate
approach could have been used. If I had more time, I would have next looked
into explicitly preventing my opponent from getting more than two character
sequences. Of course, it's a fine balance between defense and offense...
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
Live: Seattle
Fun: No time for fun, too busy studying!!
Work: Computer engineering student at UW
Secret: The name of my program was a carefully chosen anagram selected from
Anagram Insanity (http://www.anagramfun.com)
++ What is the URL of your homepage? http://www.theonion.com
_________________________________________________________
de-pah-ted was seeded number 143
_________________________________________________________
=================
de-pah-ted submitted by Andrew Feren at feren-at-cabletron.com
=================
++ Please summarize the strategy used by de-pah-ted
My initial submission applied weights to various squares and
used a more or less static board evaluation to make choices.
In the case of equal weights a random choice was made. The
end result was a more or less random move generator.
Unfortunately, work got busy and the next revision never got
fully debugged.
++ If I had it to do all over - here's what I would try ....
The static evaluation turned out to be much more random than I
had hoped. I started implementing look ahead, but lost time
implementing data structures. I think the next time I would
use a language like C++ or Java that gives me a richer library
to draw from.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live on the New Hampshire seacoast.
For fun I spend time with my kids and work on renovating my
house. Programming is fun too even when disgused as work.
I design and implement device management applications and
other tools for Enterasys (a subsidiary of the company
formerly known as Cabletron)
++ What is the URL of your homepage? http://metalab.unc.edu/Dave/
I don't have a homepage, but http://metalab.unc.edu/Dave/ is
usually entertaining
_________________________________________________________
MATcHUP was seeded number 144
_________________________________________________________
=========================
MATcHUP submitted by Robert Morrison at RMorrison-at-hitex.de
=========================
++ Please summarize the strategy used by MATcHUP
MATcHUP does a simple ordering of the possible positions based
on how many in a
row are possible in the various directions and how many possible
win directions there
are. A square that has four empty neighbors is more important
than one that only has
1 empty neighbor. Then alpha-beta min-max is used to go to a
predetermined depth
that depends on the number of possible moves left. The
evaluation routine was very
basic (see below).
++ If I had it to do all over - here's what I would try ....
Unfortunately I never finished...
Our mail server started (and still does) breaking outgoing mails
at 72 characters which
prevented me from sending Fred my version 2 program. Also, I
never finished doing a
'real' evaluation routine as I had to go to the States on short
notice due to a death in the family.
++ WHERE DO YOU LIVE? DO FOR FUN? DO FOR WORK? INNERMOST SECRET?
I live in W=F6rth, Germany (near Karlsruhe [ SW of Frankfurt, W of
Stuttgart]).
For FUN I work with my computer writing programs, generating
ray-traced pictures
using POV-Ray, surfing the net, etc. I also play chess, read
science fiction books,
go to the movies and play tennis...
I am an electrical engineer (BEE, 1978, Georgia Institute of
Technology, Atlanta, GA)
that is working as a software application programmer for Hitex
Development Tools.
++ What is the URL of your homepage? http://www.povray.org
I currently don't have a homepage but my personal favorite
(other than POTM) is
http://www.povray.org
_________________________________________________________
Friend was seeded number 145
_________________________________________________________
Sorry ... No questionairre was returned for Friend