3 ms·

Pull requests welcome! 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

by graue 13y ago

Pull requests welcome! 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.

mynameishere 13y ago
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.
- graue 13y ago
  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 http://www.iggamecenter.com
mpyne 13y ago
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.
sergiosgc 13y ago
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 http://en.wikipedia.org/wiki/Minimax http://en.wikipedia.org/wiki/Alpha-beta_pruning http://en.wikipedia.org/wiki/Alpha-beta_pruning http://en.wikipedia.org/wiki/Negascout http://en.wikipedia.org/wiki/Negascout

by graue 13y ago

mynameishere 13y ago

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.

graue 13y ago
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 http://www.iggamecenter.com

mpyne 13y ago

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.

sergiosgc 13y ago

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 http://en.wikipedia.org/wiki/Minimax http://en.wikipedia.org/wiki/Alpha-beta_pruning http://en.wikipedia.org/wiki/Alpha-beta_pruning http://en.wikipedia.org/wiki/Negascout http://en.wikipedia.org/wiki/Negascout