Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - Greg Strong

Pages: 1 2 »
1
This is an interesting idea.  As far as I know, this approach to mitigate white's first move advantage is new.

Unfortunately, playing for king capture removes stalemate from the game.  Stalemate is nice because it gives the losing player something to play for.

You could, instead, address it like this...  If white inflicts checkmate, black may make one more move if and only if it results in checkmating white.  In this case the game is a draw.

2
General Discussion / Re: Will computers ever solve chess?
« on: April 20, 2018, 12:19:25 am »
Even conventional computers may be able to brute force given the right algorithms.

Brute force and algorithmic smarts are practically polar opposites.  The only algorithm which successfully reduced the tree size without any risk overlooking better moves was alpha-beta and that's ancient.  It is almost inconceivable that we'll come up with any further breakthroughs like that.  We do, indeed, improve the strength of our chess programs with better algorithms, but this is done by searching deeper in more promising parts of the tree and searching more shallowly (or pruning altogether) less promising branches.  But this comes with the risk of overlooking things and is no longer "brute force."  You have not "solved" chess, technically speaking, if you have skipped parts of the search tree because they didn't look promising.

I suspect the wall you are referring to will be solved and Moore's Law will continue on well past the point needed to brute force Chess.

Moore's Law is already in trouble.  The writing is on the wall due to physical limitations in miniaturization and heat dissipation.  But Moore's Law only addresses the number of transistors in a CPU, it says nothing about computational performance.  We ran into the wall of maximum single-threaded performance a decade ago.  Computers only become more powerful now through more parallelism.  And parallelism does provide some gains in chess computation but with rapidly diminishing returns.  The exponential growth of the search space in chess is so explosive that it would require something on the order of quadrillions of cores running at a dozen GHz for hundreds of years.  So I'm sorry to report that it's pretty much quantum computers or bust.  Fortunately, I think in the next few decades there is a good chance that we will see some very powerful quantum computers.

3
General Discussion / Re: Will computers ever solve chess?
« on: April 18, 2018, 09:54:22 pm »
A brute-force solution to chess will probably not happen unless (A) we get functioning quantum computers with a sufficient number of qubits and (B) a quantum algorithm is developed for chess.

Conventional computers will hit a wall long before chess can be brute-forced.  There are physical limits to miniaturization and clock-speed and we are nearing them rapidly.

4
General Discussion / Re: POLL: Off Topic Section?
« on: April 15, 2018, 12:59:01 pm »
No

5
True, but I understood it is not WB compatible as an engine yet.

Well, you didn't specifically stipulate that  ;D

Spartacus is sort of in a sorry state. It seems I inadvertently forked the development. (I was not using version control at the time.) So I have two different versions of the executable, one obviously broken for Spartan Chess (it gives +1.80 in the initial position), the other for normal Chess. And there aren't ay source-code files that correspond to their creation date.

Spartacus was supposed to be a varaiant-capable engine based on an incrementally updated attack map. At one time I had that working for normal Chess, but then I changed the board size from 32x8 to 24x10 in order to support Grand Chess, and that broke the incremental update, so that I temporarily disabled it.

I suppose I could fix that, but in the mean time my ideas for how to incrementally update an attack map have evolved a lot, and even if I could get Spartacus working as designed, I would be quite unhappy with it. I applied my new design for the attack map in my Tenjiku-Shogi engine, and it works like a charm there. So it seems my time would be better spent to completely rewrite Spartacus, based on the same principles.

Sorry to hear that.  I'm revisiting Quadrox now but it's been so long and I have so many old hard drives lying around I'm not at all sure that the code I'm looking at was the latest, so I can sympathize.  Although if you've discovered a better approach in the meantime, maybe it's not too much of a loss.  I hope you get back to it.  We could really use another strong universal chess engine.  Fairy-Max may be a weak engine, and yet it remains one of the strongest universal engines ...

Incrementally updated attack maps are an interesting idea that I've thought about from time to time for at least a decade.  For large board variants at least I think the idea has great promise.  But when I think deeply about it and try to nail down all the details, I see it's pretty complicated and I'm not confident I can get it working correctly without spending a *TON* of time developing and debugging, so I keep putting it off.  I've been able to create some decent engines, but I'm not the bad-ass programmer you are.  (not being sarcastic.)

6
Hello all! I am new to this forum, but not new to chess. I registered for chessvariants.com but unfortunately have not received the email that they were supposed to send so that I may confirm my email address. I double checked that the email I input was correct, and I also attempted to create 2 other accounts under a different email, but unfortunately registration emails were also not sent to either of those. Is it normal for the registration emails of this site to take so long?

