Kids Cube/5_Logic.iso/flip47/flip.doc

Text File | 1993-04-28 | 21KB | 387 lines

     Flip-it and Octothello.
    -------------------------
  Copyright PC Solutions 1991, All rights reserved.

  This is documentation for the PC-SOLUTIONS games of FLIP-IT and
OCTOTHELLO. It may only be distributed together with the shareware
versions of those programs in a complete, unaltered form - other uses
require explicit permission from PC SOLUTIONS first.
  [NOTE:- FLIP-IT and OCTOTHELLO are now integrated as 1 program - the
Octothello game is selected by selecting corner-shape 3 on the title
screen - some shareware versions of FLIP-IT automatically start in this
mode. For normal OTHELLO, select corner-shape zero.]

  Octothello/FLIP-IT are variants on the board game REVERSI (or
OTHELLO). There have been many versions of OTHELLO published in magazines
and shareware libraries, and yet they all play VERY weak games -
OCTOTHELLO is probably the first REALLY decent OTHELLO game to be
released as shareware. OCTOTHELLO is much, much more than OTHELLO - you
can set it for normal OTHELLO if you like, and it will play a VERY good
game - or you can select hundreds of different board and corner shapes
and sizes, with each variation having its own subtleties!
  As I have said, there have been many OTHELLO programs written, since
the rules lend themselves to computer implementation. Most programs just
seem to play by trying to flip over the maximum number of pieces at each
move - but this is a recipe for disaster if used against someone with
knowledge of the game. Have a go at playing OCTOTHELLO like that, then
when you have lost by about 60 disks to 4, come back and read how to
REALLY play! I believe these weak programs have lead to OTHELLO being
looked down upon a bit by some of the more hardened computer users, and
yet OTHELLO can sometimes surpass CHESS in subtlety and depth!
  Let us start with Normal OTHELLO. The game starts with the following
board:-
                                     DIAGRAM 1
         A  B  C  D  E  F  G  H
      1  -  -  -  -  -  -  -  -
      2  -  -  -  -  -  -  -  -
      3  -  -  -  +  -  -  -  -      O  -  White
      4  -  -  +  O  x  -  -  -      x  -  Black
      5  -  -  -  x  O  +  -  -      Black to play.
      6  -  -  -  -  +  -  -  -      (+ indicates legal black moves)
      7  -  -  -  -  -  -  -  -
      8  -  -  -  -  -  -  -  -

  The rules that define a legal move are very simple when seen in real
play, but they sound complex when written down, so it is a good idea to
run FLIP-IT/OCTOTHELLO and try an auto-demo to get the idea. Anyway, you
may move to a vacant square if it is adjacent to an opponents piece, and
if by moving to that square you bracket a horizontal/vertical/diagonal
line of your opponents piece(s) between the square you are moving onto
and a square you already occupy. All of the opponents pieces bracketed or
trapped in this way are captured and are flipped over to your colour. As
I said it is much easier to see this by example - in Diagram 1 above
black can move to the squares marked '+' - for instance if he moves to C4
he 'traps' whites piece at D4 between his at C4 and E4, and D4 becomes a
black piece.
  If a player has no legal moves available he must PASS a turn, allowing
his opponent to take another turn. However if he has a legal move
available he MUST take it - you may only pass when you have no moves.
  The game ends when all 64 squares are full up, or when neither player
has legal moves available - even though there may be some vacant squares
left. Once the game ends, the player with the most pieces wins - or
occasionally there is a draw if both players have the same.
  So, because the object of the is to finish with more disks than your
opponent, some people translate this as meaning "Gosh, lets flip over as
many disks as possible with every move." leading to disaster. You could
imagine that the following diagram could result at the end of a game
where White has been capturing everything in sight..

         DIAGRAM 2             O = White, x = Black, Black to play

         A  B  C  D  E  F  G  H
      1  -  O  O  O  O  O  O  -
      2  O  O  O  O  O  O  O  O
      3  O  O  O  O  O  O  O  O
      4  O  O  O  O  O  O  O  O
      5  O  O  O  x  O  O  O  O
      6  O  O  O  O  O  O  O  O
      7  O  O  O  O  O  O  O  O
      8  -  O  O  O  O  O  O  -


  Black has only one disk on the board at D5, with the four corner
squares empty and white holding the remaining 59 squares. And yet, if you
play out the game, you will find that black wins by 40 disks to 24! IE.
Black plays A8, White PASSES, then A1, PASS, H1, PASS, H8. While this is
an extreme example, this sort of chaotic turn-about often occurs in the
last few moves of an othello game, particularly when a master player
crushes a novice. The critical factor in the above example are the CORNER
SQUARES. Whites mass of pieces were totally unstable because he didn't
have possession of the corners. These are referred to as STABLE SQUARES -
 once you have a corner it can never be recaptured by your foe, and also
