- Created Friday, December 25th 2015 @ 19:34:19
Let's talk about our bot strategies.
I'm using a simple basic evaluation function that I found somewhere in the internet. So I'm looping over all (I believe 69) victory possibilities, give little points for 1's there, more points for 2 stones, huge points for 3 stones and 4 is a victory of course.
Imo the nice part about my bot is that it is capable of searching 8 steps deep into the minimax tree (from the start, with all possiblilites open). When I count my minimax calls I get almost 400.000 calls in the first round (just to find out that the stone should be put in the middle...) I'm using the starterbot Java datastructure and doing those alpha / beta cuts without any further optimizations.
There are some papers on the internet including the master thesis where 4 in a row got solved. Some stuff there seems pretty important for me, especially the distinction between even and uneven threats and different winning conditions for the first and the second player.
- Updated Friday, December 25th 2015 @ 23:22:33
Very similar approach, but it allows me to search up to the depth 15 and higher. I think this is because of some classic minimax optimizations (try to use transposition tables), tuned data structures and probably bit more complicated evaluation function.
- Created Saturday, December 26th 2015 @ 00:12:35
I guess you aren't talking about the late game where there aren't that many options left. Depth 15 seems extremely deep for me and I already thought my depth of 8 was something to brag about.
- Updated Sunday, December 27th 2015 @ 23:58:37
I just very quickly put my bot together from pieces of code I had lying around from previous projects. The search is plain iterative alpha beta with transposition tables (not optimally used) and killer moves, with a quiescence search that evaluates immediate threats and single moves. The evaluation function is home made and accounts for even/uneven threats.
The search is largely unoptimized and is probably quite slow (although I don't know how many nodes/seconds). At the beginning it searches typically 9 plies (+ immediate threats), as the game progresses the search depth gradually increases and typically it sees 20-24 plies in advance when it will win/lose. The evaluation function usually indicates a probable win/loss some moves before that.
For fun I started a search from the beginning to find the winning strategy but I had to kill it around ply 30 after 2 days of computation but I think it is definitively doable within a few weeks.
- Updated Wednesday, December 30th 2015 @ 05:29:17
I read into those Transposition Tables and this seems quite usefull. However this opens up the next problem that you need a better data structure for the lookup than a 2 dimensional array.... so, store the whole board state in a number? But how?
Restrictions in the length of Java longs, so just storing the state according to the output from the engine isn't working (0,1,2 in all digits).
It would be also cool if the number representation allows running fasst evaluation functions directly.
- Created Wednesday, December 30th 2015 @ 06:29:40
Mine is minimax with alpha beta, killer moves and a transposition table.
Unfortunately its also written in python, so it only makes it to depth 7 (searches about 10000 nodes per second).
My scoring function is also probably horrible, it just checks for regular wins, forced wins (when you can fill all the tiles and force your opponent to play a move and let you win), and gives a small bonus for having more threats
- Updated Thursday, December 31st 2015 @ 06:45:14
With Java you are not restricted with long keys for hash tables, so you can simply use strings of length 42.
But with compact approach 64 bit is enough to represent any game state: 3x7 bits to represent how many cells are occupied in each column + 6x7 bits to represent only cells that are occupied by first player = 63 bits. It is obvious that this information is sufficient and unambiguous. But bit manipulations are quite slow in Java. So there is a much more efficient (but a bit more probabilistic) way to represent keys for transposition tables. I recommend you to read also about Zobrist hashing commonly used in chess programs.
- Created Thursday, December 31st 2015 @ 15:30:45
I didn't know how to write a proper evaluation function for minmax, so I just used this idea:
I also check for forcing moves during the playouts to avoid the problem mentioned at the end. I keep track of time to maximize the amount of playouts done; with about 800ms I can get around a quarter of a million playouts, depending on how far along the game is. It's fairly good considering how simple it is.
Unfortunately, it doesn't converge to the best move, so a very large number of playouts doesn't improve my odds of winning by very much.
- Created Sunday, January 3rd 2016 @ 00:54:34
@Norman: like chianti(?) I use zobrist hashes to represent the board and hope for the best, the main reason being that I just could copy some old code I had laying around. I store 64 bits in the transposition table and use an independent key to index the table so with over 80 random bits the risk for collisions (two different positions giving the same hash) is very small. But an unambiguous board representation for this particular game should work well, just be careful to create a good quality hash function to index the table.
- Created Friday, January 8th 2016 @ 19:38:49
Couple of days ago I've added precomputed lookup table to get perfect play on game start. The lookup table contains real score for each board state with 10 stones (it is about 900k states, I use this lookup-table when doing minimax on first moves).
Sometimes my bot still timeout or doing incorrect estimation in the middle-play, but I think perfect play can be reachable with some more additional optimization.
- Created Tuesday, April 19th 2016 @ 04:33:14
I'm doing 1-ply with Monte Carlo rollouts (about 100k games simulated in a few ms, more didn't make much difference). So far I seem to be playing a perfect game as 1st player (as of a couple of hours ago).
My hopeful secret sauce is around trying to find ways to win as second player. It seems as though all top 15 bots have some flaws in their starting-player game with the exception of Calculon or chianti_Four (they seem to have perfect starting-player games so far -- only going on 5-10 samples).
I'm curious what the finals will look like. If even just the top two bots play perfectly, then what? A two-way tie for first place?
- Created Tuesday, April 19th 2016 @ 06:04:41
Update: I found one exception for chianti_Four - it drew as first player versus Calculon here: http://theaigames.com/competitions/four-in-a-row/games/571344344ca8011a0edcd419
DeveloperCreated Tuesday, April 19th 2016 @ 08:47:14
@hitechbunny For Four In A Row there won't be any finals. As this is just a beginners competition and bots can be made to play 'perfect'.