2000.12.1
POSTER PROJECT STUFF!
README
Broke a bit early to go do all our work! Huzzah!
Chris will get us a paper!
Dr. Wolz will ("mach up interface for go fish" || "give up")
We have to do two abstracts for the poster project under 2 pages.
Suggested 2 topics are:
*Comparison of various tic tac toe implementations
What make this different from all the work that is out there?
emphasize that this was chosen for it's size:
we can control all the knowledge
we were able to map entire search tree and draw from that
generalities/conclusions
rule
tree
agent
*Go fish vs. tic tac toe as models of knowledge
What make this different from all the work that is out there?
attempt to generalize tic tac toe's model to a general model
which would fit something like go fish.
public vs private knowledge
perfect knowledge vs limited range vs imperfect
alternate representations of knowledge - Anthony's crazy statistics.
2000.11.17
WHAT DID WE DO THIS SEMESTER?
GO FISH - knowledge, probability (Go Antony)
TIC TAC TOE - rules, trees, generalities of board position (in relation to
devloping rules), rule based systems are faster but more difficult to design
minimax systems are slow and easier to design (save for the hueristic [which
makes all the difference])
CURRENT EVENTS - research papers, agents in tic tac toe/go fish
as far as resources - rules have design issues, minmax and agents have runtime
strategies - agressive vs defensive (this relates to real time strategy)
planning - single vs multi goal games
math theory - mapping knowledge, having representations for knowledge
"good guess" work programmer - tweaking weights
completeness of knowledge (see above)
modeling cognition vs making it work
"goodness" - is whats good for me necessarily bad for them
leaning, reflection, explanation
idea that a rule based system may break down in the fact that knowledge is
isolated (in each rule) and therefor lost - no reordering or the combination of
answers found in agents - agents can do interaction, this is based on having a
language to describe this (java, parallel prolog)
all you need is the toy! fries, burger, and drink are secondary (resources)
agents as nfa - gain us anything (maps entire "agent results" tree)
what have we learned in terms of conceptualizing ideas inherent in ai
2000.10.31
Discussed Go Fish in terms of Java implementation as far as objects and
knowledge. Decided to attempt Observer/Observable design.
Public vs. Private vs. Strategic Knowledge (vs. Something Else?)
Databases vs. LEARNING Databases
How can this information be applied to Rummy?
Learning algorithm vs. coding "knowledge"
Hardcoded rules vs. Databases vs. Minimax vs. Knowledge of Opponent's Knowledge
Combinations?
Intellegence vs. Seemingly intellegent agent
2000.10.27
Drew pictures to show object relations between Go Fish players and their
knowledge (see fig 1). Dr. Wolz came back from her conference with cool
insights from smart folk. Showed via Venn diagram discribing relation
between experiencial knowledge and mathmatical theory. There are points at
which math can not discribe experience. (See the diagram on the previous page.)
2000.10.20
Anthony's data management for Go Fish discussed
card value [ace, 1 , 2 ,...,kng]
player 0 [int, int, int,...,int]
1 [int, int, int,...,int]
2 [int, int, int,...,int]
The int will be the known position of cards.
Values greater than possible denote undefined.
CODE:
unknown = 52 - (num_of_paris * 2 + num_cards_in_my_hand + num_infinites)
remaining_i = 4 - (any_in_my_hand + any_known + any_in_pairs)
new_prob = (machine.possible_cards[player][i] * remaining_i) / unknown
if (new_prob > prob) {
prob = new_prob;
card = current_card;
}
void draw_card(player s) {
for (i, 1 to 13)
if (remain(i) >= 0)
machine.possible_cards[play][i]++;
}
// need to handle case where player has two cards in their hand
void drop_card (int index, Player p) throws what_the_&*#$%@_are_you_doing {
machine.possible_cards[p][index] = 0;
if (machine.possible_cards[p][index] = size_of(hand)
machine.possible_cards[p][index]--;
}
void update_knowledge(Player ask, Player called, int index) {
machine.possible_cards[ask][index] = INFINITY;
machine.possible_cards[called][index] = 0;
}
2000.10.17
1) STUFF TO DO FOR NEXT TIME WE MEET (WEEK N A HALF):
- get article to read from door box
- heuristic for go fish (minimax)
- fishs go fish
- wolz finish wolz stuff then send out to us
2) PERFECT MEMORY VS IMPERFECT MEMORY (IE LEVEL OF DIFFICULTY/CHEATING)
- cheating - looking at someone elses hand
3) HEURISTIC DISCUSSION
CONCEPTS
- cards in hand
- questions youve asked
- questions others have asked
- cards that have been paired
4) MINIMAX (n > 2)
STATE
- cards in hand (c)
- players to ask (p)
- top card in deck (t)
- possible actions which could be taken (a) = c * p
- a could then return a yes or no
- yes returns the card (one possibility)
- no returns t (many possibilities)
GOODNESS OF NEXT STATE TO DETERMINE MOVE BASED ON
- probibility of getting requested card from player
- probibility of getting requested card from deck
THIS MAY LEND ITSELF MORE TO A PROBIBILITY RULE BASED ALGORITHM
IDEA OF WHAT I KNOW VS WHAT I REVEAL
- asking for a card provides knowledge of a card you have
- keeping track of all public knowledge may lead to evaluation of
goodnesss
- set this vs what you have made public
- asking for card you dont have?
- question of perfect public knowledge ie do all players draw from a
common knowledge pool that is kept up to date (correctly of course)
- keeping track of probable location of cards
- idea of clue - keeping track of what is definitly known (he has this,
i have this, he does not have this, i do not have this) as well the
probabilities of players having/not having things
- mechanistically, we can implement minimax
- generation of next states could be tough
- pruning may help, what about probability
- step one, look at who has/doesnt have what cards
- step two, incorporate probabilities
nextStateGen(c, p, pk){
switch{
got it:
pair(pk); //all the pk parameter passing is just
didnt get it: //to show that public knowledge is
got it from deck: //always updated
pair(pk);
didnt get it from deck:
gotSomethingElse(pk):
otherPair(pk);
useless(pk);
}
}
5) MINIMAX VS RULES
RULES WORK WELL, BUT ARE A PAIN TO DEVELOP/CODE/READ
MINIMAX ALSO WORKS WELL, BUT DOES NOT HAVE THESE ISSUES
2000.10.6
Looked at Minimax.
Graig says it looks cool.
Played vs. Rules version of TicTacToe
They seem very equivalent.
Q: If removed WIN constants so that [x,x,-] was worht -2, not -16.
A: On look-ahead 2 it lost badly.
On look-ahead 5 and 4 it did better, but seemed more concerned with
it's own winning than with defending. It still lost.
We also noted that the H function returns the same value for some
boards. There should be added some function to "nudge" the H
function toward good moves.
Thoughts on 4x4 games and 3D games where purposed.
We tried playing tic tac toe on a 4x4 board with 3 players, X, O and * -> its
very cool. 3 in a row is still considered a win, and it seems that the first
player has a big advantage iff they take two center blocks.
---Early On---
At the IV coffee house (mixed college students, mixed majors, etc), we
asked people to play tic-tac-toe, and this is what we found. About 70% of
the people started with an X in the corner, about 15% started with an X in
the center, and about 15% started with an X in one of the outside middle
spots.
----------
Fish Rules:
1. Win
2. Block
3. Take a corner that leads to victory, or take another corner
4. Blah - any other square
----------
Other Rules (Computer goes first)
1st Move: Take a corner
2nd Move:
If O is NOT in the middle: Take a corner not adjacent to the O, and not
opposite of your first X.
If O is in the middle: Take the corner opposite your first move.
Subsequent Moves (prioritized as follows):
1. Win
2. Block
3. Take another corner
4. Anything else (draw situation)
----------
Rules for Computer Goes Second
----------
Sam's Rotational Observance... we can't explain in e-mail.
----------
Psychology brings us to a whole new level. A learning database, even for
tic-tac-toe, is extremely complicated. We think that we should start with
X in the corner. X starting in the center is only advantageous if we can
make use of a learning database.
-Chris, Graig, Sam
// The memory management on the PowerPC can be
// used to frighten small children.
// -Linus Torvalds