other adjacent pieces of your colour can also become stable, forming an
unassailable fortress from which you can attack the rest of the board.
 So if, for instance, in Diagram 2 White had already occupied, say, A1,
the whole mass of 28 pieces up and left of the A8-H1 diagonal become
stable white territory, and white would win the game.
  By implication, it is bad to occupy the squares adjacent to the corner
squares before you have captured the corner, because you may be offering
your opponent the option to get the corner, either immediately or later.
Consider the following position:-












         DIAGRAM 3             O = White, x = Black, White to play

         A  B  C  D  E  F  G  H
      1  -  -  -  -  -  -  -  -
      2  -  x  -  -  -  -  -  -
      3  -  -  x  O  O  -  -  -
      4  -  -  -  x  O  -  -  -
      5  -  -  -  O  x  -  -  -
      6  -  -  O  -  -  x  -  -
      7  -  -  -  -  -  -  -  -
      8  -  -  -  -  -  -  -  -

  Black has, rather foolishly, just moved to the B2 square. While White
cannot capture the corner immediately, all he needs to do is to move to
F5 (capturing E5), and wherever black moves he cannot recapture E5, so
White will be able to capture A1 on the next turn. The square at B2, and
also those at B7, G2 and G7 are referred to in Othello terminology as the
X-SQUARES, and are generally considered very bad to occupy, especially in
the early/mid game. While there are some particular positions towards the
end-game where an "X-SQUARE SACRIFICE" can actually win you the game, you
should avoid these squares unless you know what you are doing.
  The Edge squares adjacent to the corners, (B1, A2, G1, H2, A7, B8, H7
and G8) are called the C-SQUARES, for rather obscure historic reasons.
The position with C-SQUARES is more complex - while they may offer your
opponent future access to a corner, there are some positions where it is
relatively safe to take these squares, particularly towards the end of a
game. However it is still wise to avoid occupying a C-SQUARE unless you
are sure it is a safe position. Of course once you actually occupy a
corner all this changes, and it becomes desirable to capture the adjacent
C and X-SQUARES - these will now be stable and unassailable.
  OK, now up to this point I have discussed ideas that may already be
known, at least to some extent, to people who have picked up OTHELLO from
some of the other shareware OTHELLO offerings. I now move to ideas that
are less commonly known outside the realm of serious OTHELLO players, and
yet are critical to actually winning games against strong opponents.
  So far, you understand that your ultimate objective is to get stable
corner (and then surrounding) squares - but what strategy should you
adopt in the early-mid game, before you get near these squares? Well, if
you think about it, you want to FORCE your opponent to capture weak
squares such as (say) an X-SQUARE, enabling you to capture a corner -
after all he probably will not make such moves voluntarily. However if
you can engineer a situation where your opponent only has one or two
legal moves available, and these moves are to weak squares, he will have
no choice! Here we come to an absolutely critical concept in OTHELLO -
MOBILITY. The MOBILITY of a player is simply a count of the number of
legal moves he has available - a subset of this, what you could call
GOOD-MOBILITY, is a count of legal moves excluding bad C and X-SQUARE
moves that result in the opponent getting the corner. Consider the
following:-





         DIAGRAM 4             O = White, x = Black, Black to play

         A  B  C  D  E  F  G  H
      1  -  -  O  -  -  -  -  -
      2  -  -  O  O  O  O  -  -
      3  O  O  x  x  x  O  -  -
      4  O  O  x  O  O  O  -  -
      5  O  O  O  O  x  O  -  -
      6  -  -  O  O  x  O  -  -
      7  -  -  O  x  O  O  -  -
      8  -  -  O  O  -  O  -  -

  Here all black needs to do is move to E8, effectively blocking whites
last decent move. Now white has only one move left, and he HAS to move to
B2, allowing black to get A1. By capturing a corner this early in the
game, black should have no problem in forcing a win. Take a note of the
formation after blacks E8 move - all of blacks pieces are surrounded by
white ones (except C3), and white occupies all the peripheral or frontier
pieces. This is called CENTRAL CONTROL, and it is very desirable to have
this sort of formation - the more peripheral squares you have, the more
moves you are offering your opponent!
  While in the above example disaster was just one move away for white,
the strategy for whittling away at your opponents stock of good moves
holds out for the longer term as well. If you watch a game between a weak
player and an expert, and made a note of the mobility after each move,
you will often see the expert players mobility creep up, while that of
the weak player diminishes to a point where he literally has no decent
moves at all.
  So what long term strategy increases your mobility? Here we come to one
