|
|
|
|
Gothic Vortex contains a high performance search engine, and a finely tuned evaluation function. These are the two critical ingredients that
make a program a formidable opponent. Each of the three different editions of Gothic Vortex will feature the same technologies at their core.
This page will provide a list of these common components, and offer an explanation of how they work.
| |
|
Below is a short list of what programmers would identify as the key components of the Gothic Vortex search engine. You can
click on any of the links and go directly to that section of the page.
80-bit Search Engine
Static Exchange Evaluator (SEE)
Finely Tuned Evaluation Function
Alpha-Beta Nega-Max Principal Variation Search
Iterative Deepening
Fractional Depth Search Extensions
History Heuristic
Killer-Move Heuristic
Frequency Filtering Heuristic
Multiple Hash Tables
Each of these items are explained in detail below.
In order to run Gothic Vortex, you can see all of the requirments (hardware, operating systems) if you
click here.
|
|
Contemporary chess programs are able to exploit the rapid binary calculations performed by the computer by representing the pieces on the board
in a rather unusual fashion. Programmers use many variables comprised entirely of 32-bit or 64-bit constructions that can actually
be sent to routines that do the equivalent of generating chess moves. Such a program is usually called a Bitboard Move Generator.
Since the regular chess board contains 64 squares, it makes sense to use
64-bit constructions to optimize the speed at which the program executes. However, not all computer operating systems perform native 64-bit math manipulations. So, 64-bit program code is "emulated" by using pairs of 32-bit constructions.
Such emulation slows down the overall performance by at least a factor of two.
It is possible to use an Array Move Generator. Most programmers who attempt to write something as complex as a chess program
first build an Array Move Generator. On the plus side, an Array Move Generator is easier to program and debug. It also "makes sense"
to think in terms of an Array Move Generator, since the computer instructions used to encode the program closely resemble the process a human
player might use to do the same thing. On the minus side, an Array Move Generator is usually slower than a Bitboard Move Generator.
All of this was mentioned because Gothic Chess, with an 80 square board, is even more difficult to implement as a Bitboard Move Generator. There
are no 80-bit operating systems, and the types of 80-bit instructions that are needed for maximum speed of execution are just not available.
Writing code to handle the data as three discrete packets of 32-, 32-, and 16-bit chunks is so tedious that it almost defies a rational explanation.
What is needed is an 80-bit emulation core, and this is very difficult to design.
Just designing such a core was a huge project unto itself. Once the core was completed, the rest of the game shell had to be designed around it.
Using something known as 45-degree rotated bitboards for an 80 square board and intelligent 80-bit register shifts, the Gothic Chess engine
was hand crafted. The result was the equivalent of a Nitrous Oxide-powered dragster.
Gothic Vortex is capable of performing very deep searches in only a matter of seconds!
|
|
|
|
There is a way to "force" exchanges to occur where the "weakest piece" captures the "strongest piece" in positions where potentially
long sequences of trades take place. When there are more than one way to capture, you want to look at situations where "pawn takes queen"
before you examine options such as "queen takes pawn".
The reasoning is that if a position is entered where an opponent's pawn can take your queen, there is a strong chance that you
have blundered, unless you can take back more material, or deliver checkmate. The Static Exchange Evaluator (SEE) provides a
"searching mechanism" whereby such trades can be examined very quickly without having to evoke your move generator!
This amazing piece of technology is very fast, especially when you consider how "expensive" it is to call the move generator.
By "blitzing through" exchanges statically until no threats of captures, checks, or mates occur, the program will not misevaluate
a position due to hanging pieces. This drastically reduces the size of the game tree by pruning away the "ridiculous" positions
that might otherwise occur.
In the end, this allows the program to search more deeply in less time.
|
|
|
|
In "regular" chess, the Queen is basically given the movements of a Rook or a Bishop, residing on one square,
instead of two. in Gothic Chess, with the Chancellor behaving like a Rook or a Knight, you might think it is about
equal in strength to the Queen. Since the Archbishop combines the powers of a Bishop and Knight,
one's first thoughts are to automatically assume it is always less powerful than a Chancellor.
Experience has shown us that you cannot apply absolutes to these major pieces in Gothic Chess. There are positions
where an Archbishop can dominate the board, and it is stronger than either a Queen or a Chancellor in the same position.
This is due to the fact that the Archbishop is capable of delivering a checkmate unassisted! It is the only piece that
can do this (even the Queen needs the help of another piece to deliver mate.) There are also classes of positions where
the Chancellor combines with a Bishop to deliver unstoppable, wheeling checks. It would be much better not to trade
the Chancellor for a Queen in such positions. Of course, the Queen can dominate in the open or semi-open playing field
in most cases.
The question is, should you trade an Archbishop and Pawn if you can win a Chancellor? How about Chancellor and Pawn for
a Queen? Archbishop and Knight for Queen and Pawn? Chancellor and Bishop for Archbishop and Rook?
Gothic Vortex makes uses of its intelligent selection criteria to determine which of these trades should be taken,
and which should be avoided, throughout the course of the game.
|
|
|
The Principal Variation Search (PVS) is a means of getting a small performance improvement out of the alpha-beta algorithm.
Any node in an alpha-beta search belongs to one of three types:
Alpha node: Every move you search will have a value less than or equal to alpha, meaning that none of the moves in here will be any good, probably because the starting position is bad for the side to move.
Beta node: At least one of the moves will return a score greater than or equal to beta.
Principal variation (PV) node: One or more of the moves will return a score greater than alpha (a PV move), but none will return a score greater than or equal to beta.
Sometimes you can figure out what kind of node you are dealing with early on. If the first move you search fails high
(returns a score greater than or equal to beta), you've clearly got a beta node. If the first move fails low (returns
a score less than or equal to alpha), assuming that your move ordering is pretty good, you probably have an alpha node.
If the first move returns a score between alpha and beta, you probably have a PV node.
Of course, you could be wrong in two of the cases. Once you fail high, you return beta, so you can't make a mistake about
that, but if the first move fails low or is a PV move, it's still possible that a later move will come back with a higher value.
The PVS makes the assumption that if you find a PV move when you are searching a node, you have a PV node. It assumes that your
move ordering will be good enough that you won't find a better PV move, or a fail-high move (which would cause this to become
a beta node), amongst the other moves.
Once you've found a move with a score that is between alpha and beta, the rest of the moves are searched with the goal of proving
that they are all bad. It's possible to do this a bit faster than a search that worries that one of the remaining moves might
be good. If the algorithm finds out that it was wrong, and that one of the subsequent moves was better than the first PV move,
it has to search again, in the normal alpha-beta manner. This happens sometimes, and it's a waste of time, but generally
not often enough to counteract the savings gained from doing the "bad move proof" search referred to earlier.
If no PV move has been found, "AlphaBeta()"
is recursed normally. If one has been found, everything changes. Rather than searching with a normal (alpha, beta) window, we
search with (alpha, alpha + 1). The premise is that all of the searches are going to come back with a score less than or equal
to alpha, and if this is going to happen, the elimination of the top end of the window results in more cutoffs. Of course,
if the premise is wrong, the score comes back at alpha + 1 or higher, and the search must be re-done with the wider window.
Generally speaking, the PVS will offer a 10 percent improvement over alpha-beta.
|
|
|
If you are about to start searching a position, how deep should you search it? It is difficult to predict in advance how
long a search will take, since the time it takes to complete a search of depth D is dependent upon factors that might not
be obvious. In a complex middlegame position, you might search not very deeply at all, while in an ending you might search
significantly deeper, and in some king+pawn endings you might be able to search 60 plies.
An idea is to search to depth one. If this search completes in less than the amount of time allocated, search again to depth two.
And then to depth three. And so on, until you run out of time.
This all but guarantees pretty good time usage. If you are able to perform a deep search quickly, you'll continue along and
search even deeper the next time, and perhaps you'll finish that. If the position is more complicated than you expected, you won't
finish many plies of search, but you will have at least some legal move to play, since it's almost impossible to not finish
a 1-ply search.
This idea is called iterative deepening, because what happens is you iterate the search, going one ply deeper each time.
It might seem surprising that this is actually an extremely efficient way to search. If you enhance alpha-beta so that it
returns a principal variation, you can feed this principle variation back into the next iteration of search.
For instance, if a one-ply search indicates that 1. d4 is the best move, you will search 1. d4 first when you perform a two-ply
search. If that returns the line 1. d4 d5, you will search that line first when you perform a three-ply search.
The effect of this is that the first line you search tends to be good. Alpha-beta is extremely sensitive to move ordering.
If your move ordering is bad, your Gothic Chess branching factor will be about 50. If your move ordering is good, the branching
factor will be closer to 3. This is because your principal variation from the previous iteration of the search function tends
to be very good.
Iterative deepening provides you with a simple means of interrupting the search when you run out of time, and it makes your
search more efficient.
|
|
|
Search extensions are vital to any good quality program. However, when implemented badly they can be detrimental to the
overall performance, causing your search tree to increase in size enormously with few advantages. One of the great problems
is how to search the bad moves to a shallower depth and the good moves more deeply. Of course, it is very difficult to predict
the former. Nobody knows which moves will turn out to be good before you have played them.
However, searching the good moves to a greater depth is altogether more simple. You can't tell if a move is going to be good,
but you can certainly tell if it looks as if it might become interesting. This is the whole principle of search extensions.
In a standard tree search, the recursive search procedure is called until the maximum depth is reached then we look at the
quiescence search. However, for certain nodes, the quiescence search will not find the tactical gain, and we would be much
better off just extending the main search a little more so that we can see if these moves develop into something interesting.
One important addition is the idea of fractional ply extensions, which involves storing the depth in multiples of some large number,
say 100. In this scheme, a depth increase of 100 is equal to one ply. This way, if a search extension is not quite interesting enough
to merit an entire extra ply extension, you just increment the "extension depth" by 50. When two of these extensions happen
to occur in the same branch you will get an extra 'whole' ply of extension.
Gothic Vortex uses the fractional (as well as "whole") search extension technique for the sceanrios shown below:
Check Extensions
If the side to play is in check then extend the search by one ply.
This improves tactical strength dramatically.
Checkmate detection is drastically improved.
Recapture Extensions
These occur when one side plays a capture and then the opposition recaptures with an identical value piece.
This move is pretty much forced, so we search deeper.
Gothic Vortex will extend the depth differently depending on the piece captured.
Singular Reply Extensions
If there is only one legal move in a certain position then extend.
The extra cost is minimal as the branching factor at this node is 1.
Can be used in addition to check extensions to find checkmates very quickly.
Threat Extensions
These are used with NULL move search
If NULL move search returns a checkmate against Vortex, then there is a threat nearby.
Extend the search so that we can find the best way to avoid it.
Pawn Push & "Pawn Race" Extensions
If a pawn is pushed to the 7th rank, or promoted, then extend.
If one or more pawns can potentially "outrace" the other side's pawns, then extend.
This helps spot winning tactics in the endgame from a great distance
|
|
|
The history heuristic is another technique that can be used to improve move ordering. In a table indexed by from and to squares, statistics
are maintained for moves that produce good cutoffs. This table of values is used in the move ordering sort
(together with other information such as capture gains/losses) in order to produce a "statistically likely" cutoff, as
these moves have, historically, achieved this result. As these from-to moves are tested for legality, then applied to the position,
if a cutoff is achieved, its "value" is increased so that it moves higher up in the list.
|
|
|
The killer heuristic is a technique for improving the efficiency of alpha-beta pruning.
Alpha-beta pruning works best when the best moves are considered first. This is because the best moves are the ones most
likely to produce a cutoff, a condition where the program probably knows that the position it is presently
considering could not possibly have resulted from best play by both sides and so need not be considered further.
The killer heuristic attempts to produce a cutoff by assuming that a move that produced a cutoff in another branch of the
game tree at the same depth is likely to produce a cutoff in the present position. It supposes that a move that was a
very good move (a "killer") from a different position might also be a good move in the present position. By
trying the killer move before other moves, the program can often produce an early cutoff, saving itself the
effort of considering or even generating all of the legal moves from a position.
In practical implementation, programs frequently keep track of two killer moves for each depth of the game
tree and see if either of these moves, if legal, produces a cutoff before the program generates and considers the rest of
the possible moves. If a non-killer move produces a cutoff, it replaces one of the two killer moves at its depth.
|
|
|
A relatively new technique designed specifically for Gothic Chess pieces, the Frequency Filtering Heuristic will prevent
miniature "tree explosions" in positions where Chancellors and Archbishops have many legal moves. Since these new pieces
"hop" as well as "slide", then can navigate around pawns and continue to areas where they have many more legal moves. This
tends to bloat the game tree. By tracking the frequency that designates how often each of these pieces have moved, a Fibonacci-like
penalty accumulator can curtail their over-zealous activity.
|
|
|
Gothic Vortex uses three different hash tables to store information about positions that occur frequently during the
look-ahead search. By storing the score for these positions, when the position occurs again from a different move order
(transposition), the program can rerieve its value from the table much more quickly then recomputing its value from the
evaluation function.
The primary hash table stores the "most recently seen" positions encountered at the leaf nodes deep
in the search. The scores for these positions are hashed and stored, saving the time it would otherwise require for an
expensive re-evaluation of the position. The secondary hash table stores positions that occur as the search retreats
to lower levels, generating more positions from the new "baseline". This technique prevents older "root positions" from
being replaced by the rapidly changing primary hash table entries. Without this, each retreat to a prior depth to generate
more positions would result in less efficient use of the memory reserved just the one hash table. The pawn hash table stores
the information about the pawn chains. Since pawns tend to become "fixed" for long periods of time as non-pawns moves
are being generated, retrieving these values is very fast and efficient, since it is used over and over again.
The primary and secondary hash tables are effective "tree-reducers", while the pawn hash table is a great time-saving technique.
|
|
|
Gothic Vortex currently runs on the Windows platform. As it is high perfomance software, there are some minimum
requirements that must be met for the software to function at its peek efficiency.
Operating Systems Supported
Windows 98
Windows NT
Windows 2000
Windows 2000 Professional
Windows XP
If you do not see an operating system listed above (such as Windows ME) there is a very good reason for it.
The software will not run under that environment!
Minimum RAM & Hard Disk Space Required
|
Gothic Vortex Product
|
Minimum RAM
|
Minimum HD Free
|
|
Gothic Vortex Gold III
|
64 MB
|
12 MB
|
|
Gothic Vortex Gold IV
|
512 MB
|
200 MB
|
|
Gothic Vortex Gold V
|
2 GB
|
63 GB
|
|
|
|
|