I imagine the basic chess algorithms adapt nicely for Hex. A min-max with alpha-beta prunning and, if needed, nega-scout. The trick is designing a good heuristic for game board state evaluation (non-final board states, of course). For Hex, this should be fairly trivial: How many pieces needed to win, how vulnerable am I to being blocked.
References:
http://en.wikipedia.org/wiki/Minimax
I once programmed a pretty bad Othello/Reversi game for a friend of mine.
Given that it was my first AI the difficulty levels were called (in order of increasing difficulty): "Mr. Stupid" (chose random valid moves), and "Very Easy" (stupidly simplistic min-max algorithm over the next 2-3 possible moves).
You're right that the AI will be easy to beat, but it does at least give you something to do.
Re:Hexagonal grids for games
by mynameishere on Sunday June 02, 2013 @08:27PM
(#5810694)
I think it's okay if it's a poor AI, but it should be enough to play the game through. When you're sitting alone at your computer, there's nothing to do past the first move.
Got it. Yup, right now the site is only interesting if you have someone sitting next to you to share the computer with. The next step would be to add a server-side backend and allow playing online, if I end up revisiting this project.
FYI, if you and the other commenters just want to play Hex, there are existing sites you can play it on, like http://www.iggamecenter.com
I'm under the impression that making a non-sucky AI for nontrivial board sizes (say 10x10 and up) is an unsolved problem... much like no one had a Go AI that could beat even a skilled beginner until quite recently. And I couldn't find an example of any Hex-playing AI, even a crap one, that was open source.