of the most shocking truths about OTHELLO - because while the ultimate
goal is to get more disks than your opponent, the best way to win is to
actually keep your disk count LOW in the early and mid game! This is
called EVAPORATION strategy, and can be translated at its simplest as
trying to flip over the FEWEST number of opponents disks at each move.
The logic behind this is simple - the more disks you have on the board,
the more mobility you are ultimately offering your opponent. However we
can refine this strategy further, since it is clearly worst to flip over
peripheral (rather than central) pieces, because the more peripheral
pieces you have, the more moves you are offering your opponent. A move
that doesn't flip over many (or any) peripheral squares is called a QUIET
move, and this will be illustrated in our next example. Incidentally note
that evaporation doesn't apply once you start capturing corners, because
your tactics will then be to MAXIMISE your STABLE (ie. unflippable) piece
count.
  Another feature of the Diagram 4 is whites wall of pieces from F2 to F8
- it is considered very bad to form an unbroken peripheral wall like this
since white has no options to move into the territory in the G and H
columns. Similarly once the wall has been formed, black should avoid
breaking up the wall by cutting across it - this would let white off the
hook. Consider blacks options in Diagram 5:-




         DIAGRAM 5             O = White, x = Black, Black to play

         A  B  C  D  E  F  G  H
      1  -  -  O  O  O  O  -  -
      2  -  -  O  O  -  -  -  -
      3  -  -  O  O  O  O  -  -
      4  -  -  x  x  O  O  -  -
      5  -  -  x  x  O  O  -  -
      6  -  -  O  O  x  x  -  -
      7  -  -  O  O  -  -  -  -
      8  -  -  -  -  -  -  -  -

  Compare two of blacks moves, E2 and F2. From the point of view of
evaporation they are the same - they flip over the same number of disks.
However note that E2 only flips over central pieces, and only creates one
new white move at F2. By comparison, F2 flips over a whole mass of
peripheral squares E3,F3,F4,F5, creating no less than 6 new white move
options - and sealing off a similar number of his own move options to
boot! What's worse, he has created a wall of pieces from F2 to F6, and is
in a pretty bad way.
  It is important to try and see the effects of tactics like mobility and
evaporation at depth. Consider the following:-

         DIAGRAM 6             O = White, x = Black, Black to play

         A  B  C  D  E  F  G  H
      1  -  -  -  -  -  -  -  -
      2  -  -  -  -  -  -  -  -
      3  -  O  O  -  x  -  -  -
      4  x  O  x  O  O  O  O  -
      5  O  x  x  x  x  x  -  -
      6  O  O  O  O  O  O  -  -
      7  -  -  x  O  O  -  -  -
      8  -  -  x  -  -  -  -  -

  Black can force a corner capture thus:- A7, E2, A3, G6, A2, and white
now only has B7, conceding A8 to black. You will need an OTHELLO board to
play this through - or the full version of FLIP-IT, which allows the
setting up and playing through of positions.
  Let us consider another category of OTHELLO squares - the EDGE squares.
Even though these squares are peripheral, occupying them does not
directly create moves for your opponent, since he cannot move 'beyond'
the edge and flip them! So, on the face of it, occupying a wall of pieces
along the edge of the board does not seem bad, and to a certain extent
this is true. However you should be wary of occupying edge territory too
early in the game - it can tend to make subsequent moves 'flip' over more
non-edge pieces than you want to, in other words it works against your
evaporation and mobility in the long run.
  As mentioned earlier, the edge squares adjacent to the corner (the C-
SQUARES) can be dangerous to occupy, since they sometimes offer your
opponent an option to form a tactical trap, allowing him to get a corner.
Consider this position:-


         DIAGRAM 7             O = White, x = Black, White to play

         A  B  C  D  E  F  G  H
      1  -  x  -  -  -  -  -  -
      2  -  -  x  x  O  -  -  -
      3  -  -  O  O  O  -  -  -
      4  -  -  O  O  x  O  -  -
      5  -  -  x  O  x  -  -  -
      6  -  -  -  O  -  -  -  -
      7  -  -  -  -  -  -  -  -
      8  -  -  -  -  -  -  -  -

  Black has just taken an isolated C-SQUARE, B1. If white now takes E1,
then whatever black does (he cannot move C1 or D1) white can go C1! Now
black must lose the corner - if he goes D1, white can still simply take
A1. Isolated C-SQUARES like that are the worse - the situation is not so
bad when you already occupy some of the edge squares. Even then there are
dangers:-

         DIAGRAM 8             O = White, x = Black, White to play

         A  B  C  D  E  F  G  H
      1  -  -  O  O  O  O  O  -
      2  -  -  O  x  O  O  -  -
      3  -  x  x  x  O  O  -  -
      4  x  O  O  O  O  O  -  -
      5  x  x  x  x  x  O  -  -
      6  x  O  O  x  x  O  -  -
      7  -  -  -  -  -  -  -  -
      8  -  -  -  -  -  -  -  -

  Here black can play B2! Now if white replies with A1, black can take a
