New algorithm: Concentric AlphaBeta

[Brunetti]

Finally I've implemented a long time idea, concentric alpha-beta. The principle is simple, but to implement it I had to overcome a lot of practical problems. It seems to work very fine now, despite one crash every 4 or 5 games, but this could be corrected by a better implementation.

I thought a while about that, and I won't release Protej 058 sources, but I'm going to public the algorithm: I think that this can be a good contribute to the community.

This is the last gauntlet, 1+1 time and G6 positions:

Code: Select all

    Engine                   Score     Pr
01: Protej 0.5.8             150.5/180 ············
02: Igorrit 0.086v9          5.5/12    0=====1=0===
03: Naum 4.1                 4.5/12    0===0=10=0==
04: IvanHoe 9.63 ModB3       3.0/12    0==00==0=00=
04: Stockfish 1.6.2 JA       3.0/12    00==0==00=0=
04: Stockfish 1.6.3 JA       3.0/12    00=00==0=0==
07: RobboLito 0.085e4        2.5/12    00=000=00===
07: Stockfish 1.6.0 JA 3     2.5/12    00=000=0==0=
09: Naum 4                   2.0/12    00=000==000=
10: Rybka 3                  1.0/12    000000=0000=
10: Tankist 1.2              1.0/12    00=000=00000
10: Grapefruit 1.0a3         1.0/12    000000=0000=
13: Rybka 2.3.2a mp          0.5/12    000000=00000
14: Glaurung 2.1             0.0/12    000000000000
14: Cyclone xTreme Wrath     0.0/12    000000000000
14: Crafty 22.0              0.0/12    000000000000

240 games played / Tournament finished
Start positions: 001-006
Completed: 2010.04.01

Alex[/b]

[PK]

well, I have a better one, and I give it for free. There is a paper on solving a game of five-in-line (like noughts and crosses, only one needs a longer line) by the means of threat space search. You make a threat (a three or a four), assume that opponent blocks it in all the available places *simultaneously* and proceed with the next threat. If there's a win to be found this way, then there would be a win in the normal game as well.

Now for the Big Thing: in the over the board game actual chess move consists of lifting a piece and putting it back on the board. The new algorithm postpones the second step. You threaten the opponent Queen, it goes up and does not return for a moment. You make a move, opponent may react by reinstating a Queen on any previously legal square. If You still win,, You have saved some search effort.

[Brunetti]

well, I have a better one, and I give it for free. There is a paper on solving a game of five-in-line

Well, I was talking about standard chess

This is the modified AlphaBeta, summarized:

Code: Select all

SearchRoot(){
	Alpha=-inifnite
	Beta=+Inifnite
	InternalAlpha=0
	InternalBeta=0
	Range=+MaxEval
	Detail=1
	Best=-infinite
	
	while not timeout
		Value=Search(InternalAlpha,InternalBeta,Range,Detail)
		if Value>Best
			print line
}		
		
Search(InternalAlpha,InternalBeta,Range,Detail){
	GenerateLegalMoves
	SortMoves
	foreach move
		MakeMove
		Value=-Search(-InternalBeta+Detail,-InternalAlpha+Detail,Range-Detail,Detail+1)
		UnmakeMove
		if Value>=InternalBeta
			return Value-Detail
		if Value>InternalAlpha
			InternalAlpha=Value+Detail
			Detail+=1
			Range-=Detail
	return InternalAlpha-Detail
}	

Actually Range and Detail have to be choosen better; I won't say my values, tuned after a lot of tests... Some work for you too

Alex

[zamar]

is the modified AlphaBeta, summarized:

Code: Select all

SearchRoot(){
	Alpha=-inifnite
	Beta=+Inifnite
	InternalAlpha=0
	InternalBeta=0
	Range=+MaxEval
	Detail=1
	Best=-infinite
	
	while not timeout
		Value=Search(InternalAlpha,InternalBeta,Range,Detail)
		if Value>Best
			print line
}		
		
Search(InternalAlpha,InternalBeta,Range,Detail){
	GenerateLegalMoves
	SortMoves
	foreach move
		MakeMove
		Value=-Search(-InternalBeta+Detail,-InternalAlpha+Detail,Range-Detail,Detail+1)
		UnmakeMove
		if Value>=InternalBeta
			return Value-Detail
		if Value>InternalAlpha
			InternalAlpha=Value+Detail
			Detail+=1
			Range-=Detail
	return InternalAlpha-Detail
}	

Congrats!! I think you've just made the greatest invention in computer chess since inventing PVS.

Your algorithm is absolutely brilliant!!!

[Damir]

Finally I've implemented a long time idea, concentric alpha-beta. The principle is simple, but to implement it I had to overcome a lot of practical problems. It seems to work very fine now, despite one crash every 4 or 5 games, but this could be corrected by a better implementation.

I thought a while about that, and I won't release Protej 058 sources, but I'm going to public the algorithm: I think that this can be a good contribute to the community.

This is the last gauntlet, 1+1 time and G6 positions:

Code: Select all

    Engine                   Score     Pr
01: Protej 0.5.8             150.5/180 ············
02: Igorrit 0.086v9          5.5/12    0=====1=0===
03: Naum 4.1                 4.5/12    0===0=10=0==
04: IvanHoe 9.63 ModB3       3.0/12    0==00==0=00=
04: Stockfish 1.6.2 JA       3.0/12    00==0==00=0=
04: Stockfish 1.6.3 JA       3.0/12    00=00==0=0==
07: RobboLito 0.085e4        2.5/12    00=000=00===
07: Stockfish 1.6.0 JA 3     2.5/12    00=000=0==0=
09: Naum 4                   2.0/12    00=000==000=
10: Rybka 3                  1.0/12    000000=0000=
10: Tankist 1.2              1.0/12    00=000=00000
10: Grapefruit 1.0a3         1.0/12    000000=0000=
13: Rybka 2.3.2a mp          0.5/12    000000=00000
14: Glaurung 2.1             0.0/12    000000000000
14: Cyclone xTreme Wrath     0.0/12    000000000000
14: Crafty 22.0              0.0/12    000000000000

240 games played / Tournament finished
Start positions: 001-006
Completed: 2010.04.01

Alex[/b]

April 1st fools...

[Andres Valverde]

Finally I've implemented a long time idea, concentric alpha-beta.

And suddenly .... you got awake

Well done Alex

[LiquidNitrogenOverclocker]

Actually Range and Detail have to be choosen better; I won't say my values, tuned after a lot of tests... Some work for you too

If you are going to publish your findings, be prepared for a lot of nay-sayers out there. They have to be able to duplicate your results in order for your claims to be taken seriously.

You should be prepared to:

1. Show the complete implementation in C
2. Discuss the role of "Range" and "Detail" in the reduction of the search space. Start with a chess-specific case, but generalize to a "general" case for any game.
3. Compare the number of nodes explored as a function of depth searched from several different positions, and compare/contrast the same search with Alpha_Beta, PVS(), and perhaps MTd(f).

I wish you the best of luck, and I hope your early results hold out good for the long run!

[wgarvin]

Ed, did you notice the date on the original post?

[metax]

[CRoberson]

The algorithm, as currently stated, would play very poorly. It will go down the left most branch of the tree and will not look at any 2nd moves much less 3rd or other choices. Its only chance of looking at some second choices is if it hits terminal nodes such as checkmate or stalemate.