Question posted in 
I’m working on a toy problem: it is to make code that learns to be unbeatable at Tic Tac Toe only by playing itself. I’m a newbie to this sort of thing… I just decided that I would do it by using a random number generator to choose moves for X and for 0… and then keep record in a text file of moves that should never be played again (there is some complexity in that part of the algorithm, but never mind).
My question is: should I use a relational database management system instead of a text file to store “game states” to avoid? I’m tempted to do so because then I could have unique ID’s for each game state… and special tables added to the database to keep track of, say, all “game states” that came before a loosing “game state” (one “game state” mapped to many “previous-move game states”, for example). It seems to me that with some smart use of tables, a relational database management system would be WAY easier to go fishing through than a crude text file. I’m assuming the downside will be the run time needed for the code to train itself (because all the calls to the database could take a while).
Any wisdom would be much appreciated. Is it sane to be thinking about using a database? Is my analysis of the pros and cons accurate? Thanks!
3
Answers
RDB (relational databases) are useful when you have to be certain that all data are consistent, however, the velocity of the system (due to transactions, lock, etc…) is less efficient than Objects Database (Redis) or Documents Database (MongoDB)
You can use this approach with MongoDB :
1 game is a JSON document that contains :
ID of the game (eg “0001”)
Game state (eg “0” for ‘0’ win, “1” for ‘X’, “2” otherwise
An array that contains all move during game
Other data like time, date, …
After that you can simply explore all JSON with regex throw Mongo Connector.
I really love your analysis of database problem, that is true !
Hope this can be helpful.
Tic tac toe has 9 fields.
in any field you have 3 value options (‘ ‘, ‘X’, ‘O’). That makes 3^9 = 19.683 possible combinations.
You need to store 9 bit for any field (0,1 or null). That makes 177.147 bits of data, not mentioning meta data.
Additionally not all possible combinations are valid (you can’t have 3 O’s and only 1 X in your field). That makes the number above even smaller.
In other words, If you don’t have any extremly high timelimitations the choice of your database is not a performance driven one.
You still should read about indexing if you use relational databases.
However, i would not recomend you to store your data in textfiles (not talking about no-sql db, but real text files on your hard disk). Because that makes accessing complicated and, if not programmed well, maybe slow.
A final recomendation would be the relational database system, because here you have more restrictions like unique ids and no unwanted datatypes. That often leads to less mistakes/bugs. Also you can give any possible combination a unique key and let your RDBMS enforce this for you with a unique_constraint. Than later on you make a “linking table” that links only the id’s of your unique combinations.
Florian made a good start, but note that you have notably fewer than the 3^9 game states listed. If we assume that
Xmoves first, then the count ofXentries must be equal or one more than the count ofOentries. For instance, the boardXX- | --- | ---is illegal.There are 7665 unique board positions. This should be small enough to give each a simple key (such as its integer value in trinary). Use a graph package to build the graph of positions that lead to other positions; label the edges with the choice of move. For instance, if we code the board as 0=blank, 1=X, 2=O, then we get the opening board (0) transitioning to position 1 (aka 000 000 001) on choice 9 (lower-right corner).
You should be able to hold the entire game tree in memory at once: 7665 nodes with a mean of perhaps 6 edges per node, 3 words per edge. That’s ~120k words of memory for the entire tree, before you apply pruning as you train the game AI.