Author: Bas Hamstra
Date: 05:11:35 01/18/03
Go up one level in this thread
Actually we *reversed* random parts like this: A B C D E F G H -> A F E D C B G H Bas. On January 18, 2003 at 07:42:12, Bas Hamstra wrote: >Hi Russell, > >Reminds me of the assembly NQueens.com program that I once wrote. You start it >with Queens n, where n is the number of queens on a nxn board. The comfile is >687 bytes, which includes 18 bytes for the error message "Usage: NQueens n". For >14 queens it outputs: > > "QUEENS=14 Solutions=365596" > >In a few seconds. If I am not mistaken it doesn't even use a board, but just >computes the number of queens per "ray". Have to look it up, it is a while ago. >In fact it was not straight asm, but a C-- variant (contra C++) which is halfway >between C and asm (Sphinx C-- compiler). It was fun, we did contests back then, >to see who could solve it fastest. We also did travelling salesman problems with >impossible numbers of cities, every day new distance records were posted... >Brute force didn't work anymore, so heuristics, like genetic algo's etc. I think >an approach where the "route" was encoded as an array, and you randomly swapped >random portions of the route was a simple and very effective approach. If length >increased more than a certain margin, you swap it back. The margin prevents more >or less getting stuck in a local optima. Optimum solution not guarantueed of >course, but you get nearly optimal solutions extremely fast. Sorry if I drifted >away from your question a bit :-) > >Bas. > > > > > > > > > > > >On January 17, 2003 at 23:58:25, Russell Reagan wrote: > >>If you were writing a program to solve the 8-queens problem, and your goal was >>speed, would you use "normal" computer chess techniques (like, say, 0x88 or >>bitboards) or would you do something more specific? >> >>For instance, rather than detecting attacks via traditional 0x88 or bitboard >>methods, you could keep track of which ranks and files are already occupied (and >>thus are not candidates for further occupation), and then you could quickly rule >>out large chunks of the board that are not available for a queen. This would >>seem to be much faster than doing a typical "full blown" attack detection. >> >>You could also use a simple pseudo-attack array (easy to create for 0x88 or >>bitboards) and cut out the extra code to determine if a pseudo-attack is a real >>attack, since in this problem, a pseudo-attack means two queens are attacking >>each other somewhere. >> >>I am interested in two things. First, I would be interested in knowing how >>people would approach this problem (and other "chess-like" problems) where >>traditional computer chess methods will work, but might not necessarily be as >>fast as other methods. Second, I would be interested in knowing of other chess >>problems that are not "game" problems (IE something a typical chess engine can't >>solve, like the 8-queens problem or a knight's tour problem). The knight's tour >>problem seems like another one that fits into this category. >> >>For those who may not know what the 8 queens problem is, it involves finding >>positions using only 8 queens where no queen attacks another queen. You can only >>use queens. So adding pawns to block a queen attack, for example, is not >>allowed.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.