Any help is much appreciated!

It seems the system is not sending out emails.  I've emailed the site owner.  That's not something I can fix, but I can register you.  Just shoot me an email (mageofmaple@gmail.com) from the email you used to sign up to the Chess Variant Pages and I'll activate your account.

7
as far as I know there has been no development of engines that could play Gothic Chess at all, since then.
There's the new ChessV.  Say, what ever happened to Spartacus?

8
Just to note, your two new pieces, the Pope and Cardinal come from historic Shogi games.  The Pope is a promoted bishop in modern Shogi and is called a Dragon Horse.  The Cardinal is from Chu Shogi and is called a Phoenix (also present in Chess with Different Armies where Betza called it a "Waffle", but I use "Phoenix" instead.)  The name "Cardinal" usually refers to a Bishop + Knight compound as in Grand Chess.  I am not familiar with the name "Pope" being used before.

9
Variant Reviews / Re: Peace Chess (Paco Shako)
« on: February 04, 2018, 06:29:33 pm »
There's a little bit of Alice Chess in this (in that you can both be in the "same square" in Alice Chess) but the joining of the pieces is quite nice.

Actually, that's not quite true.  The rules of Alice Chess are such that the two corresponding squares of a pair can never be occupied at the same time.  (You could, for example, play on a single board where some pieces sit on top of checkers pieces or not to designate which "phase" they are in.)

10
General Discussion / Re: Games against Programs
« on: February 03, 2018, 09:33:26 pm »
It isn't really complicated; the only code it requires is three simple assignment statements. At the start of the node

alpha -= (alpha < currentEval);
beta -= (beta <= currentEval);


and at the end

bestScore += (bestScore < currentEval);

You would need a similar or even larger amount of extra code to adapt mate scores with the distance to root to make sure they show up right in the root, and correct for that while storing and probing in the transposition table.

I am not sure what you mean by 'later in the search'. There is no inconsistensy: the search window is shifted down when propagating towards the leaves; the score is shifted back up when propagated back towards the root. It is just like each level of the tree has its own, slightly shifted zero point of the score scale, so that transferring scores from one tree level to the next needs to translate the score to the new scale by adding or subtracting 1 quantum.

And the delayed-loss bonus does more than just accounting for DTM. For one, it gives you automatic mate-distance pruning, as explained earlier; with the root-distance method you would have to program that separately. In addition, it also works for other gains than checkmates. The engine will always take the shortest path to the best forcible position within its horizon. Plain minimax / alpha-beta doesn't do that; it only cares whether you reach it in the leaves, but not where along the branch towards the leaf. This can be a problem with 'bumpy evaluations', like you often encounter in late end-games like KBNK, where you temporarily have to allow the bare King to flee away from the edge, to drive it back later and closer to the fatal corner. The evaluation doesn't like that. So if you look along the line of optimal play the static evaluation goes up and down, and then up to an even higher local maximum, etc. If the seach has the nearest local maximum well within its horizon, but not the higher maximum beyond it, it wouldn't see any reason to immediately start pushing towards that local maximum, and speding the rest of the depth there. First wasting time deep in the valley, until just enough moves are left to climb to the nearest maximum, scores just as much. And there are always many more ways to waste time than to take the best path. So wasting time is what it will do, and will continue to do forever (as from that valley the next-higher summit will never come into view, it will only be able to see that when it has mounted the nearest maximum). Even 50-move blackmail would not help to make it finally do something, because the nearest maximum does ot involve a capture or Pawn push, and at some point it will just see "hey, that's strange... now it will be draw in X moves whatever I do!" WIth a delayed loss bonus a maximum will look lower if it lies further away, so the engine will start climbing it as fast as it can. And once it reaches the top, it then can see the next-higher maximum, and goes as fast as it can there, etc. A delayed-loss bonus is really a very good cure for indecisive play.

Ok, it took me a while to get my mind around this.  I think I understand why it works.  And it seems to be significantly simpler than the alternative.  You don't need specific mate-distance-pruning code, and you don't need the code to adjust mate scores when reading and writing from the TT.  And it has the added advantage of solving the mate-distance-pruning issue in more general cases.  Very clever innovation.  I wonder why other programs aren't doing this.  There are no others that I'm aware of.  True, some programs don't do a full eval at every node and this approach requires that, but I think most engines do that now.  ChessV does full eval at every node, so I think I'm going to give this a try.