toe hold at B1, and no matter where white goes, black can take H1 and not
only get a corner, but also a whole edge of stable squares from B1 to H1.
Note that blacks B2 move was to a normally dangerous X-SQUARE, and this
is one of the occasions when an X-SQUARE and corner sacrifice is a
winning tactic. Whites pieces from C1 to G1 are called an UNBALANCED
EDGE, and are dangerous because white only occupies one of the C-SQUARES
- if he already had B1, he would not be in danger. While unbalanced edges
are not always bad, they should still be avoided if at all possible.
  There quite a lot of different tactical edge traps, along similar lines
to the above positions. I don't have space to cover all this here - see
below if you want to get more OTHELLO material.
  As the very end of the game approaches, the value of the corner squares
diminish and the actual piece count becomes more relevant - particularly
stable disk counts. In the last few moves of the game you simply want to
flip over the maximum number of disks RELATIVE TO YOUR OPPONENT - trying
to see this is called DISK-COUNTING, and is something that humans are bad
at, and computers are good at! FLIP-IT can sometimes execute PERFECT play
over the last twenty or more moves of the game, based simply on counting
pieces for all possibilities!
  General rules of thumb for the end-game are hard to come by, and again
this is better served by a more comprehensive OTHELLO book. There will be
more extensive notes and documents with the full version of FLIP-IT - if
you got this document with the shareware version, you'll need to get the
full version to progress. I can also recommend an excellent book,
"OTHELLO, BRIEF AND BASIC" - this is available from:-
  The British Othello Federation, 62 Romsey rd, Winchester SO22 5PH.
    They also do a newsletter - for 5 pounds/year - send an SAE for details.
  Other Othello newsletters and clubs:-
    FFO, BP 147, 75062 Paris, Cedex 02, France.
    Othello Quarterly, 920 Northgate av,Waynesboro,VA 22980,USA

     FLIP-IT and OCTOTHELLO specific notes and bits..
    --------------------------------------------------
  You may have seen an early version (FLIP14.EXE) on some computer-
magazine cover disks - ignore the level of play of that program - the
latest version is immeasurably stronger. I was able to apply much of what
I learnt from writing SAGE-DRAUGHTS (Probably the strongest commercially
available CHECKERS program) to writing FLIP-IT. In particular, a fast,
deep, lightweight search algorithm seems to work better than trying to
load the program with too many human-play derived parameters - if the
program is intelligent enough to search the right lines it can figure out
most of the traps and combinations for itself based on a few simple
evaluations like corner squares, stable squares, evaporation and
mobility.
  One feature I have preserved from SAGE DRAUGHTS is the IQ system for
calculating depth-of-search, rather than the more traditional 'ply'
method. This is based on various factors, such as mobility (thus deep-
scanning critical combinations with low-mobility), and it averages out to
about 9 points per ply - however it will search some combinations much
deeper. The search iteratively deepens in steps of 20 points, however
this amount is fine-tuned according to the amount of time in hand.
  Another innovation I have introduced into FLIP-IT is the ability to try
different board sizes and corner shapes. Since the stable corner squares
are so critical to OTHELLO, the game play is radically altered if you
block-out some squares around the corner as non-usable. You can try this
yourself on a normal OTHELLO board - try blocking out squares A1,A2,B1,
and the same in the other 3 corners, and you get OCTOTHELLO, with 8
'corner' squares! FLIP-IT has a total of 16 corner shapes selectable from
the front menu, including normal OTHELLO of course. Another fun-thing you
can do is try different board-sizes, anything from 4 by 4 up to 19 by 19.
For instance FLIP-IT can 'solve' the game on a 4 by 4 board, as resulting
in a forced win for black! By implication OTHELLO is probably a forced
win for white or black - its just a question of getting a computer to
search deep enough! Don't laugh - a Super-Computer program is getting
close to doing this for the game of DRAUGHTS (or CHECKERS), by stint of
storing billions of end-game positions! Hmm.. anyone out there got a
Cray-5 going spare?
  I have released a shareware version of FLIP-IT, however the full
version is a commercial product, and you will want to get this if you are
a serious player. The full version (On GAMES-PACK-2) has full game
replay/save/load/print features, game comment text, board edit/setup,
response time (and hence play strength) variable from 1 second up to 1
week, and very pretty CGA/EGA/VGA graphics. It also comes with other
interesting strategy games, and full documents. It costs just 9.15 pounds
inc mail (PC compatible, 5.25 or 3.5 disk), or USA customers can pay
normal cheques IN US DOLLARS for only $24 - that's including AIR MAIL and
currency conversion charges.
       Cheques, P.O.'s and Enquiries to:-
   PC SOLUTIONS, Dept OTH, PO BOX 954, Bournemouth BH7 6YJ, ENGLAND.