i'm currently developing a two player logic game in university, and i'm facing a huge problem. The game is a state space representated, and I alredy have Alpha-Beta pruning and MinMax algorithm implemented and they are working fine.
The root of the problem is that my gametree is extra large. It is a 20*20 square grid field, which is actualy a 20*20 JRadioButtons. In every turn, a player can almost select any buttons (not the ones that are already selected and a few other ones), so my searching algoritms create a huge gametree, with only a depth of 4-5 (which is really low) there could be billions of treenodes, and it takes forever to go through all of them, even the A-B pruning fails.
So someone gave me the idea that I should use neural networks, so that way I would be able to do something in real time, but i have no idea how should I even start it and what should I do. I've read a lot about ANN, but still, I have no clue how to begin this. I've only found a game which implements an ANN for the AI, but it's in C++ and I could't understand it perfectly.
So, any ideas what should I do, where should I begin or WTF to do?
thx
if you want a pic of the game I can show you 1 if you guys didn't understood a word what I just wrote :D
Is your game an OCR game? No? Then you probably don't want to use neural networks.
There's a fair chance your game is a toy game with an optimal strategy, and you should just follow it.
Failing that, you'll just have to use damn good heuristics.
Some Go AIs use Monte Carlo methods where they pick random moves and play as many games as they can afford to an end.
>>7
i'm not going to, two reasons
1: as I mentiond, i'm not that good at c++, i just never got the hang of it, don't know why
2. my program is working fine, this whole thing is just an idea, if I can't do it, than i won't, no big deal
I'm just curious how could i do this, and because the are so few publications in this area that if i could acomplish this i would be proud of myself.
Name:
Anonymous2010-06-29 15:22
>>12 I see. Yeah, I wouldnt go through all the trouble of rewriting.
Name:
Anonymous2010-06-29 15:25
>>9
the rules are the following:
1. the players move after each other in rounds(duh :D)
2. every player can select any point in the field, except the ones that are already taken and the OTHER players sidepoints (he can altough pick the ones in the corner)
3. if there are two points which are connected via horse move(i don't know the correct english word for it, but the picture talks for itself), and if this line is not crossing any enemy lines, then a new line is drawn.
4. the first player who can create a continous line between his two base sides(green player: verticaly, blue player: horizontaly) wins
i've started to think about this a few days ago, and altough that i've some ideas on some kind of situations (if there is a point selected +-4 distance away horizontaly or verticaly from a given point than a neuron would fire, or if there is a line outgoing from that point it would fire two, i than would only just have to adjust the weights correctly on each inputs), but i just can't see it how could this all come together and how on earth could the computer make a move this way :(
Use iterative deepening and let the human player stop the AI when he's sick of waiting, and then just use the best answer found so far.
Also, learn English.
so no one has any idea, only to solve it some other way?
i don't think IDDFS will work but i'll try it out, i'll put in a timer so the thread will die after maybee 20-30 secs and will use the current best strategy (at current rate that is like 1,5 / 2 million treenodes searched) and i'll also look after that monte carlo thing (don't know much about that either) if no one has any idea how could I make this work with neural networks.
Name:
FrozenVoid2010-06-29 16:18
>>28
The game tree will be too complex anyway for naive bruteforcing.
You should use better pruning in your search, rate the closer(to existing live) cells higher, with a bonus for being closer to edge/for longer connections. Improve the evaluation function, then improve pruning.
Monte-Carlo is random guesses on future game state(statistics), i think its better suited to Go and games with random patterns.
__________________
Orbis terrarum delenda est
Name:
Anonymous2010-06-29 16:28
by evaluation you mean heuristics or the expansion of a tree node or what?
my heuristics are good, i'm quite sure thats not the problem, the problem is like you mentioned, the tree is too complex.
I'll try to find a better pruning algorithm, i just freaked out when the AB pruning failed so hard (well it's the fault of the game, it still improves the search by aprx 70-80% so it isn't that bad, but that remaining 20% of the tree is still too big) and that's why i wanted to find/try other methods.
Name:
Anonymous2010-06-29 16:35
doubles get
Name:
FrozenVoid2010-06-29 16:35
>>30
Each node(game state) has a value e.g. -1.5 or +6.7
which tells how much the board is better for each player.
If the evaluation is very good(more correct), pruning can be increased.
There many kinds of pruning strategies used in chess for example: http://chessprogramming.wikispaces.com/Pruning
__________________
Orbis terrarum delenda est
Name:
Anonymous2010-06-29 16:47
i've made something like this (minmax search with heuristic, only expanded one child node with the biggest heuristic value, I hope you ment to say the same :D) and yes, it was able to search a lot better and faster, the only problem with this was that (and this comes from the game itself too) you have to think at least 3-4 steps ahead to get a "real life" stategy, and i couldn't make a good heuristic function for this (well this maybee my fault :))
the other thing i tried is that the algorithm didn't use all of the usable operators on a game state, just a few ones (i think only in a 6 point or so radius in every point), and at the beginning of the game it was useful, but as the game advance, it used some operators more then just once simply because there were a lot points selected, so it did more harm then it helped...
Name:
FrozenVoid2010-06-29 16:57
>>33
experiment with different evaluation functions/heuristics.
You need to find the one that allows heavy pruning and gives decent results. You can change heuristics by counting active cells vs freecells,
like endgame/midgame/opening in chess. In fact some heuristics might need to take some global factors into account, e.g. if the edges are occupied or blocked by enemy lines(in endgames).
__________________
Orbis terrarum delenda est
Name:
Anonymous2010-06-29 17:08
never thought of dividing the game into multiple sections, thanks for this and the other ideas too!
i'm just a little sad that i won't be able to implement the ANN version of it, oh well, maybee some other time
thanks to everyone who actualy gave some usable ideas :)
Name:
Anonymous2010-06-29 17:14
i'm just a little sad that i won't be able to implement the ANN version of it, oh well, maybee some other time
Don't be. ANNs are pretty rotten unless you put a lot of work into them. The kind you can train with result sets are disappointing for just about anything interesting.
Name:
Anonymous2010-06-29 17:25
i've worked with ANN before, but it had nothing to do with this (it just took a lot of 3D points (like from a 3D scanner), and it draw the approximated Bezier surface, not that big of a deal), and that was pretty simple and I thought when I heard the word neural network that i could do this easily, but i couldn't be more mistaken
the reason the person who recommended ANN said that the network could take a huge benefit from the fact that the game tree is so large and could be really efficient, i don't know if that is rigth or not (well my gut says yes), but if everyone is talking me out of it I belive that it's realy that difficult
Name:
IGNORETHIS!!Aqzg896nRAOgunE2010-06-29 17:26
IGNORE THIS.
Name:
Anonymous2010-06-29 17:39
>>37
The task sounds like the kind that would cause confusion in an ANN. I don't know what kind of sophistication you have in mind for your ANN, but if it's a feed-forward / backprop kind I wouldn't be too optimistic doing any "AI" things with it.
With certain atypical modifications I think a sensibly sized variant could be trained in a reasonable amount of time, but otherwise I think you're looking at a pretty big net and a long time to train it. Maybe a GA would give you the net you're looking for, even if you stick with the feed-forward model.
>>24
How many fucking times does this question have to be answered?
Python or C, depending on which kind of speed is more important to you: development or runtime. Java is the worst of both worlds.
Name:
Anonymous2010-06-29 18:11
>>40
C is off my list for not being object oriented(i'm not saying i hate it, i've used it a lot,but for a 'bigger' project like this one I don't want to use C)
Python may have been a better choise, but i have little experience in it, and i've put my trust in my fairly good Java knowledge.
i'm not that old, i'm only 22 years old, so i favor a little bit the newer languages (Java, Scala, etc...)
but thats that, i don't want to start a flame war
like i said i DON'T want to start flame war
i've got a few very helpful tips on my project, if you have some other fresh ideas they are welcome, else please stop the offtopic crap. thx
>>46
There's nothing off-topic about your profound ignorance when it comes to programming and programming languages. It's the most significant reason you're having problems.
Dipshit.
Who said i'm ignorant?
I never said anything wrong about the other languages, i just said that at the moment Java suits me the best. I've the biggest experience in it, at for me it was the easiest to do this little game with it, you are all probably better in Java/Lisp/C/SEPPLES/whatever, that's why I asked for your help. You don't have to point out that I suck at programming, i know i'm not a genius, i've only done the SCJP exam and i'm still learning at the university, but please let me have my own opinion about some things without raping my butt. Thank you.
I'm not actually good at programming, I just hang around here and type stuff I see at random to try to fit in.
Also you have been given sound advice (wait how would I know?) already and I suggest you take what you can.
At this moment, what is it you're asking for / wondering about?
Name:
Anonymous2010-06-29 19:04
>>51
I'm just watching this thread in case someone comes up with a new idea that might be helpful, may that be any kind of an idea.
And I'm wondering about why i'm not in my bed, it's 01:00 here and I have an exam in the morning from 09:00 :)
You have exams this late in Hungary? When do you get summer vacation?
Also if you've had stable sufficient sleep rest of the week I've found it doesn't really matter how much sleep you get the day before the exam as long as you get some sleep.
please let me have my own opinion about some things
Oh, fuck you. How could you possibly be qualified to hold an opinion on things you know absolutely nothing about?
You may want to look into evolutionary AIs, tho if you take that route, I HIGHLY recommend leaving Java for C or lisp. The AI would be built by writing some conditionals (If the longest enemy line to my left is ____) and actions (Then add a point up-left). You'd add complexity at each generation by replacing actions with conditionals+actions and reduce complexity by replacing conditionals with actions. You'll want to reduce complexity at a higher rate than you add complexity to avoid getting needlessly complicated algorithms. This will ONLY work with one point at a time, but it should be fast enough that you can run one for every friendly point. You can always run more than one per point if you find some way to effectively evaluate a small number of moves. This way, you'd be pruning through a lower depth. Be careful how you swap "DNA". One method would be to only swap along equivalent conditional paths ([If A then [If B then C else D] else [If E then F else G]] will only swap with [If A then [If H then I else J] else [If E then K else L]] along the path [If not A]).
This will be hell to implement in Java because you can't just swap out conditionals or swap conditionals with actions. It would be MUCH easier in C or Lisp where you can pass references to functions. If you want to still keep the Java code, you can always run two processes: one for the GUI and game logic, and another for the AI. They would communicate over a socket or pipe.
It's not exactly a hard problem. Just use a fucking beam search if you want to guarantee an upper limit on the size of the search queue, or use any of a dozen techniques you will already have seen if you've covered alpha-beta pruning to an extent significant enough that you were able to adapt your professor's code.
If your heuristic function has to think three or four steps ahead, you don't understand what a heuristic function is supposed to do.
Read your SICP, read your Xarn, and learn how to program. Problem solved.
What evaluation function are you using? I've never played this game but from a cursory glance ([smallest number of consecutive moves for evenmy to win] - [smallest number of consecutive moves for us to win]) would serve as an ok sarting heuristic. This should allow you to get the offending/defending type tactic. Then just make a number of adjustments to value articulation points and account for number of equivalent paths and their obstructability and you should be getting somewhere.
In the image above green can win in six moves, blue can win in nine so the board is initially valued at 3? A good move for green is row 12 column 10 (1-indexed); as he can now win in five- with no easily blockable routes, deeper searching reveals blue will have only one way to still win in nine moves, and this can be easily blocked.
My intuition here would be that player 1 can at at the very least always force a draw, possibly using some kind of mirroring, or an "always play at same row/column as opponent" strategy.