[geeks] Oh my god...

[Lionel Peterson]

--- Dave McGuire <mcguire at neurotica.com> wrote:
> On Friday, November 29, 2002, at 10:03 PM, Lionel Peterson wrote:
> > Algorithims + Data Structures = ___________
> >
> > Anyone? ;^)
> 
>    I sure hope this isn't a serious question. ;)

Heh, something in Joshuas post reminded me of the book... just having a
bit of fun...
 
> > My goal is to have a program that remembers every "human" move it
> > has encountered, but only "knows" what is a legal move and when
> > the game has been won. I want the strategy to come be learned from
> > the "human" opponent, not hard-coded in the logic.
> >
> > By using a relational DB (MySQL most likely), the idea is to
> > catalog positions and moves in a table for quick retrieval...
> > Oddly, I've spent *way* too much time working on the design,
> > and no time coding so far...

Well, my thought at the moment is to set up a database table with the
key set to each position on the board (each position will have a value
of "Opponent"("X"), Myself"("0"), or "Open"("?")), then there will be a
move column, that will have the number of one of the possible moves (an
"Open" space), and a counter.

After each "Opponent" move, the starting board status will be saved,
and the move by the "Opponent" will be used to determine which row to
retrieve from the DB, then the counter will be incremented by one.

For example, with an empty starting board, represented as such:

?|?|?   Index of b[] 1|2|3
-----                -----
?|?|?                4|5|6
-----                -----
?|?|?                7|8|9

The human will move to b[5], so the database update to store the human
move will look like:

update table.counter where table.board = '?????????' and table.move =
'5';

Then the compter will query the database with the new board and select
the move with the highest counter:

select table.move from table where table.board = '????X????'

and use the max() functionto find the most "popular" move for that
given board "state" - if none is found, randomly choose a move from the
open "?" spaces in the board.

Computer moves will not be counted.

Over time, it is expected that all possible board "states" will be
recorded (there aren't that many, since I am only saving the board
state after each Opponent move, not every move - there will only be
states inthe DB for one, three, five and eight boxes occupied, in
various configurations). After a critical mass of historical games have
been played, clear choices will emerge for every possible board state I
figure. When there is no clear choice (multiple moves with equal
counters for a given state), the rnd() function will be used...

>    Eh...Unless you're talking about a stateless program, say, 
> front-ended by a web server or whatever, I'd do something like a
> b-tree in memory.  Maybe checkpoint it to a database once in a
> while or something.

ANother project I've thought about before was a spell checker that has
a near infinite number of nodes in a tree, with each node having, say
27 pointers ('A' -> 'Z'), and a single datapoint at each node of "True"
or "False", indicating if this node terminates a valid word or not...
As a string is input, the tree is traversed, and when whitespace is
encountered, the data point is checked, and the "word" just parsed is
either marked as invalid or valid...

I came up with that one in discrete mathematics class about 17 years
ago...


=====
Lionel

"Nothing would please me more than being able to hire ten
programmers and deluge the hobby market with good software"
Bill Gates, in "An OpenLetter to Hobbyists" dated February 3, 1976
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com