Java / AI / ANN

so, here is my problem:

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

suck your own dick

>>2 Seems like a logical solution. Well said.

JRadioButtons wtf?

Did you actually write something in Java?

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.

>>4
maybe you'll understand it this way better: http://img571.imageshack.us/img571/3236/gamej.jpg

>>6

Rewrite in SEPPLES.

>>8 Why would he rewite in SEPPLES?

Can you describe the game rules and the value of fields?


__________________
Orbis terrarum delenda est

>>8

Because it's not Java.

Ohh gotcha, my bad.

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

>>12 I see. Yeah, I wouldnt go through all the trouble of rewriting.

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

that is all

>>12
Post rules of game please.

In during >>15 see >>14

oh and ofcourse in every turn the oncoming player can select only ONE point, i've forgot that

>>14

Just to clarify; horse move like in chess?

>>18
yup

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 :(

>>18
horse move..  ahh reminds me of a vid I saw

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.

Give the AI whatever suggestions you can and Monte Carlo it, also next time don't use Java.

>>23
i know this isn't the best language for this kind of shit, but which one you suggest then and why?

>>24
[u][i]READ YOUR FUQIN SICP[/i][/u]

>>25
^FUCK!!!

>>24

SEPPLES

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.

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

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.

doubles get

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

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

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

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 :)

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.

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

IGNORE THIS.

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