11
General Discussion / Re: Games against Programs
« on: February 02, 2018, 12:04:13 am »
There are two issues here: mate-distance pruning and stopping the root iteration. After you find a mate score, the only reason to search on is to find a faster mate. Once you have exhaustively searched every line to, say, 7 ply, it is not possible that there is a mate in less than 7 ply in nodes that you haven't searched yet. Now this situation probably doesn't correspond to the 7-ply iteration in the root, because of various reductions. But searching beyond 11 ply is probably overdoing it.

The second problem is that it doesn't only continue with iterations that cannot possibly turn up anything better, but that those iterations also progressively start to take up more time. So apparently the search continues to extend lines that do not lead to mate, to a depth that is already beyond the mate. If the best root score so far is a mate in N ply, (as you can see from alpha), it is pointless to search further than N-1 ply from the root, because even if the next ply performs the checkmate, it will still not be faster than what you already had. So you can just return alpha for a fail low, even if the requested depth was far larger. With such mate-distance pruning the tree would not grow larger anymore once every branch has reached the depth of the mate.

Right.  In addition to not cutting off the root iteration, I have not implemented mate-distance pruning...

12
Correspondence Game Requests / Re: Gothic Chess Correspondence Game
« on: February 01, 2018, 11:48:36 pm »
No, NEVER run the move generator twice!

Please note that my suggestion was intended purely in the context of Fairy-Max, which specifically aims for simplicity over strength, and has basically no move ordering at all (beyond TT move.)  I was suggesting that a simple thing like doing captures before non-captures should be a huge improvement.  Running the generator twice was just a suggestion of how that might be accomplished without adding more than a couple lies of code.  But of course running the generator twice is not ideal.  Based on H.G.'s follow-up, though, it seems he's about to accomplish a similar effect with very aggressive use of IID.  Although each IID iteration is another call to the move generator, so it seems he is, in fact, running the move generator repeatedly on the same positions to get better ordering...

While my code is different than yours, what I accomplish is similar.  I run the move generator once and give a score every move (capture or otherwise.) Whenever it's time to play a move, a scan the for the one with the highest eval, move it to the end of the array and decrement the array length so I won't try it again, and then play it.  In a cut-node, hopefully I get a cut-off after the first move.

I assign the scores such that it goes: PV/TT move, winning or equal captures, killer moves, bad captures, other moves.  Captures are scored in MVV/LVA order (I'll always grab the most valuable victim first, starting with the least valuable attacker.)  If the attacker is more valuable than the victim, I use SEE to determine if it's a "bad" capture.  Other moves are scored based on history and PST.  And, actually, I was just looking at the code while writing this to refresh my memory and found a bug!  I wasn't disabling SEE in games that can't handle it.  (My static exchange evaluator isn't going to do the right thing in games with chinese chess cannons, for example.)  Gotta fix that ...

13
Correspondence Game Requests / Re: Gothic Chess Correspondence Game
« on: February 01, 2018, 11:10:16 pm »
Well, in a sense it does search captures before non-captures, because of the IID, which starts at QS depth, where all non-captures are skipped. So obvious material gains (i.e. visible in QS) will be preferred as cut-moves over non-captures. And before the QS iteration the IID even does an MVV/LVA iteration, to select the best capture to start the QS iteration with. For each iteration it runs the move generator again, as there is no storage of moves. It only remembers which move is best (so the next iteration can start with it).

Interesting.  So do you do IID at every node?  Usually there are some restrictions, like not in check, eval within a margin of beta, etc.

14
General Discussion / Re: Games against Programs
« on: February 01, 2018, 11:52:42 am »
Hmmm... yeah, something is wrong.  I think I just need to cut off the iterative deepening loop when a couple successive iterations return a checkmate score.  I'm not sure it's searching beyond depths that can be reached, though.  White isn't forced to deliver the checkmate so the game can go for another 25 ply.   True, the vast majority of that stuff should be pruned but not all will be.

Thanks for taking the time, by the way, to give us some useful analysis so we can improve our engines!

15
Correspondence Game Requests / Re: Gothic Chess Correspondence Game
« on: January 31, 2018, 11:13:06 pm »
I guess the most limiting factor for it is poor move ordering (hash move, and then the rest of the move in move-genration order).

Ouch.  Yeah, that would hurt.  I bet just trying captures before non-captures would make a huge difference.  Even if it meant running the move generator twice, once for captures, and then again for non-captures (if there is no cut-off), I bet that would still be a win, and would keep your code fairly simple.  Or you could consider doing this only at likely cut-nodes...

Pages: 1 2 »