Posts:
4
Registered:
Feb 15, 2010
From:
Maryland
Age:
36 Home page
Pente AI and "undo-able" GUI
Posted:
Feb 15, 2010, 6:59 PM
I am new here; I really enjoyed playing Pente as a kid, and recently resurrected past interest in developing an AI opponent that (1) could beat me, but (2) used a relatively simple board evaluation function. The result is a program that I had a lot of fun putting together, and hopefully you may find it interesting or useful as well.
Well, (1) beating me turned out to be pretty easy to do, since I am definitely a novice player. But I think the program plays pretty well even at more advanced levels. I am interested in pitting it against more advanced play than I can provide; I have done some testing against Mark M.'s Windows Pente program, but I have stayed out of pente.org since the use of AI is explicitly discouraged.
Also, while the GUI was admittedly an afterthought (my main interest was in the AI "business logic"), the interface didn't turn out too badly. It's built using FreeGLUT/OpenGL, so should compile without problems on any supporting platform. (I have pre-built it for Windows.) You can play any move of either color yourself or let the computer move, varying the search depth/breadth at any point in the game. You can backup in the move history to explore lines, etc.
There is also a clean separation between the AI and the GUI, the latter which could be stripped off and replaced with something else (I have done this for my own automated testing/analysis/timing/etc.)
Anyway, I would appreciate any review or comments any of you may have. Windows executables and all source code are available. I am working on hosting the software online somewhere (maybe here?), but until then, send me an email if you are interested.
Posts:
1,032
Registered:
Dec 16, 2001
From:
Powell, OH
Age:
37 Home page
Re: Pente AI and "undo-able" GUI
Posted:
Feb 15, 2010, 9:28 PM
Very cool, thanks for posting Eric!
I always thought it would be good to have multiple AI implementations at pente.org but never had another one to use except Mark's.
I would be interested in seeing the source definitely! If you want to host it somewhere it would probably make more sense at someplace like sourceforge.net or code.google.com
Let me know what you think. Note that the "branching factor" is a mostly artificial restriction, but one that speeds things up quite a bit without sacrificing too much in level of play. For example, when I extend the lookahead, I usually limit the branching factor accordingly: e.g., depth/breadth combinations of 6/24, 8/15, 12/8, etc.
If you or anyone else is interested in extending/modifying/redistributing/whatever, you're certainly welcome to. (I saw earlier posts about your porting Mark's AI code to Java; I could help with a JNI hookup to native C++ if that would be easier.) Let me know if I can help, or at least drop me a line if you do use it-- these projects are more fun when I know someone is getting some use out of them.
Posts:
542
Registered:
May 9, 2002
From:
Northeast USA
Re: Pente AI and "undo-able" GUI
Posted:
Feb 17, 2010, 12:42 AM
Hi farmeer1, welcome to Pente.org!
I played a few games with your AI and it's pretty decent. In one game I put myself at a disadvantage pretty early on to see how it would do and it did carry the game out to a victory, which I was impressed with. A couple of other games I felt like it had much stronger moves available and it made the "wrong" choice, which ended up with me beating it pretty easily. I couldn't tell if it did better or worse as more and more stones dropped onto the board, or if certain types of positions were easier for it to evaluate than others or not. But it seemed above average for an AI anyway.
How are you handling opening moves? Asking an AI to calculate the first couple of moves -- first of all is very slow, and second of all the normal evaluation algorithms are probably insufficient to consistantly end up with a strong result. You might want to consider putting together a small "database" of neutral to strong openings for the first 3 moves or so that the AI can lookup without crunching through it's algorithm. You could do this by including, say, the top 3 most successful moves in each position as shown in the Pente.org database.
Some quick feedback: The number displayed for the AI's "confidence" in it's position is pretty wacky. I guess if he's saying something over 2 billion you're in trouble! Haha. The biggest thing -- if you could add some sort of progress bar or percentage for waiting time like Mark does in the WPente program it would be extremely helpful. Like I said before, the very first move is extremely slow -- and I wasn't even sure it was working the first few times I tried it, so I would hit the spacebar a few times and it eventually caused the software to hang and I had to kill it and restart. I had no visual feedback that showed that the AI heard my request and was "thinking" about its move or any indication of how long I would have to wait for it to respond. The only way I knew it was working at all was when I finally tried a game by reducing the "depth" down to 1 and then it responded right away. Then I put it back to the default and just waited and it did eventually move.
It would definitely be cool if you could add this AI to this site as another choice for a computer opponent in the game room. This would give the appearance of AIs with different "personalities" which would be cool. I hope you will continue to work with Dweebo to make that happen.
Not sure if there is anything about your evaluation algorithms that you can improve. With only a small sample of games that I played, it seemed to me that the AI plays at an intermediate level, but not an advanced level. But this is generally good enough for an AI anyway.
Posts:
2,220
Registered:
Mar 4, 2007
From:
San Francisco
Age:
45 Home page
Re: Pente AI and
Posted:
Feb 17, 2010, 1:24 AM
i have been working on a AI Opening Data Base, formatted in .SGF file type.
it will belong to dweebo when its completed, and thus his decision to share if your interested. it will essentially be the best 2nds and 3rds for player one that i can determine. this will only be partially based on data base results from this site, as much of the results can be false. im rewriting the results based on my own deep analysis. im half way finished with it. again this will just be a opening book for Player 1.
the player 2 opening book will be a larger project that will take alot more time to complete. i havnt started it yet.
i tried your AI and liked it. ill give you a better opinion on it in time. i look forward to what becomes of it, thanks again.
zoeyk
Scire hostis animum - Intelligere ludum - Nosce te ipsum - Prima moventur conciliat - Nolite errare
Posts:
4
Registered:
Feb 15, 2010
From:
Maryland
Age:
36 Home page
Re: Pente AI and "undo-able" GUI
Posted:
Feb 18, 2010, 1:56 AM
Thank you very much for taking a look. Your comments were helpful, and I made some changes in response (see the link I posted earlier)...
> How are you handling opening moves?
As you can probably tell from the computation time, I don't have an opening database; that will take some work. In fact, there is literally *nothing* fancy here at all-- it's really just fixed-depth negamax with alpha-beta pruning.
The only interesting part-- at least initially-- was my idea for the board evaluation function. The idea was to have a *very* simple evaluation function, essentially just a sum over all empty points of values from a lookup table indexed by patterns of empty/black/white stones. The thought was that this would be (1) very fast, and (2) easily "tweakable," indeed possibly even *learnable*, by iterative modification of the pattern weights based on playing another AI opponent.
It did turn out to be reasonably fast-- indeed, I actually evaluate *every* board position, not just the max-depth ones, as a simple approach to move ordering. The lookup tables (*.dat files) are generated in the Mathematica notebooks (src/*.nb files) if you want to take a look.
> Some quick feedback: The number displayed for the > AI's "confidence" in it's position is pretty wacky. > I guess if he's saying something over 2 billion > you're in trouble! Haha.
This latest version displays the board evaluation in hex, which might make them seem a little less wacky . The numbers over 2 billion are approximately 2^31, and represent terminal (won/lost) games. The lookup table weights are also powers of 2, but with exponents varying over most of the available range. This effectively realizes a "lexical" comparison of board positions, where a known win is always better than, say, an open 4, which is in turn always better than an open 3, etc.
> The biggest thing -- if > you could add some sort of progress bar or > percentage for waiting time like Mark does in the > WPente program it would be extremely helpful.
This is a good suggestion. I actually added a couple of things to this latest version. One is an indication of progress, showing the moves as they are evaluated... but the progress is sent to stdout, which on Windows will appear in the now-accompanying console window. (I also added an indication of time elapsed to compute each move.) Stdout is lazy, I know, but (1) it was much cheaper than the multi-threading that would be involved in showing progress on the GLUT window, and (2) it has the additional benefit of making it easier to kill the program by closing the *console* window.
The other addition was the ability to save/load games. See readme.txt, but it's basically 'S' to save and 'L' to load.
One last issue that I am still analyzing is level of play. I agree that the AI doesn't always make the best move, particularly early-- it seems entirely too comfortable with giving up a first capture. Have you experimented with lookaheads beyond the default 6? I have been testing against Mark's WPente AI, and had pretty good results, particularly at deeper lookaheads, even when significantly restricting the branching factor to make the moves (a lot) faster. I need to look at this in more detail...
. The numbers over 2 billion are approximately 2^31, and represent terminal (won/lost) games. The lookup table weights are also powers of 2, but with exponents varying over most of the available range. This effectively realizes a "lexical" comparison of board positions, where a known win is always better than, say, an open 4, which is in turn always better than an open 3, etc.