Quote:

Original post by WeirdoFu Its a nice idea, but then consider the space complexity involved. I'm not even sure if you can set your k to 3 or 4. Given the current problem, say we group the first 3 pieces together and generate all the possible combinations, which is 432x216x432 and then 64-bit entries, that's 8 bytes per entry. So, the required space would be 322,486,272 bytes, or about 307.5MB. Through in another piece and you'll be clear into the multi-GB region. Even if you store only the feasible ones, you'll still need to check 40 million entries and optimistically if only 1% are feasible, storing all combinations of 4 pieces would still require close to a GB of memory. The only possible implementation for this I can think of is dump everything to file then use the windows filemapping feature to map the whole file into virtual memory and then let the OS worry about the address paging.

I hadn't made any computations on how big the table would have to be. There are some tricks by which you can save some space. For instance, you could divide the data in 65536 data structures, indexing with the first two bytes. Those data structures now only have to contain 6 bytes per entry. In any case, there are more combinations than I had originally thought. 3 pieces is workable and 4 might be possible with a lot of RAM and effort (1 GB of RAM is fairly standard these days, and 4 is not unheard of).

Quote:

Original post by alvaro Quote: I wouldn't really call this artificial intelligence but more like a really nice optimization trick, if you can get it to work. I wouldn't call it AI either. I am just trying to solve a problem here, and I don't particularly care if you can call it AI or not. Do you consider computer chess to be AI? A very similar trick is used there; databases are generated with all the exact scores for positions with only a few pieces left, and then they are queried during the search, whenever one of the branches happens to fall into a known endgame.

I think the key word here is search. If the solution uses a search, it's AI. On the other hand, it is often said that once we solve an AI problem, it's not AI anymore. ...Maybe AI is in the eye of the beholder.

This is a problem that falls clearly within the realms of constraint satisfaction problems, which are a popular area of AI research. I would suggest that MILP (Mixed Integer Linear Programming) would be a good tool to tackle your problem. You'll find plenty of free software and literature for MILP on the web.

Good luck with it. 8)

Timkin

Quote:

Original post by Anonymous Poster Give simulated annealing a try. I think you will find it easier to implement than a GA. There should be plenty of papers available to point you in the right direction. I remember a lecture given by Rob Rutenbar @ CMU where they had a video of one of their place and route systems solving the exact problem you describe.

Yup, simulated annealing will be much easier to implement, considering its nothing more than a probabilistic hill climber. And of course, like every other probabilistic hill climber, you run into the nasty cooling schedule issue. What most research on simulated annealingdon't show half the time is all the various cooling schedules that are tested before they hit on one that does better. Of course, its the same with GAs as well. So, in the end, you win some and you lose some. It all boils down to heuristics, parameter settings, and the various choices you make during implementation. The crazy world of optimization.

Heck, even hill climbers have various issues involved, like do we do probabilistic restarts or do we do min conflict or something else.