I'm looking through your sourceforge project and I have downloaded the example database stuff and the java files. Unfortunately I am not at all good with Java and I have given myself screwy eyes trying to figure out what two fields in the pente_move database do. What are the hash_key and rotation fields used for?
Just to let you know I am trying to work out an algorithm to play against the database ( as opposed to a full- fledge AI) which is a similar technique to the A.L.I.C.E. bot.
Posts:
1,032
Registered:
Dec 16, 2001
From:
Powell, OH
Age:
37 Home page
Re: Game database
Posted:
Oct 20, 2002, 3:07 PM
> I'm looking through your sourceforge project and I > have downloaded the example database stuff and the java > files. Unfortunately I am not at all good with Java > and I have given myself screwy eyes trying to figure > out what two fields in the pente_move database do. > What are the hask_key and rotation fields used for?
I don't remember the specifics of the database since I developed it quite a while ago. Basically each move in a game is associated with a hash_key. That hash_key is unique (or nearly unique, we never proved anything) for the whole sequence of moves up through that move (no different sequence of moves should have the same hash_key with the same number of moves in the game, captures etc). It is kind of a weird concept and takes a little getting used to. But basically it makes comparing a given set of moves (entered through the gui) with the database a very quick operation. You only have to calculate the hash_key for the entered moves and then search the database for that same hash_key and number of moves, etc.
The rotation field is used to store which way the games in the database were played, any game can be played exactly the same but rotated about the board in 1 of 8 rotations. We want to be able to search ALL rotations so the following scheme is used I think. All hash_key's in the database are stored with the moves converted to a "standard" rotation. Then the original rotation is also stored with the moves. When a search is performed, the entered moves are also converted to standard rotation, then the hash_key is generated and then the results are rotated back using the rotation field and the rotation used by the user. In this way a player searching with a position in say rotation 1 can match games played in rotation 3 and 5 for example, and the results are displayed with the same rotation used by the user. I think thats basically how it works, the details are all in the code.
> Just to let you know I am trying to work out an > algorithm to play against the database ( as opposed to > a full-fledge AI) which is a similar technique to the > A.L.I.C.E. bot.
Mark mmammel and I have talked about doing something like, at least consulting the database for possible moves, it is an interesting idea. I'm not sure playing 100% against the database would produce that good of an AI, considering all the crappy games in the databse
Okay that will help me immensely in reading the code. Having the outcome is much easier to discern the question in programming. I don't quite get it all but it's clearer so I'm sure I will get it.
> Mark mmammel and I have talked about doing something > like, at least consulting the database for possible > moves, it is an interesting idea. I'm not sure > playing 100% against the database would produce that > good of an AI, considering all the crappy games in the > database
True, there will be tons of crappy games in the database but that will serve as a negating dataset. In other words, it will eliminate options based on previous failures and that will be key in the creation of the positing dataset or the games which have moves for success. I would guess that for expert players, they would win more often than lose but as they play the database, the database will begin winning more often (diminishing options for the human player as opposed to increasing options for the database). Think of it this way:
Say we have 5 games in the database and they all had wins in 5 moves. Let us also assume that each move is represented as a unique character (A,B,C,D,E). The only other needed assumption is that the computer is looking for games with wins matching its own move pattern.
So Game 1 has moves of A,D,B,C,E and is a win for the player that placed A. Game 2: A,D,B,C,E win for player that placed A Game 3: A,D,B,E,C Game 4: D,B,E,C,A Game 5: B,E,A,C,D
So that the computer is now in position A, it looks at the first three games which have A as the starting position for a win and then computes the next move based on the redundant frequency of the remain moves in games which had A as a winning start position. Logically, it picks D as the next move because it is the most often made next move in winning games with A as a start position. I'm oversimplifying it all but I think you understand where I am coming from. In this way, the database need only be more clever than the most clever human. And ultimately will force even the best players to learn new strategies to counteract this brute force method.