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
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.