{ WO.PAS -> WIPEOUT (Othello/Reversi Game)

  Matthew J. Doucette
  12:18am, February 2nd, 1998

  Original Beginning: November 6th, 1997, just after proposing challenge to
                      Andre Trudel in the morning to give us an A+ in
                      COMP3613 AI if we can make an intelligent game playing
                      program.  Scrapped old start code for a new beginning.


  --------------------- RULES ---------------------

  - Black moves first, white moves second.
  - Each player has 30 stones, black on one side, white on the other.
  - Every moves must flip, or reverse, an opponents stone.
  - If you can not flip an opponent's stone, then you must pass.
  - Opponent's stones are flipped when they are caught in-between the stone
    just played, and other stones of the current player's color.
  - If nobody can move, then the game is over.
  - Whoever has the most stones of his/her own color wins.
  - Empty squares default to winner.  (All wipeouts are 64-0 wins, hence the
    name of the program.)
  - Initial board position:

    кФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФП B = Black stone
    Г   Г   Г   Г   Г   Г   Г   Г   Г W = White stone
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД . = possible first moves for black
    Г   Г   Г   Г   Г   Г   Г   Г   Г
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
    Г   Г   Г   Г . Г   Г   Г   Г   Г
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
    Г   Г   Г . Г W Г B Г   Г   Г   Г
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
    Г   Г   Г   Г B Г W Г . Г   Г   Г
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
    Г   Г   Г   Г   Г . Г   Г   Г   Г
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
    Г   Г   Г   Г   Г   Г   Г   Г   Г
    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
    Г   Г   Г   Г   Г   Г   Г   Г   Г
    РФФФСФФФСФФФСФФФСФФФСФФФСФФФСФФФй


  --------------------- IDEAS for improvement ---------------------

  - When human attempts illegal move make an error sound and respond with:
    "During the time that you thought that move was legal, I already
    contemplated 485,639 moves."

  - total game time / 30 = time per move
    (although with passes the amount of moves is greater than 30.

  - Should have a different end game search, once end game is within
    search reach, therfore playing perfectly.

  - When a player must pass, the null move and the next move should NOT
    count towards plys in the search tree

  - When a player only has one possible move, that move and the next move
    should NOT count towards plys in the search tree.

  - F1 brings up a scrollable help screen at any time (like multitasking)

  - animations for stones being flipped

  - easy/worse levels of play
    - do same calculations but do worst move
    - random move
    - random of top n/.../3/2 moves (n=worse play, 1=best

  - strong evaluation fuction consists of:
    - mobility
    - potential mobility
    - precalculated edge values

  - OPTIMIZATION: while testing is possible move is legal, depending on where
    the move is on the board, it may be faster to start with a specific
    direction.

      Examples - Moves on top TWO rows of board aren't found checking the
                 upward directions. Likewise for all 4 edges.

    Perhaps separately store direction ordering for all 64 squares and
    amount of directions.  (Corners only have 3 directions to be checked)

      Implement:  1) store 64(squares)x8(8 directions): store directions: [1,2,3,4,x,x,x,x]
                     store 64(squares)x1(amount):           store amount: [4]
                  2) store 64(squares)x2(start direction,amount):          [1,4] means 1,2,3,4


  - Move Ordering.  Depending upon the move tested first in Alpha-Beta
    it will prune more of the tree if the best move is found first.  Do
    move ordering like this:  Have an array that says which order
    to check for legal moves.  For example [1,8,56,64,....] instead
    of [1,2,3,4...]

  - figure out maximum amount of moves possible (in search tree), this
    would speed up the search as it would allow the use of a smaller
    movelist array.


  - add empty sqaure count in board record.  **ELIMINATES EXTRA 2-PLY
    TO SEE 2 NULL MOVES TO SEE END OF GAME**

  - with move ordering, make an array [0..59] pointing to all the empty
    squares, ordered by best move first, but DECREASE SIZE OF ARRAY as
    moves are made, speeds up thinking in end game!!!!!!!

  - instead of using 'et' procedure, count ticks myself with a variable
    preset to 0, and incremented every time timer is called.

  - once a came to a situation where WipeOut had this for move values:

    ??: -2
    ??: Lose by 64
    ??: Lose by 64
    ??: Lose by 64
    ??: Lose by 64
    ??: Lose by 64
    ??: Lose by 64
    ??: Lose by 64

    Then it extended it's depth and pointlessly searched through the
    'lose by 64's.  All loses should be marked at loses, not looked
    through again, BUT ALSO NOT IGNORED, as this might happen:

    Depth 6:

    ??: -2
    ??: Lose by 40

    Then through iterative deepening:

    Depth 7:

    ??: Lose by 64
    ??: Lose by 40

    and thus the best move is the lose by 40.

  --------------------- PROGRESS ---------------------

  * Testing had been performed every step of the way.
  * Research done before coding has not been included.

  02/02/98: ---WO---
            - Othello Game Research
            - Main Screen Design
            - Wrote up comments you see (above) here
            - 640x480 Reversi board on screen
            - Board storage designed: (one-dimensional array,
                                       0 = black stone
                                       1 = white stone
                                       2 = empty square
                                       3 = possible moves/empty square)
                    кФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФП
                    Г 0 Г 1 Г 2 Г 3 Г 4 Г 5 Г 6 Г 7 Г 27,36 := 1
                    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД 28,35 := 0
                    Г 8 Г 9 Г 10Г 11Г 12Г 13Г 14Г 15Г 18..21,26,29,
                    УФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФД 34,37,42..45 := 3
                    Г 16Г 17Г 18Г 19Г 20Г 21Г 22Г 23Г rest := 2
                    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
                    Г 24Г 25Г 26Г W Г B Г 29Г 30Г 31Г
                    УФФФХФФФХФФФХФФФлФФФХФФФХФФФХФФФД
                    Г 32Г 33Г 34Г B Г W Г 37Г 38Г 39Г
                    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
                    Г 40Г 41Г 42Г 43Г 44Г 45Г 46Г 47Г
                    УФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФД
                    Г 48Г 49Г 50Г 51Г 52Г 53Г 54Г 55Г
                    УФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФД
                    Г 56Г 57Г 58Г 59Г 60Г 61Г 62Г 63Г
                    РФФФСФФФСФФФСФФФСФФФСФФФСФФФСФФФй
            - Draw board and pieces to screen
              - TP's 640x480 graphics unit took a while to figure out


            12:18am -> 2:03am = 1hr 45mins total = 105min


  02/02/98: - board storage redesigned/implemented for efficiency:

                                       0 = black stone
                                       1 = white stone
                                       2 = empty square
                                       3 = possible moves/empty square
                                      *4 = edge = off the board

                   EEEEEEEEEE 10x10 board, (8x8 plus an outside edge),
                   EBBBBBBBBE increases speed in checking for
                   EBBBBBBBBE out-of-range board positions.
                   EBBBBBBBBE
                   EBBBBBBBBE
                   EBBBBBBBBE
                   EBBBBBBBBE
                   EBBBBBBBBE
                   EBBBBBBBBE
                   EEEEEEEEEE

                But, as long as the 8-direction check for every outside
                square "B" still lands on an edge "E" through wrap-around,
                the left and right edge can be THE SAME EDGE like this:


                   EEEEEEEEE 9x10 plus 1 = 91 element array
                   EBBBBBBBB
                   EBBBBBBBB
                   EBBBBBBBB
                   EBBBBBBBB
                   EBBBBBBBB
                   EBBBBBBBB
                   EBBBBBBBB
                   EBBBBBBBB
                   EEEEEEEEE
                   E
                                       0 = black stone
                                       1 = white stone
                                       2 = empty square
                                       3 = possible moves/empty square
                                       4 = edge = off the board
                    кФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФП
                    Г 0 Г 1 Г 2 Г 3 Г 4 Г 5 Г 6 Г 7 Г 8 Г
                    УФФФЩЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЛ
                    Г 9 К 10Г 11Г 12Г 13Г 14Г 15Г 16Г 17К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 18К 19Г 20Г 21Г 22Г 23Г 24Г 25Г 26К
                    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    Г 27К 28Г 29Г 30Г 31Г 32Г 33Г 34Г 35К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 36К 37Г 38Г 39Г W Г B Г 42Г 43Г 44К
                    УФФФКФФФХФФФХФФФХФФФлФФФХФФФХФФФХФФФК
                    Г 45К 46Г 47Г 48Г B Г W Г 51Г 52Г 53К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 54К 55Г 56Г 57Г 58Г 59Г 60Г 61Г 62К
                    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    Г 63К 64Г 65Г 66Г 67Г 68Г 69Г 70Г 71К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 72К 73Г 74Г 75Г 76Г 77Г 78Г 79Г 80К
                    УФФФШЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭМ
                    Г 81Г 82Г 83Г 84Г 85Г 86Г 87Г 88Г 89Г
                    УФФФХФФФСФФФСФФФСФФФСФФФСФФФСФФФСФФФй
                    Г 90Г
                    РФФФй


            5:54pm -> 6:24pm = 30mins


  02/03/98: - "Draw_Board" procedure finished.
            - 463 lines of code.

            12:30pm -> 12:59pm = 29mins

  02/07/98: - adjusted size of board on screen
            - "Find Legal Moves" procedure finished

            2:32pm -> 4:01pm = 1hr 29mins = 89mins

  02/08/98: - "Make Move" procedure finished

            2:00pm -> 2:46pm = 46mins

  02/11/98: - checking code with first move in legal move list.
            - error found, "Find Legal Moves" returns the same move twice
              if it flips pieces in two directions.

              FIXED in 2min!!!

              The fix was an actual optimization, because once a move is
              found to flip pieces in one direction, then there is no
              sense to check the other directions.

            4:00pm -> 4:17pm = 17mins

  02/13/98: - Friday the 13th!!!!!!!
            - added temp. code to show legal moves in "Draw Board"

            2:14pm - > 2:23pm = 9mins

  02/14/98: - User Interface implemented, user can select moves and quit.

            1:46am -> 2:20am = 34mins

  02/14/98: - improved user interface graphics

            3:04pm - > 3:08pm = 4mins

  02/20/98: ---WO2---
            - took out VGAColors array... apparently you don't need it

            11:30pm -> 11:31pm = 1min

  02/21/98: - fixed intensity of green colors

            4:05pm -> 4:15pm = 10min

  02/23/98: - allow user to choose human/computer for blach and white
            - computer now plays with random moves
            - 1019 lines of code.

            6:05pm -> 7:10pm = 65min

  02/23/98: - created matrial evaluation function
              ("simple evalution function")
            - fixed slow update of board on screen
              ( now only draws changes, instead of whole board )
            - everything test ok.
            - 1185 lines of code.

            8:21pm -> 9:51pm = 60+30=90min

  02/23/98: - fixed bug in updated board

            ???? -> ???? = 2min

  02/24/98: - program now 'sees' end of game, by using a
              "consecutive null move" variable when it reaches 2.
            - score and side-to-move indicator is drawn/updated on screen
            - 1288 lines of code

            1:28pm -> 2:35pm = 60+7=67min

  02/24/98: - fixed up game over situation with less than 64 stones
              played.  (Empty squares go to winner.)
            - designed anti-aliased stones, but could hardly tell
              the different in 640x480 resolution so scrapped idea

            12:35am -> 1:18am = 43min

  02/25/98: ---WO3---
            - fixed up "byte" to "10..80" for proper range checking
            - fixed up positioning for messages to user (ex. "Game Over")
            - setup thinking information on screen
            - setup program for depth first search

            9:13pm -> 10:21 pm = 60+8=68min


  02/26/98: - Depth 0 Alpha Beta search implemented (enables Depth 1 play)
            - Plays much stronger than random moves!
              but still easy to beat:
                1st: I lost: 12-52 (I was not thinking at all)
                2nd: "  won: 52-12
                3rd: "   "   53-11
                4th: "   "   56-08
                5th: "   "   50-14
                6th: "   "   62-02
            - now picks randomly if more than one move ties for best move.
            - 1649 lines of code.

            1:29pm -> 2:55pm = 60+26=86

  02/26/98: - beat ply-1 search 64-0 in 1-sec/move game
            - starting to code full alpha beta

            5:46pm -> 6:42pm = 60-4=56min

  02/26/98: - Depth>0 Alpha Beta search implemented
              (all in exception to null move handling)
            - testing on Depth=2
            - testing on Depth=4
            - appears to work properly,
              more testing needing,
              null move handling a neccesity.

            6:52pm -> 7:24pm = 32min

  03/04/98: - added 'last move null' to board position
            - fixed up 'double moves' and 'game over' in alpha-beta,
              lot of debugging and testing, appears to work fine now.

            9:00pm -> 12:14pm = 3*60+14min = 194 min


  03/05/98: - added empty square count (allows change of depth for endgame)
            - set depth to variable (instead of a constant)
            - implemented perfect endgame play (for last 10 moves)
            - tested on Moses:

              Moses lost twice: #1 53-11
                                #2 ??-?? (resigned)

            12:50pm -> 2:06pm = 136 min

  03/06/98: ---WO4---
            - added positional evaluation function
              (endgame will still use material evaluate for perfect play)


            12:30pm -> 1:00pm = 30 min

  03/07/98: - tested at depth 5, perfect play 10 squares under,
              with new positional evaluation function:

              White to move, 11 squares empty, seen win by 54 in this pos:
              Computer wins by 54:  5-59 !!!


                         Black: 47  White: 6
                    ЩЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЛ
                    К   Г B Г B Г B Г B Г B Г B Г * К * = win by 54
                    КФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК . = other possible
                    К B Г   Г B Г B Г B Г B Г B Г B К     moves
                    КФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    К B Г B Г B Г B Г W Г W Г B Г B К
                    КФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    К B Г B Г B Г B Г W Г B Г B Г B К
                    КФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    К B Г B Г B Г W Г B Г B Г B Г B К
                    КФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    К B Г B Г W Г W Г B Г B Г B Г B К
                    КФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    К B Г   Г B Г B Г B Г B Г   Г . К
                    КФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    К   Г . Г B Г . Г B Г B Г . Г   К
                    ШЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭМ

                Games:

                1st: I lost:  5-59 (+54)
                2nd: I lost: 16-48 (+32)
                3rd: I  won: 36-28 ( +8)
                4th: I lost: 16-48 (+32)
                5th: I lost: 15-49 (+34)

                Plays MUCH better.  Hard to beat.

            12:56pm -> 1:37pm = 37+4=41min

  03/07/98: - printed depth to screen.
            - fixed drawing of legal moves to screen.
            - count/draw positions seen
            - count/draw leaf node positions seen
            - 2032 lines of code

            2:20pm - > 3:07pm = 47 min


  03/07/98: - added empty square count in board record
              ( gets rid of extra 2-ply check to see end of game )

            7:58pm -> 8:58pm = 60min

  03/09/98: - tested with 'checking' off and at depth 6
              (takes a while to move, over a minute)

              approx: 50,000 pos/sec

              #1: beat me 1-63!!  (selectively searched a WIN BY 54 with 19
                                   squares left!, and then seen the better
                                   win later on!!!)

            12:00pm -> 12:20pm = 20min


  03/10/98: - Testing.  Played Kato Calnen in about 5 or 6 games.  Won
              every time (first 63-1, all others by at least 40 )
            - added search extension for forced moves.  Whenever a forced
              move is encounter (only ONE move), it extends the normal depth
              2-ply (to ensure the search ends on the correct color)

            1:30am -> 2:23am = 53 min

  03/10/98: - Testing.  Played more games against it.
              Cannot beat it.  Won by 54 and 40.
            - fix printing value to screen.  Now prints "Win by 54" instead
              of "10054"
            - extending depth on forced moves sometimes leads to over
              21,000,000 positions!!!!!!  It takes about 7 minutes+
              MUST have a 'max depth cut off'
            - evaluation function now counts empty squares as winner's
              squares when it sees end of game with empty squares left.
            - 2167 lines of code.

            12:00pm -> 1:21pm = 60+21 =81min

            FIXED FORCE MOVE EXTENDED SEARCH BUGS

  03/11/98: - More testing.  Still can't beat it.


              Depth = 4
              Perfect Play = 11 empty squares and under

              #1 I lost:
              #2 I lost: 6-58
              #3 I lost: 7-57

            - fixed 'max depth' calculations.  Different from depth, max
              depth is the maximum depth reached in selective search
              extensions (right now caused by null and forced moves,
              although the null move itself is not counted)
            - fixed leaf node/pos count bug (wasn't count them both at
              end of game )
            - optimized maxdepth count
            - fixed maddepth count bug, wasn't re-setting count to 1 for
              next move (thus kept adding to the final value each time.)

            ---WO5---
            - implemented timer procedure to update screen constantly when
              computer is 'away' thinking.
            - 27 hours exactly
            - 2347 lines of code

              Depth = 5
              Perfect Play = 11 empty squares and under

              #4 I lost: by 34
              #5 I lost: by 58 (see win by 50 with 23 emtpy squares!!!)

            12:00am -> 1:30am = 90min

  03/12/98: - added pos/sec and time count
            - testing.... works!

            2:01pm -> 2:20pm = 19min

  03/12/98: - testing....
              (must fix long searches on forced moves.)
            - added no-think forced move, computer doesn't think when there
              is only one possible move.
            - speed: (AMD K6 200 Mhz MMX)
                     Approx: 104,000 pos/sec begin-middle game
                             75,000 pos/sec end-game (should use separate
                                                      incremental search)
            - test strenth:

              Depth: 6
              Perfect Play: 11 and under

              game #1: WO won by 34
                   #2: WO won by 22 (it only seen win by 10 at first)
                   #3: took too long to think.........

            - changed forced search extension to only one ply
              - this means that the side2move is NOT the same for all
                lines of thought
              - also this takes away deep lines of thought where one side
                has all kinds of moves and the other is always forced.

            - test strenth again:

              Depth: 6
              Perfect Play: 11 and under
              I'm Playing White

                   #4: WO won by 38
                   #5: WO won by 10
                   #6: WO won by 48

            - added 'xxxxx wins by xx' or 'tied game' at end game.
            - fixed small display bug.

            - test strenth again:

              Depth: 6
              Perfect Play: 11 and under
              I'm Playing White

                   #7: WO won by 48
                   #8: WO won by 14 (I had a win by 26, shows powers of
                                     perfect endgame play)

            - 2446 lines of code.

            4:00pm -> 5:38pm = 60+38=98min

  03/13/98: - iterative deepening added (but messes up perfect end game play)
              move takes < ? second, then inc(depth)
              move takes > ? seconds, then dec(depth)
            - set up separate code for end game play to fix problem above.
            - testing (fixed minute bugs, everything is ok now.)
            - 2566 lines of code

            2:35pm -> 3:44pm = 60+9 = 69min

            OVER 30 HOURS!!!!!!! 1821 min = 30.35 hrs!!!!!!!

  03/14/98: ---WO6---
            - tested on PlaySite.Com:

              highest rating: 1824  (Goal was 1800+)
            - fixed forced move bug, doesn't time at all for forced moves.
            - fixed end of game bug (under one second, sees win, kept
              searching beyond ply 60.  Made it never search beyond
              amount of empty squares.)

              Seen win by 64 with 27 empties on 486-66!!!!

            2:03am -> 3:03am = 60 min

  TOTAL:  105+30+29+89+46+17+9+34+4+1+10+65+90+2+67+43+68+86+56+32+194+136+30+41+47+60+20+53+81+90+19+98+69+60
          -----------
          1881 min = 31.35 hrs

  LINES OF CODE: 2796


            ............ SOFTWARE ENGINEERING IS OVER WITH .........
            .............. NO MORE KEEPING TRACK OF TIME ...........


  03/18/98 - touch ups:
             - took out programming info on screen
             - fixed up clock
             - fixed up clock bug, doesn't start again
               with iterative deepening
             - formatted end of game text, computer move text
             - prints out proper co-ordinated instead of 10..80
             - testing... appears to work properly.
             - printed indicator, show which move computer is thinking on
             - 2758 lines of code


             PlaySite Rating: 1861

  03/23/98 - fix 'positions seen' bug.  Was calculating leaf nodes twice.
           - WipeOut thinks 50,000 pos/sec, NOT 100,000!!!!!!!

  03/26/98 ---WO7---
           - searches for EGAVGA.BGI in current directory
             AND c:\tp\bgi directory.
           - implemented Incremental_Make_ Move, an exact copy of Make_Move
             with the return of a value.  If the move flipped 2 stones,
             then the value=3, (2 + the stone played)


  03/27/98 - decrease depth for every move, sometimes, when human plays
             white, the computer assumes that depth 7 is ok, when it would
             take over 40 seconds!!!! too long....

  03/30/98 ---WO8---
           - move ordering array created
           - implemented move ordering, worked exactly the same....,
             removed it.

  04/25/98 - first game at home (bellneck) beat WipeOut by 14,
             first win ever!!!!!!!!!!!!! (since it's 'completion')

}

{$C FIXED PRELOAD PERMANENT} {for Timer Handler procedure }
{
  Code Segment Attribute: Controls the attributes of a code segment.

  FIXED     Г The system cannot change the location of the code segment
            Г in memory.
  PRELOAD   Г The code segment loads when your program begins execution.
  PERMANENT Г The code segment remains in memory once it is loaded.
}

{ ----------------- Compiler Directives ---------------------- }

{$g+}     { generate 286 }
{$r-}     { range checking }
{$q-}     { overflow checking }
{$s-}     { stack-overflow checking }
{$n+,e-}  { 80x87 numeric coprocessor _MUST_ be present }
{$m 65520,0,655360}

uses
  dos,crt,timer,vga40,utils,graphics,graph;

const
  Initial_Depth = 1;
  Increase_Depth = 1.50;  { seconds }
  Empty_Squares_for_Perfect_End_Game_Play = 11;

  { misc }
  version = 'v0.8'; { program version }

  { Dark Colors:     Light Colors:
    ---------------------------------
    Black         0  DarkGray       8
    Blue          1  LightBlue      9
    Green         2  LightGreen    10
    Cyan          3  LightCyan     11
    Red           4  LightRed      12
    Magenta       5  LightMagenta  13
    Brown         6  Yellow        14
    LightGray     7  White         15 }

  { 'Links' to original 16 colors for palette setting }
  VGAColorsNum: array[0..15]of Byte = ( 0, 1, 2, 3, 4, 5,20, 7,
                                       56,57,58,59,60,61,62,63);

  Position_Value: array[10..80] of integer =

                (100,-20,10, 5, 5,10,-20,100,     0,
                 -20,-50,-2,-2,-2,-2,-50,-20,     0,
                  10, -2,-1,-1,-1,-1, -2, 10,     0,
                   5, -2,-1,-1,-1,-1, -2,  5,     0,
                   5, -2,-1,-1,-1,-1, -2,  5,     0,
                  10, -2,-1,-1,-1,-1, -2, 10,     0,
                 -20,-50,-2,-2,-2,-2,-50,-20,     0,
                 100,-20,10, 5, 5,10,-20,100);

  (*
  Move_Ordered_List: array[0..63] of 10..80 =
  (
   10,17,73,80,                                     { corners }
   12,15,28,35,55,62,75,78,                         { edges 2 away from corner }
   13,14,37,44,46,53,76,77,                         { middle 2 pieces of each edge }
   30,31,32,33,39,40,41,42,48,49,50,51,57,58,59,60, { 4x4 middle squares }
   21,22,23,24,29,34,38,43,47,52,56,61,66,67,68,69, { squares 1 away from edge }
                                                    { not including X squares }
   11,16,19,26,64,71,74,79,                         { C squares }
   20,25,65,70                                      { X squares }
  );
  *)

  { colors }
  Board_Background_Color =  2;
    Move_Highlight_Color =  0;
          Dividers_Color = 10;
             Black_Color =  0;
             White_Color = 15;
     Possible_move_Color =  0;
              Edge_Color =  8;
             Empty_Color =  7;
        Legal_Move_Color =  4;
       Chosen_Move_Color =  4;

  { board placements }
  Black = 0;
  White = 1;
  Empty = 2;
  Possible = 3;
  Border = 4;

  { radii }
  Piece_Radius = 20;
  Possible_Move_Radius = 4;
  Chosen_Move_Radius = 4{20};

  { legal move vars }
  { - set up 8 directions of search }
  {   \Г/ 012 }
  {   Ф Ф 3 4 }
  {   /Г\ 567 }
  GLB_direction: array[0..7] of -10..10 = (-10,-9,-8,-1,1,8,9,10);

  { players array }
  Human = True;
  Computer = False;

  { screen locations/placements }
  Legal_Move_Start_Row = 16;

  { move value (are Integer: -32768..32767 Signed 16-bit }
  INFINITY = 32767;

  { timer constants }
  ticks_per_move = round(10*18.206481481);  { 10 seconds }


type
  boardrecord = record
    side2move: 0..1;
    board: array[0..90] of 0..4; { 0 = black piece }
                                 { 1 = white piece }
                                 { 2 = empty }
                                 { 3 = empty/possible legal moves }
                                 { 4 = edge = off the board }
    lastmovenull: boolean;       { T = last move was null
                                       (allowing player to move twice or
                                        game over) }
    empty_squares: 0..60;        { amount of empty squares on baord }
                                 { 0 = end of game }
  end;

  movelisttype = array[0..60] of 0..80; { [0] = number of moves }
                                        { [1..[0]] = legal moves }
                                        { 0..80 because: }
                                        {   60 = max. moves  }
                                        {   10..80 = possible moves }

{ GLB_ = GLOBAL VARIABLE }

var

  { graphic driver vars }
  GLB_grDriver: Integer;
  GLB_grMode: Integer;
  GLB_ErrCode: Integer;

  { loop vars }
  GLB_i,
  GLB_j: byte;

  { board vars }
  GLB_mainboard: boardrecord;          { board positions }
  GLB_mainboard_copy: boardrecord;     { copy of board positions }
  GLB_movelist: movelisttype;

  { game vars }
  GLB_move: 0..80;                      { select move, 0=quit }
  GLB_Player:  array[0..1] of boolean;  { 0 = black }
                                        { 1 = white }
                                        { true  = human player }
                                        { false = computer player }
  GLB_Consecutive_Null_Moves: 0..2;     { 2 = end of game }
  GLB_Depth: 1..60;                     { search depth }
  GLB_Max_Depth: 1..60;                 { maximum search depth (in search selective extensions) }
  GLB_Positions_Seen: longint;
  GLB_Leaf_Node_Positions_Seen: longint;
  GLB_Perfect_End_Game_Play: boolean;   { T = playing perfectly }

  { user interface vars }
  GLB_user_x,
  GLB_user_y: 0..7;          { cursor position }


  { string vars }
  GLB_string: string;

  { char }
  GLB_Key: char;

  { timer handler vars }
  GLB_TimerIntVec: Procedure;    { store old procedure }
  GLB_ticks_so_far: longint;     { amount of ticks in current move }
  GLB_secs_so_far: longint;      { amount of seconds in current move }
  GLB_time_up: boolean;          { true if computer is out of time }
                                 { and has to stop thinking }


label
  GLB_Quit,             { user quits from game }
  GLB_Game_Over;        { game over, end of game }


{ ------------------------------------------------------------------- }
{ ------------------------------------------------------------------- }
{ ------------------------------------------------------------------- }
{ --------------------- PROCEDURES / FUNCTIONS ---------------------- }
{ ------------------------------------------------------------------- }
{ ------------------------------------------------------------------- }
{ ------------------------------------------------------------------- }


{ ------------------------- PRINT END TITLE --------------------------- }
procedure Print_End_Title;
begin
  { Outro text }
  textattr := Yellow + Blue shl 4;
  writeln(' WipeOut '+version+'                                      (c) 1998 Matthew J. Doucette ');

  { DOS text color }
  textattr := LightGray;
end;


{ ------------------------- DRAW FILLED CIRCLE --------------------------- }
{ Draws a filled circle at (x,y), (x,y=0..7), of specified radius & color
  at appropriate spot on screen }
procedure Draw_Filled_Circle(DFC_x,DFC_y,DFC_radius,DFC_color: byte);
var
  { loop vars }
  DFC_x2,
  DFC_y2: byte;
begin
  { - Set color of border }
  SetColor(DFC_color);
  { - Set style/color of fill }
  SetFillStyle(SolidFill,DFC_color);
  { - draw stone in approprite spot on screen }
  {   - squares are 60x60, 29 approx. = center }
  for DFC_x2 := 0 to 1 do
    for DFC_y2 := 0 to 1 do
      PieSlice(DFC_x2+24+50*DFC_x,DFC_y2+24+50*DFC_y,0,360,DFC_radius);
end;


{ -------------------------- FIND LEGAL MOVES ------------------------ }

{ find legal moves of a board position }
procedure Find_Legal_Moves(FLM_board: boardrecord;
                       var FLM_movelist: movelisttype);
var
  { loop vars }
  FLM_i,      { move being tested }
  FLM_j: byte;
  FLM_dir: 0..7; { 8 directions }

  FLM_num_legal_moves: 0..60; { number of legal moves }
  FLM_Opposite_Color: 0..1;   { other player's color }

label
  FLM_Next_Direction,        { quit current direction and goto next one }
  FLM_Next_Possible_Move;   { legal move found, try another... }

begin
  FLM_num_legal_moves := 0;

  FLM_Opposite_Color := 1-FLM_board.side2move;

  { search for all "possibly legal" moves }
  (*
  for FLM_i := 0 to 63 do
  *)
  for FLM_i := 10 to 80 do
    begin
      (*
      if FLM_board.board[Move_Ordered_List[FLM_i]] = possible then
      *)
      if FLM_board.board[FLM_i] = possible then
        { calculate if possibly legal move is legal }
        begin
          for FLM_dir := 0 to 7 do { check all 8 directions }
            begin
              { check first stone in direction FLM_dir }
              (*
              FLM_j := Move_Ordered_List[FLM_i] + GLB_direction[FLM_dir];
              *)
              FLM_j := FLM_i + GLB_direction[FLM_dir];

              { is first stone opponent's color? if not goto next dir. }
              if FLM_board.board[FLM_j] <> FLM_Opposite_Color then goto FLM_Next_Direction;

              repeat
                { continue down direction FLM_dir until opponent's color
                  is NOT found.  May be your color/empty square/edge... }
                FLM_j := FLM_j + GLB_direction[FLM_dir];

              until FLM_board.board[FLM_j] <> FLM_Opposite_Color;

              { is 'last' square your color?  if not then goto next dir. }
              if FLM_board.board[FLM_j] <> FLM_board.side2move then goto FLM_Next_Direction;

              { move is legal, put it in array and goto next move. }
              inc(FLM_num_legal_moves);
              (*
              FLM_movelist[FLM_num_legal_moves] := Move_Ordered_List[FLM_i];
              *)
              FLM_movelist[FLM_num_legal_moves] := FLM_i;
              goto FLM_Next_Possible_Move;

              FLM_Next_Direction:
            end;
        end;
      FLM_Next_Possible_Move:
    end;

  { store number of legal moves }
  FLM_movelist[0] := FLM_num_legal_moves;


end;


{ --------------------- DRAW BOARD BACKGROUND ------------------------ }

{ Draw Reversi Board Background to Screen 480x480 (0,0)->(479,479) }
procedure Draw_Board_Background;
var
  { loop vars }
  DBB_i,
  DBB_x,
  DBB_y: byte;

begin
  { - Set fill style  }
  SetFillStyle(SolidFill, Board_Background_color);
  { - Draw Board 50*8=400 }
  Bar(0,0,399,399);
  { - Set color }
  SetColor(Dividers_color);
  { - Draw Dividers }
  for DBB_i := 0 to 7 do
    begin
      { vertical lines }
      Line(DBB_i*50,0,DBB_i*50,399);
      Line(49+DBB_i*50,0,49+DBB_i*50,399);
      { horizontal lines }
      Line(0,DBB_i*50,399,DBB_i*50);
      Line(0,49+DBB_i*50,399,49+DBB_i*50);
    end;

end;


{ ----------------------------- DRAW BOARD ------------------------------- }

{ Draw Reversi Board to Screen 480x480 (0,0)->(479,479) }
procedure Draw_Board(DB_board,DB_board_copy: boardrecord);
var
  { loop vars }
  DB_x,
  DB_y: byte;

  { temp vars }
  DB_temp_byte: byte;

begin

  { - Draw Stones }
  { draw what's     кФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФП
    inside square   Г 0 Г 1 Г 2 Г 3 Г 4 Г 5 Г 6 Г 7 Г 8 Г
    of asterisks.   УФФФЩЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЛ
                    Г 9 К 10Г 11Г 12Г 13Г 14Г 15Г 16Г 17К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 18К 19Г 20Г 21Г 22Г 23Г 24Г 25Г 26К
                    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    Г 27К 28Г 29Г 30Г 31Г 32Г 33Г 34Г 35К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 36К 37Г 38Г 39Г W Г B Г 42Г 43Г 44К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 45К 46Г 47Г 48Г B Г W Г 51Г 52Г 53К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 54К 55Г 56Г 57Г 58Г 59Г 60Г 61Г 62К
                    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    Г 63К 64Г 65Г 66Г 67Г 68Г 69Г 70Г 71К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 72К 73Г 74Г 75Г 76Г 77Г 78Г 79Г 80К
                    УФФФШЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭМ
                    Г 81Г 82Г 83Г 84Г 85Г 86Г 87Г 88Г 89Г
                    УФФФХФФФСФФФСФФФСФФФСФФФСФФФСФФФСФФФй
                    Г 90Г
                    РФФФй }
  for DB_x := 0 to 7 do
    for DB_y := 0 to 7 do
      begin
        DB_temp_byte := DB_board.board[(DB_x+1)+((DB_y+1)*9)];

        { update CHANGED values only: }
        if DB_temp_byte <> DB_board_copy.board[(DB_x+1)+((DB_y+1)*9)] then
          begin
            Case DB_temp_byte of
              Black:    begin
                          Draw_Filled_Circle(DB_x,DB_y,Piece_Radius,Black_color);
                        end;
              White:    begin
                          Draw_Filled_Circle(DB_x,DB_y,Piece_Radius,White_color);
                        end;
              Possible: begin
                        end;
              Empty:    begin
                          { draw nothing }
                        end;
              Border:   begin
                          { Go back to text mode }
                          CloseGraph;
                          WriteLn('Error in "Draw Board".');
                          WriteLn('An "Edge" value was set on the board: ',DB_temp_byte);
                          Halt(1);
                        end;
            else
              begin
                { Go back to text mode }
                CloseGraph;
                WriteLn('Error in "Draw Board".');
                WriteLn('An incorrect value was set on the board: ',DB_temp_byte);
                Halt(1);
              end;
            end;

            (*
            { show board values on board }
            str(DB_temp_byte,GLB_string);
            SetColor(Black_Color);
            OutTextXY(DB_x*50+42,DB_y*50+42,GLB_string);
            SetColor(White_Color);
            OutTextXY(DB_x*50+41,DB_y*50+41,GLB_string);
            *)

            (*
            { show board position values (10..80) on board }
            str((DB_x+1)+((DB_y+1)*9),GLB_string);
            SetColor(Black_Color);
            OutTextXY(DB_x*50+2,DB_y*50+2,GLB_string);
            SetColor(White_Color);
            OutTextXY(DB_x*50+1,DB_y*50+1,GLB_string);
            *)
          end;


        { update ALL values: }
        Case DB_temp_byte of
          Black:    begin
                    end;
          White:    begin
                    end;
          Possible: begin
                      {
                      Draw_Filled_Circle(DB_x,DB_y,Possible_Move_Radius,Possible_Move_Color);
                      }
                    end;
          Empty:    begin
                      { draw nothing }
                    end;
          Border:   begin
                      { Go back to text mode }
                      CloseGraph;
                      WriteLn('Error in "Draw Board".');
                      WriteLn('An "Edge" value was set on the board: ',DB_temp_byte);
                      Halt(1);
                    end;
        else
          begin
            { Go back to text mode }
            CloseGraph;
            WriteLn('Error in "Draw Board".');
            WriteLn('An incorrect value was set on the board: ',DB_temp_byte);
            Halt(1);
          end;
        end;

      end;

  (*
  { show board values on side of screen }
  for GLB_i := 0 to 90 do
    begin
      str(DB_board.board[GLB_i],GLB_string);
      PrintString8(51+GLB_i mod 9,5+GLB_i div 9,GLB_string,sys8.FontPtr);
    end;
  *)


  { show legal moves }

  { - using __GLOBAL__ movelist }
  Find_Legal_Moves(DB_board,GLB_movelist);

  (*
  { - erase previous text }
  SetWritePlane(15);
  for GLB_i := 50 to 53 do
    begin
      PrintString8(0,GLB_i,'                                        '+
                           '                                        ',sys8.FontPtr);
      PrintString8(0,GLB_i,'________________________________________'+
                           '________________________________________',sys8.FontPtr);
    end; SetWritePlane(15);
  { - draw legal moves in text }
  for GLB_i := 0 to 60 do
    begin
      str(GLB_movelist[GLB_i],GLB_string);
      PrintString8(3*(GLB_i mod 20),50+(GLB_i div 20),GLB_string,sys8.FontPtr);
    end;
  *)

  (*
  { - draw legal move circles }
  for GLB_i := 1 to GLB_movelist[0] do

    { - move = 10..80 -> x,y = 0..7 }
    Draw_Filled_Circle((GLB_movelist[GLB_i]-10) mod 9,
                       (GLB_movelist[GLB_i]-10) div 9,
                       Possible_Move_Radius,
                       Legal_Move_Color);
  *)

end;


{ --------------------------- MAKE MOVE ---------------------------- }

{ make moves on board }
{ - NO ILLEGAL MOVE CHECKING, MOVE MUST BE LEGAL }
procedure Make_Move(var MM_board: boardrecord;
                        MM_move: byte);
var
  { loop vars }
  MM_i: byte;           { loop variable }
  MM_dir: 0..7;         { 8 directions }

  MM_flip_stone_count: byte;  { counts amount of stones to be flipped in ONE dir. }
  MM_move_copy: 0..90;       { copy of MM_move }
  MM_opposite_color: 0..1;

begin
  MM_opposite_color := 1-MM_board.side2move;

  { place new stone on board }
  MM_board.board[MM_move] := MM_board.side2move;

  { check 8 directions to update empty squares to possible moves }
  for MM_dir := 0 to 7 do
    begin
      MM_move_copy := MM_move + GLB_direction[MM_dir];
      if MM_board.board[MM_move_copy] = Empty then
        MM_board.board[MM_move_copy] := Possible;

    end;

  { check 8 directions to flip appropriate stones }
  for MM_dir := 0 to 7 do
    begin
      MM_move_copy := MM_move + GLB_direction[MM_dir];

      { first piece MUST be opposite color to continue }
      if MM_board.board[MM_move_copy] = MM_Opposite_Color then
        begin
          MM_flip_stone_count := 0;

          { continue down direction until NOT opposite color }
          repeat
            MM_move_copy := MM_move_copy + GLB_direction[MM_dir];
            inc(MM_flip_stone_count);
          until MM_board.board[MM_move_copy] <> MM_Opposite_Color;

          { check to see if next square is your color... }
          { - if so then move is LEGAL }
          if MM_board.board[MM_move_copy] = MM_board.side2move then
            begin
              { go backwards back to stone just played, flipping
                opponent's stones }
              for MM_i := 1 to MM_flip_stone_count do
                begin
                  MM_move_copy := MM_move_copy - GLB_direction[MM_dir];
                  MM_board.board[MM_move_copy] := MM_board.side2move;

                end;


            end;

        end;

    end;

  { update: 1) null move }
  {         2) side-to-move }
  {         3) empty squares }
  MM_board.lastmovenull := False;
  MM_board.side2move := MM_opposite_color;
  dec(MM_board.Empty_Squares);

end;


{ --------------------- INCREMENTAL MAKE MOVE ---------------------------- }

{ make moves on board }
{ - NO ILLEGAL MOVE CHECKING, MOVE MUST BE LEGAL }
procedure Incremental_Make_Move(var IMM_board: boardrecord;
                                    IMM_move: byte;
                                var IMM_value: integer);
var
  { loop vars }
  IMM_i: byte;           { loop variable }
  IMM_dir: 0..7;         { 8 directions }

  IMM_flip_stone_count: byte;  { counts amount of stones to be flipped in ONE dir. }
  IMM_move_copy: 0..90;       { copy of MM_move }
  IMM_opposite_color: 0..1;

begin
  IMM_opposite_color := 1-IMM_board.side2move;

  { place new stone on board }
  IMM_board.board[IMM_move] := IMM_board.side2move;

  { update value of move }
  IMM_value := 1;

  { check 8 directions to update empty squares to possible moves }
  for IMM_dir := 0 to 7 do
    begin
      IMM_move_copy := IMM_move + GLB_direction[IMM_dir];
      if IMM_board.board[IMM_move_copy] = Empty then
        IMM_board.board[IMM_move_copy] := Possible;

    end;

  { check 8 directions to flip appropriate stones }
  for IMM_dir := 0 to 7 do
    begin
      IMM_move_copy := IMM_move + GLB_direction[IMM_dir];

      { first piece MUST be opposite color to continue }
      if IMM_board.board[IMM_move_copy] = IMM_Opposite_Color then
        begin
          IMM_flip_stone_count := 0;

          { continue down direction until NOT opposite color }
          repeat
            IMM_move_copy := IMM_move_copy + GLB_direction[IMM_dir];
            inc(IMM_flip_stone_count);
          until IMM_board.board[IMM_move_copy] <> IMM_Opposite_Color;

          { check to see if next square is your color... }
          { - if so then move is LEGAL }
          if IMM_board.board[IMM_move_copy] = IMM_board.side2move then
            begin
              { go backwards back to stone just played, flipping
                opponent's stones }
              for IMM_i := 1 to IMM_flip_stone_count do
                begin

                  { update 'pointer' on board in proper direction }
                  IMM_move_copy := IMM_move_copy - GLB_direction[IMM_dir];

                  { flip stones on board at 'pointer' position }
                  IMM_board.board[IMM_move_copy] := IMM_board.side2move;

                  { update value of move }
                  inc(IMM_value);
                end;


            end;

        end;

    end;

  { update: 1) null move }
  {         2) side-to-move }
  {         3) empty squares }

  IMM_board.lastmovenull := False;
  IMM_board.side2move := IMM_opposite_color;
  dec(IMM_board.Empty_Squares);

end;


{ --------------------------- GET USER MOVE ---------------------------- }

{ returns selected move (10..80) }
{ - only called if there is a legal move }
{ - WARNING: Uses and updates GLB_user_x and GLB_user_y }
function Get_User_Move: byte;

procedure GUM_Highlight(GUMH_x,GUMH_y:byte);
  var
    GUM_string: string;
  begin
    SetColor(Move_Highlight_Color);
    Rectangle(GUMH_x*50,GUMH_y*50,GUMH_x*50+49,GUMH_y*50+49);
    GUM_string := chr(GUMH_x+65);
    GUM_string := GUM_string + chr(GUMH_y+49);

    { draw user's move indicator to screen }
    { - extra space to delete previous text }
    PrintString8(51,Legal_Move_Start_Row-2,'User''s Move: ',sys8.FontPtr);
    PrintString8(64,Legal_Move_Start_Row-2,GUM_string,sys8.FontPtr);
  end;

procedure GUM_Un_Highlight(GUMUH_x,GUMUH_y: byte);
  begin
    SetColor(Dividers_Color);
    Rectangle(GUMUH_x*50,GUMUH_y*50,GUMUH_x*50+49,GUMUH_y*50+49);
  end;


var
  GUM_key: char;        { key presses }
  GUM_move: 10..80;     { chosen move}
  GUM_i: byte;          { loop varible }

label
  GUM_Legal_Move_Chosen;

begin

  { highlight initial move selection }
  GUM_Highlight(GLB_user_x,GLB_user_y);

  repeat { infinite loop }

    if keypressed then
      begin

        { read keypress }
        GUM_key := readkey;

        { extended code }
        if GUM_key = #0 then
          begin

            { delete highlighted move selection }
            GUM_UN_Highlight(GLB_user_x,GLB_user_y);

            { read extended code }
            GUM_key := readkey;
            if GUM_key = #72 then {up} if GLB_user_y = 0 then GLB_user_y := 7 else dec(GLB_user_y);
            if GUM_key = #80 then {down} if GLB_user_y = 7 then GLB_user_y := 0 else inc(GLB_user_y);
            if GUM_key = #75 then {left} if GLB_user_x = 0 then GLB_user_x := 7 else dec(GLB_user_x);
            if GUM_key = #77 then {right} if GLB_user_x = 7 then GLB_user_x := 0 else inc(GLB_user_x);

            { highlight new move selection }
            GUM_Highlight(GLB_user_x,GLB_user_y);

          end;

        { enter }
        { - select move }
        if GUM_key = #13 then
          begin
            { convert move from (0..7,0..7) to 10..80 }
            GUM_move := (GLB_user_x+10)+(GLB_user_y*9);

            { check to see if move is legal }
            for GUM_i := 1 to GLB_movelist[0] do
              if GUM_move = GLB_movelist[GUM_i]
                then { legal move } goto GUM_Legal_Move_Chosen;
              { else illegal move, do not accept }

          end;

        { esc }
        { - quit }
        if GUM_key = #27 then
          begin
            { Go back to text mode }
            CloseGraph;
            Print_End_Title;
            WriteLn('Loser.');
            {
            WriteLn('User exit from "Get User Move".');
            WriteLn('Program Aborted.');
            }
            Halt(1);
          end;

      end;

  until false; { infinite loop }

  GUM_Legal_Move_Chosen:

  { delete highlighted move selection }
  GUM_UN_Highlight(GLB_user_x,GLB_user_y);

  Get_User_move := GUM_move;

end;


{ ---------------- PRINT POSITIONS SEEN/TIME/POS PER SEC ---------------- }
procedure Print_Positions_and_Time;
var
  PPT_string: string;

begin

  { update maxdepth to screen }
  str(GLB_Max_Depth,PPT_string);
  PrintString8(67,7,PPT_string+' ',sys8.FontPtr);

  { draw positions seen }
  PrintString8(67,8,'            ',sys8.FontPtr);
  str(GLB_Positions_Seen,PPT_string);
  PrintString8(67,8,PPT_string,sys8.FontPtr);

  { draw leaf node positions seen }
  PrintString8(67,9,'            ',sys8.FontPtr);
  str(GLB_Leaf_Node_Positions_Seen,PPT_string);
  PrintString8(67,9,PPT_string,sys8.FontPtr);

  { print positions seen per second }
  PrintString8(67,11,'            ',sys8.FontPtr);
  if GLB_ticks_so_far<>0
    then str(GLB_positions_seen/(GLB_ticks_so_far/18.206481481):0:0,PPT_string)
    else PPT_string := 'ь';
  PrintString8(67,11,PPT_string,sys8.FontPtr);

end;


{ -------------------- TIMER HANDLER ---------------- }
{ - gets called 18.2 times a second automatically once "turned on" }
{ - used for updated game engine information }
{$F+}    { Force Far Calls On }
procedure TimerHandler; interrupt;
  var
    TH_string,
    TH_string2: string;
  begin

    inc(GLB_ticks_so_far);
    if GLB_ticks_so_far >= ticks_per_move then GLB_time_up := true;

    { every 16th time TimerHandler is called do... }
    if (ticks and 7) = 0 then
      Print_Positions_and_Time;

    { check for time change every call }
    if trunc(GLB_ticks_so_far/18.206481481)>GLB_secs_so_far then
      begin
        inc(GLB_secs_so_far);
        if GLB_secs_so_far<60
          then
            begin
              str(GLB_secs_so_far,TH_string);
              if GLB_secs_so_far<10
                then TH_string := '0:0'+TH_string
                else TH_string := '0:'+TH_string;
            end
          else
            begin
              str(GLB_secs_so_far div 60,TH_string);
              TH_string := TH_string + ':';
              str(GLB_secs_so_far mod 60,TH_string2);
              if (GLB_secs_so_far mod 60)<10
                then TH_string := TH_string + '0'+TH_string2
                else TH_string := TH_string + TH_string2;
            end;
        PrintString8(67,10,TH_string,sys8.FontPtr);
      end;

    GLB_TimerIntVec; { call old procedure }

  end;
{$F-}    { Force Far Calls Off }


{ ----------------------- START TIMER ----------------------- }
procedure Start_Timer;
begin
  GLB_ticks_so_far := 0;                 { intialize ticks count for current move }
  GLB_secs_so_far := 0;
  GetIntVec($1C,Addr(GLB_TimerIntVec));  { save old interrupt vector into TIMERINTVEC }
  SetIntVec($1C,Addr(TimerHandler)); { START/set pointer to new procedure }
end;


{ ----------------------- STOP TIMER ----------------------- }
procedure Stop_Timer;
begin
  SetIntVec($1C,Addr(GLB_TimerIntVec)); {restore old interrupt vector (TIMERINTVEC)}
end;


{ --------------------------- MATERIAL EVALUATE --------------------------- }

{ returns a material evaluation of a board position }
function Material_Evaluate(ME_board: boardrecord): integer;

var
  ME_value: integer;    { value of position }
  ME_i: byte;           { loop variable }

begin
  ME_value := 0;

  for ME_i := 10 to 80 do
    begin
      if ME_board.board[ME_i] = ME_board.side2move then inc(ME_value);
      if ME_board.board[ME_i] = 1-ME_board.side2move then dec(ME_value);
    end;

  Material_Evaluate := ME_value;
end;


{ --------------------------- POSITIONAL EVALUATE --------------------------- }

{ returns a material evaluation of a board position }
function Positional_Evaluate(PE_board: boardrecord): integer;
{
  Position_Value: array[10..80] of integer =

                (100,-20,10, 5, 5,10,-20,100,     0,
                 -20,-50,-2,-2,-2,-2,-50,-20,     0,
                  10, -2,-1,-1,-1,-1, -2, 10,     0,
                   5, -2,-1,-1,-1,-1, -2,  5,     0,
                   5, -2,-1,-1,-1,-1, -2,  5,     0,
                  10, -2,-1,-1,-1,-1, -2, 10,     0,
                 -20,-50,-2,-2,-2,-2,-50,-20,     0,
                 100,-20,10, 5, 5,10,-20,100);


}
var
  PE_value: integer;    { value of position }
  PE_i: byte;           { loop variable }

begin
  PE_value := 0;

  for PE_i := 10 to 80 do
    begin
      if PE_board.board[PE_i] = PE_board.side2move
        then inc(PE_value,Position_Value[PE_i]);
      if PE_board.board[PE_i] = 1-PE_board.side2move
        then dec(PE_value,Position_Value[PE_i]);
    end;

  { NEGATE X and C square values IF:
    - corresponding corner is played by either player }
  { - X and C squares are the 3 squares adjacent to the corner (12 in all) }
  { - corners = 10,17,73,80 }

  { top left }
  if PE_board.board[10] < 2  { White or Black }
    then
      begin
        if PE_board.board[11] = PE_board.side2move   then dec(PE_value,2*Position_Value[11]);
        if PE_board.board[11] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[11]);
        if PE_board.board[19] = PE_board.side2move   then dec(PE_value,2*Position_Value[19]);
        if PE_board.board[19] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[19]);
        if PE_board.board[20] = PE_board.side2move   then dec(PE_value,2*Position_Value[20]);
        if PE_board.board[20] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[20]);
      end;

  { top right }
  if PE_board.board[17] < 2  { White or Black }
    then
      begin
        if PE_board.board[16] = PE_board.side2move   then dec(PE_value,2*Position_Value[16]);
        if PE_board.board[16] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[16]);
        if PE_board.board[25] = PE_board.side2move   then dec(PE_value,2*Position_Value[25]);
        if PE_board.board[25] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[25]);
        if PE_board.board[26] = PE_board.side2move   then dec(PE_value,2*Position_Value[26]);
        if PE_board.board[26] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[26]);
      end;

  { bottom left }
  if PE_board.board[73] < 2  { White or Black }
    then
      begin
        if PE_board.board[64] = PE_board.side2move   then dec(PE_value,2*Position_Value[64]);
        if PE_board.board[64] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[64]);
        if PE_board.board[65] = PE_board.side2move   then dec(PE_value,2*Position_Value[65]);
        if PE_board.board[65] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[65]);
        if PE_board.board[74] = PE_board.side2move   then dec(PE_value,2*Position_Value[74]);
        if PE_board.board[74] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[74]);
      end;

  { bottom right }
  if PE_board.board[80] < 2  { White or Black }
    then
      begin
        if PE_board.board[70] = PE_board.side2move   then dec(PE_value,2*Position_Value[70]);
        if PE_board.board[70] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[70]);
        if PE_board.board[71] = PE_board.side2move   then dec(PE_value,2*Position_Value[71]);
        if PE_board.board[71] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[71]);
        if PE_board.board[79] = PE_board.side2move   then dec(PE_value,2*Position_Value[79]);
        if PE_board.board[79] = 1-PE_board.side2move then inc(PE_value,2*Position_Value[79]);
      end;

  Positional_Evaluate := PE_value;
end;

  {                 кФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФП
                    Г 0 Г 1 Г 2 Г 3 Г 4 Г 5 Г 6 Г 7 Г 8 Г
                    УФФФЩЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЛ
                    Г 9 К 10Г 11Г 12Г 13Г 14Г 15Г 16Г 17К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 18К 19Г 20Г 21Г 22Г 23Г 24Г 25Г 26К
                    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    Г 27К 28Г 29Г 30Г 31Г 32Г 33Г 34Г 35К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 36К 37Г 38Г 39Г W Г B Г 42Г 43Г 44К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 45К 46Г 47Г 48Г B Г W Г 51Г 52Г 53К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 54К 55Г 56Г 57Г 58Г 59Г 60Г 61Г 62К
                    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
                    Г 63К 64Г 65Г 66Г 67Г 68Г 69Г 70Г 71К
                    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
                    Г 72К 73Г 74Г 75Г 76Г 77Г 78Г 79Г 80К
                    УФФФШЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭМ
                    Г 81Г 82Г 83Г 84Г 85Г 86Г 87Г 88Г 89Г
                    УФФФХФФФСФФФСФФФСФФФСФФФСФФФСФФФСФФФй
                    Г 90Г
                    РФФФй }


{ -------------------------- ALPHA BETA ------------------------- }

{ performs an alpha beta search of a given depth on a board postion }
{ returns integer value }

function AlphaBeta (AB_Board: boardrecord;
                    AB_Depth: byte;
                    AB_Max_Depth: byte;
                    AB_Alpha, AB_Beta: integer): integer;
var
  AB_Best: integer;            { move/position value }
  AB_MoveList: movelisttype;   { legal moves }
  AB_Board_Copy: boardrecord;  { copy of board passed in }
  AB_Value: integer;           { value of recursed alpha beta }
  AB_i: byte;                  { loop variable }

begin


  if AB_Depth = 0

    { DEPTH = 0 }
    { - end search, evaluate leaf node position }
    then
      begin
        { update maximum search depth }
        if AB_Max_Depth > GLB_Max_Depth then GLB_Max_Depth := AB_Max_Depth;


        { update leaf node positions seen }
        inc(GLB_Leaf_Node_Positions_Seen);

        { evaluate end board }
        if AB_Board.Empty_Squares = 0


          { END OF GAME }
          { - use material only evaluation }
          then
            begin

              { return win or loss }
              AB_Best := Material_Evaluate(AB_board);

              if AB_Best > 0
                then
                  AlphaBeta := 10000+AB_Best { AB_Best = 1..64 }
                else
                  if AB_Best < 0
                    then
                      AlphaBeta := -10000+AB_Best { AB_Best = -64..-1 }
                    else
                      if AB_Best = 0
                        then
                          AlphaBeta := 0;
              exit;

            end

          { *NOT* END OF GAME }
          { - use positional/material evaluation }
          else
            AlphaBeta := Positional_Evaluate(AB_board);

        exit;

      end

    { DEPTH > 0 }
    { - search another ply deeper}
    else
      begin


        { ???????????????????? SHOULD THIS BE HERE OR SOMEWHERE ELSE????? }
        AB_Best := -INFINITY;


        { find legal moves }
        Find_Legal_Moves(AB_board,AB_movelist);


        if AB_movelist[0] = 1

          { FORCE MOVE, EXTEND SEARCH }
          then
            begin

              { - AB_Beta = INFINITY originally }
              { - AB_Best = -INFINTIY initially }

              { make move on main board NO COPY NEEDED }
              Make_Move(AB_Board,AB_MoveList[1]);

              { update positions seen }
              inc(GLB_Positions_Seen);

              { analyze board position after move }
              { - "depth+1" to extend 2-ply, one for the forced move,
                  the other to 'end' the search on the same color as
                  otherwise. }
              AB_Value := -AlphaBeta(AB_Board,AB_Depth{+1},AB_Max_Depth+1,-AB_Beta,-AB_Alpha);

              { return the ONLY value }
              AlphaBeta := AB_Value;
              exit;

            end

          { 0 or 2-or-more moves }
          else
            if AB_movelist[0] > 0

              { legal moves }
              then
                begin

                  { store amount/# of legal moves }
                  AB_i := AB_movelist[0];

                  { countdown # of moves to 0 }
                  { - AB_Beta = INFINITY originally }
                  { - AB_Best = -INFINTIY initially }
                  while (AB_i>0) and (AB_Best<AB_Beta) do
                    begin

                      { make copy of board to makes move on }
                      AB_Board_Copy := AB_Board;

                      { make move on copy of main board }
                      Make_Move(AB_Board_Copy,AB_MoveList[AB_i]);

                      { update positions seen }
                      inc(GLB_Positions_Seen);

                      { analyze board position after move }
                      AB_Value := -AlphaBeta(AB_Board_Copy,AB_Depth-1,AB_Max_Depth+1,-AB_Beta,-AB_Alpha);

                      { update Best value }
                      if AB_value > AB_Best then AB_Best := AB_Value;

                      { update move-'pointer' for next iteration }
                      dec(AB_i);

                    end;

                  AlphaBeta := AB_Best;

                  exit;

                end

              { no legal moves:  DOUBLE MOVE OR GAME OVER }
              else

                if AB_board.lastmovenull = True

                  { GAME OVER }
                  then
                    begin

                      { update maximum search depth }
                      if AB_Max_Depth > GLB_Max_Depth then GLB_Max_Depth := AB_Max_Depth;

                      { update positions seen }
                      inc(GLB_Positions_Seen);

                      { return win or loss }
                      AB_Best := Material_Evaluate(AB_board);

                      if AB_Best > 0
                        then
                          AlphaBeta := 10000+AB_Best+AB_Board.Empty_Squares { AB_Best = 1..64 }
                        else
                          if AB_Best < 0
                            then
                              AlphaBeta := -10000+AB_Best+AB_Board.Empty_Squares { AB_Best = -64..-1 }
                            else
                              if AB_Best = 0
                                then
                                  AlphaBeta := 0;
                      exit;

                      {
                      Text_Mode;
                      Writeln('NO LEGAL MOVES FOUND ...');
                      Writeln('GAME OVER not handled properly yet ...');
                      halt(1);
                      }

                    end

                  { DOUBLE MOVE }
                  else
                    begin

                      (*
                      { range check code!!!!!!!!!!!!!!!!!!!!!!!!!!!1 }
                      if AB_Depth>50 then
                          begin
                            text_mode;
                            writeln('AB_Depth > 50!!!: ',AB_Depth);
                            halt(1);
                          end;
                      *)

                      { last move was null }
                      AB_board.lastmovenull := True;

                      { switch back to previous player }
                      AB_Board.side2move := 1-AB_Board.side2move;

                      { call AlphaBeta again }
                      { - "depth+1" to extend 2-ply, one for null move,
                          the other for the second move in the double move }
                      { - null move doesn't count as a ply in selctive extension }
                      {   for calculating max depth }
                      AB_Value := -AlphaBeta(AB_Board,AB_Depth+1,AB_Max_Depth,-AB_Beta,-AB_Alpha);

                      { return only value }
                      AlphaBeta := AB_Value;
                      exit;

                      {
                      Text_Mode;
                      Writeln('NO LEGAL MOVES FOUND ...');
                      Writeln('Double Moves are not handled properly yet ...');
                      halt(1);
                      }

                    end;

      end;

end;

(*
Alpha-Beta search

Alpha-Beta search is the first major refinement for reducing the number of
positions that has to be searched and thus making greater depths possible
in the same amount of time. The idea is that in large parts of the tree we
are not interested in the exact value of a position, but are just
interested if it is better or worse than what we have found before. Only
the value of the psoition along the principal variation has to be
determined exactly (the principle variation is the alternation of best own
moves and best opponent moves from the root to the depth of the tree).

The AlphaBeta search procedure gets two additional arguments which indicate
the bounds between which we are interested in exact values for a position:

----------------------------------------------------------------
-MEANINGS-------------------------------------------------------
----------------------------------------------------------------
 pos        A position in a chess game.
 depth      The number of levels in the tree to be searched.
 Evaluate   A function that determines a value for a position as seen for
            the side to move. In practice such a function will be composed
            of the difference in material values and a large number of
            positional terms. Results lie between -INFINITY and +INFINITY.
 best       The best value seen while searching the next level in the tree.
 Successors A function that determines the set of all positions that can
            be reached from a position in one move (move generation).
 succ       The set of positions reachable from the input position by doing
            one move.
----------------------------------------------------------------

int AlphaBeta (pos, depth, alpha, beta)

{

    if (depth == 0) return Evaluate(pos);

    best = -INFINITY;


    succ = Successors(pos);

    if number_of_moves = 0

    then

      begin


        // game over?
        if nullmove_count=2 then return(gameover_value);

        // double move
        inc(nullmove_count)
        switch_sides(pos);
        value = -AlphaBeta(pos, depth+1, -beta, -alpha);

        return value

      end

    else

      while (not Empty(succ) && best < beta)

      {

          pos = RemoveOne(succ);

          if (best > alpha) alpha = best;

          value = -AlphaBeta(pos, depth-1, -beta, -alpha);

          if (value > best) best = value;

      }

    return best;

}

The gain from AlphaBeta will come form the earlier exit from the while
loop; a value of best that equals or exceeds beta is called a cutoff. These
cutoffs are completely safe because they mean that this branch of the tree
is worse than the prinicpal variation. The largest gain is reached when at
each level of the tree the best successor position is searched first,
because this position will either be part of the principal variation (which
we want to establish as early as possible) or it will cause a cutoff to be
as early as possible.

Under optimal circumstances AlphaBeta still has to search W^((D+1)/2) +
W^(D/2) - 1 positions. This is much less than MiniMax, but still
exponential. It allows to reach about twice the depth in the same amount of
time. More positions will have to be searched if move ordering is not
perfect.

Note: The version of AlphaBeta shown above is also known as fail-soft
alpha-beta. It can return values outside the range alpha...beta, which can
be used as upper or lower bounds if a re-search has to be done.
*)


{ ------------------------- GET COMPUTER MOVE ---------------------------- }

{ returns selected move (10..80) }
{ - only called if there is a legal move }
{ - WARNING: Uses - Global Move List: "GLB_MoveList" }
{                 - Global MainBoard: "GLB_MainBoard" }
function Get_Computer_Move: byte;
var
  GCM_i: byte;         { loop variable }
  GCM_string: string;  { string }
  GCM_key: char;       { key presses }

  GCM_Best_Move: 10..80;                    { chosen move {10..80) }
  GCM_Best_Moves: array[0..60] of 0..80;    { best moves }
                                            { - sometimes more than one move }
                                            {   TIES for best move           }
                                            { - [0] = amount                 }
  GCM_Best_Value: integer;                  { for choosing best move }
  GCM_ValueList: array[1..60] of integer;   { values of all legal moves }
  GCM_Board_Copy: boardrecord;              { copy of main board }

label
  GCM_done_thinking;

begin

  { delete previous values from screen }
  { - maxdepth }
  PrintString8(67,7,'0 ',sys8.FontPtr);
  { - positions seen }
  PrintString8(67,8,'0           ',sys8.FontPtr);
  { - leaf node positions seen }
  PrintString8(67,9,'0           ',sys8.FontPtr);
  { - time }
  PrintString8(67,10,'0:00        ',sys8.FontPtr);
  { - pos/sec }
  PrintString8(67,11,'ь           ',sys8.FontPtr);

  { delete any previous legal moves on screen }
  for GCM_i := 1 to 40 do
    PrintString8(51,Legal_Move_Start_Row-1+GCM_i,
                 '                 ',sys8.FontPtr);

  { draw amount of legal moves }
  { - extra space to delete previous string on screen }
  str(GLB_MoveList[0],GCM_string);
  PrintString8(51,Legal_Move_Start_Row-2,GCM_string+' Legal Moves: ',sys8.FontPtr);


  { for every legal move do... }
  for GCM_i := 1 to GLB_MoveList[0] do
    begin

      { draw legal moves to screen }
      { convert 10..80 to A..H1..8 }
      { - A..H }
      GCM_string := chr(((GLB_MoveList[GCM_i]-10) mod 9)+65);
      GCM_string := GCM_string + chr(((GLB_MoveList[GCM_i]-10) div 9)+49);
      (*
      { 10..80 }
      str(GLB_MoveList[GCM_i],GCM_string);
      *)
      PrintString8(53,Legal_Move_Start_Row-1+GCM_i,
                   GCM_string+': ',sys8.FontPtr);

    end;

  if GLB_MoveList[0]=1 then
    begin

      { print move value on screen }
      PrintString8(57,Legal_Move_Start_Row-1+1,'Forced Move',sys8.FontPtr);
      Goto GCM_done_thinking;

    end;

  if GLB_Perfect_End_Game_Play
    then

      { perfect end game play }
      begin
        GLB_Leaf_Node_Positions_Seen := 0;
        GLB_Positions_Seen := 0;

        { set depth to see right to end of game }
        GLB_Depth := GLB_Mainboard.Empty_Squares;

        { draw depth to screen }
        str(GLB_Depth,GCM_string);
        PrintString8(67,6,GCM_string+' ',sys8.FontPtr);

        GLB_Max_Depth := 1;                { maximum search depth }
        Start_Timer;

        { for every legal move do... }
        for GCM_i := 1 to GLB_MoveList[0] do
          begin
            { hilight current move }
            PrintString8(51,Legal_Move_Start_Row-1+GCM_i,'-',sys8.FontPtr);

            { make copy of main board to makes move on }
            GCM_Board_Copy := GLB_MainBoard;

            { make move on copy of main board }
            Make_Move(GCM_Board_Copy,GLB_MoveList[GCM_i]);

            { analyze board position after move }
            GCM_ValueList[GCM_i] := -AlphaBeta(GCM_Board_Copy,GLB_Depth-1,1,-INFINITY,INFINITY);

            { print move value on screen }
            { - delete any previous value }
            PrintString8(57,Legal_Move_Start_Row-1+GCM_i,
                   '           ',sys8.FontPtr);

            str(GCM_ValueList[GCM_i],GCM_string);

            if GCM_ValueList[GCM_i]>10000 then
              begin
                str(GCM_ValueList[GCM_i]-10000,GCM_string);
                GCM_string := 'Win by '+GCM_string;
              end;
            if GCM_ValueList[GCM_i]<-10000 then
              begin
                str(-(GCM_ValueList[GCM_i]+10000),GCM_string);
                GCM_string := 'Lose by '+GCM_string;
              end;
            if GCM_ValueList[GCM_i]=0
              then GCM_string := 'Tie';

            { error checking code }
            if (GCM_ValueList[GCM_i]<>0) and
               (GCM_ValueList[GCM_i]>-10000) and
               (GCM_ValueList[GCM_i]<10000)
              then
                begin
                  text_mode;
                  writeln('error with end game search');
                  writeln('GCM_ValueList[GCM_i]: ',GCM_ValueList[GCM_i]);
                  halt(1);
                end;

            { print move value on screen }
            PrintString8(57,Legal_Move_Start_Row-1+GCM_i,GCM_string,sys8.FontPtr);

            { de-hilight current move }
            PrintString8(51,Legal_Move_Start_Row-1+GCM_i,' ',sys8.FontPtr);

          end;

        Stop_Timer;
        Print_Positions_and_Time;

      end
    else
      { NOT prefect end game play }
      begin
        GLB_Leaf_Node_Positions_Seen := 0;
        GLB_Positions_Seen := 0;

        GLB_Max_Depth := 1;                { maximum search depth }

        Start_Timer;

        repeat { infinite loop }

          { draw depth to screen }
          str(GLB_Depth,GCM_string);
          PrintString8(67,6,GCM_string+' ',sys8.FontPtr);


          if GLB_MoveList[0]<>1 then

            { for every legal move do... }
            for GCM_i := 1 to GLB_MoveList[0] do
              begin
                { hilight current move }
                PrintString8(51,Legal_Move_Start_Row-1+GCM_i,'-',sys8.FontPtr);

                { make copy of main board to makes move on }
                GCM_Board_Copy := GLB_MainBoard;

                { make move on copy of main board }
                Make_Move(GCM_Board_Copy,GLB_MoveList[GCM_i]);

                { analyze board position after move }
                GCM_ValueList[GCM_i] := -AlphaBeta(GCM_Board_Copy,GLB_Depth-1,1,-INFINITY,INFINITY);

                { print move value on screen }
                { - delete any previous value }
                PrintString8(57,Legal_Move_Start_Row-1+GCM_i,
                       '          ',sys8.FontPtr);

                str(GCM_ValueList[GCM_i],GCM_string);

                { win/loss value? }
                if abs(GCM_ValueList[GCM_i])>10000 then
                  begin
                    if GCM_ValueList[GCM_i]>10000 then
                      begin
                        str(GCM_ValueList[GCM_i]-10000,GCM_string);
                        GCM_string := 'Win by '+GCM_string;
                      end;
                    if GCM_ValueList[GCM_i]<-10000 then
                      begin
                        str(-(GCM_ValueList[GCM_i]+10000),GCM_string);
                        GCM_string := 'Lose by '+GCM_string;
                      end;
                  end;

                { print move value on screen }
                PrintString8(57,Legal_Move_Start_Row-1+GCM_i,GCM_string,sys8.FontPtr);

                { de-hilight current move }
                PrintString8(51,Legal_Move_Start_Row-1+GCM_i,' ',sys8.FontPtr);

              end
            else
              { print move value on screen }
              PrintString8(57,Legal_Move_Start_Row-1+1,'Forced Move',sys8.FontPtr);


          Print_Positions_and_Time;

          { increase depth if under ??? seconds }
          if GLB_Ticks_So_Far < Increase_Depth*18.206481481
            then
              if GLB_Depth = GLB_Mainboard.Empty_Squares

                { maximum depth already searched }
                then goto GCM_done_thinking

                { maximum depth not reached yet }
                else inc(GLB_Depth)

            else goto GCM_done_thinking;

        until false; { infinite loop }
      end;


  GCM_done_thinking:
  Stop_Timer;

  { decrease depth for next move (EVERY TIME) }
  dec(GLB_Depth);

  { find best value }
  GCM_Best_Value := -INFINITY;
  for GCM_i := 1 to GLB_MoveList[0] do
    begin
      if GCM_ValueList[GCM_i] > GCM_Best_Value
        then
          { update best value }
          GCM_Best_Value := GCM_ValueList[GCM_i];
    end;

  { find best moves (potentially more than one) }
  { - initialize amount/count to 0 }
  GCM_Best_Moves[0] := 0;
  for GCM_i := 1 to GLB_MoveList[0] do
    begin
      if GCM_ValueList[GCM_i] = GCM_Best_Value
        then
          begin

            { increase amount/count }
            inc(GCM_Best_Moves[0]);

            { insert move }
            GCM_Best_Moves[GCM_Best_Moves[0]] := GLB_MoveList[GCM_i];

          end;
    end;

  { pick random move of best moves }
  GCM_Best_Move := GCM_Best_Moves[random(GCM_Best_Moves[0])+1];


  (*
  { OVERRIDE BEST MOVE!!!!!!!!!!!! -> PICK RANDOM MOVE  }
  GCM_Best_Move := GLB_MoveList[random(GLB_MoveList[0])+1];
  *)


  { highlight chosen move and wait }
  { - circle on board }
  { - move = 10..80 -> x,y = 0..7 }
  Draw_Filled_Circle(     {x}(GCM_Best_Move-10) mod 9,
                          {y}(GCM_Best_Move-10) div 9,
                     {radius}Chosen_Move_Radius,
                      {color}Chosen_Move_Color);

  { - '*' by values }
  for GCM_i := 1 to GLB_MoveList[0] do
    begin
      if GLB_MoveList[GCM_i] = GCM_Best_Move then
        { draw '*' indicator }
        PrintString8(51,Legal_Move_Start_Row-1+GCM_i,'*',sys8.FontPtr);
    end;


  PrintString8(51,Legal_Move_Start_Row+GLB_MoveList[0]+1,'Done.',sys8.FontPtr);
  while Keypressed do ReadKey;
  Sound(110);        { Beep }
  Delay(1);          { For 1 ms }
  NoSound;           { Relief! }
  GCM_key := Readkey;
  PrintString8(51,Legal_Move_Start_Row+GLB_MoveList[0]+1,'     ',sys8.FontPtr);

  { esc = quit }
  if GCM_key = #27 then
    begin
      { Go back to text mode }
      CloseGraph;
      Print_End_Title;
      WriteLn('Loser.');
      {
      WriteLn('User exit from "Get Computer Move".');
      WriteLn('Program Aborted.');
      }
      Halt(1);
    end;


  Get_Computer_Move := GCM_Best_Move;

end;


{ ------------------------ UPDATE SCORE ------------------------------ }

{ updates score and side-to-move indicator }
{ - WARNING: Uses GLB_mainboard to calculate score }
procedure Update_Score;
var
  US_i: byte;            { loop variables }
  US_string: string;     { string var }
  US_White_Score,
  US_Black_Score: byte;  { Black and White scores }

begin

  { initialize scores to zero }
  US_White_Score := 0;
  US_Black_Score := 0;

  { count stones }
  for US_i := 10 to 80 do { cover whole board (and some edges) }
    begin
      if GLB_mainboard.board[US_i] = Black then inc(US_Black_Score);
      if GLB_mainboard.board[US_i] = White then inc(US_White_Score);
    end;

  { update score on screen }
  str(US_Black_Score,US_string);
  if length(US_string) = 1 then US_string := US_String+' ';
  PrintString8(60,3,US_string,sys8.FontPtr);
  str(US_White_Score,US_string);
  if length(US_string) = 1 then US_string := US_String+' ';
  PrintString8(60,4,US_string,sys8.FontPtr);

  { update side-to-move indicator on screen }
  if GLB_mainboard.side2move = Black
    then
      begin
        PrintString8(51,3,'*',sys8.FontPtr);
        PrintString8(51,4,' ',sys8.FontPtr);
      end
    else
      begin
        PrintString8(51,3,' ',sys8.FontPtr);
        PrintString8(51,4,'*',sys8.FontPtr);
      end;

end;


{ ------------------------ UPDATE *FINAL* SCORE ------------------------ }

{ updates score after GAME IS OVER }
{ - WARNING: - Uses GLB_mainboard to calculate score }
{            - Only used when game is over because
               uses empty squares in score of winner }
procedure Update_FINAL_Score;
var
  US_i: byte;            { loop variables }
  US_string: string;     { string var }
  US_White_Score,
  US_Black_Score: byte;  { Black and White scores }

begin

  { initialize scores to zero }
  US_White_Score := 0;
  US_Black_Score := 0;

  { count stones }
  for US_i := 10 to 80 do { cover whole board (and some edges) }
    begin
      if GLB_mainboard.board[US_i] = Black then inc(US_Black_Score);
      if GLB_mainboard.board[US_i] = White then inc(US_White_Score);
    end;

  { update score on screen }
  str(US_Black_Score,US_string);
  if length(US_string) = 1 then US_string := ' '+US_String;
  PrintString8(60,3,US_string,sys8.FontPtr);
  str(US_White_Score,US_string);
  if length(US_string) = 1 then US_string := ' '+US_String;
  PrintString8(60,4,US_string,sys8.FontPtr);


  { are there any empty squares? }
  if US_White_Score+US_Black_Score < 64 then
    begin

      { count empty squares for winner }

      { - black wins }
      if US_Black_Score > US_White_Score then
        begin

          { count empty squares }
          for US_i := 10 to 80 do
            if (GLB_mainboard.board[US_i] = Empty) or
               (GLB_mainboard.board[US_i] = Possible) then inc(US_Black_Score);

          { update score on screen }
          str(US_Black_Score,US_string);
          PrintString8(63,3,'-> '+US_string,sys8.FontPtr);

        end;

      { - white wins }
      if US_Black_Score < US_White_Score then
        begin

          { count empty squares }
          for US_i := 10 to 80 do
            if (GLB_mainboard.board[US_i] = Empty) or
               (GLB_mainboard.board[US_i] = Possible) then inc(US_White_Score);

          { update score on screen }
          str(US_White_Score,US_string);
          PrintString8(63,4,'-> '+US_string,sys8.FontPtr);
        end;

    end;

  { - black wins }
  if US_Black_Score > US_White_Score then
    begin
      str(US_Black_Score-US_White_Score,US_string);
      PrintString8(1,52,'Black wins by '+US_string+'.',sys8.FontPtr);
    end;

  { - white wins }
  if US_Black_Score < US_White_Score then
    begin
      str(US_White_Score-US_Black_Score,US_string);
      PrintString8(1,52,'White wins by '+US_string+'.',sys8.FontPtr);
    end;

  { - tie }
  if US_Black_Score = US_White_Score then
    begin
      PrintString8(1,52,'Game tied.',sys8.FontPtr);
    end;


  { - clear side-to-move indicator  re: GAME OVER }
  PrintString8(51,3,' ',sys8.FontPtr);
  PrintString8(51,4,' ',sys8.FontPtr);


end;


{ ---------------------------------------------------------- }
{ ---------------------------------------------------------- }
{ ---------------------------------------------------------- }
{ --------------------- PROGRAM BEGIN ---------------------- }
{ ---------------------------------------------------------- }
{ ---------------------------------------------------------- }
{ ---------------------------------------------------------- }


begin
  CheckBreak := False;  { Disables user's control of termination }
  Randomize;

  { ask user to choose sides }
  WriteLn;
  TextAttr := 15;
  WriteLn('WipeOut '+version+' - Matthew J. Doucette - 100019062');
  TextAttr := 7;
  WriteLn;
  WriteLn('Current Settings:');
  WriteLn;
  WriteLn(' Depth Increase < ',Increase_Depth:0:1,' seconds.');
  WriteLn(' Perfect Play Empty Squares <= ',Empty_Squares_for_Perfect_End_Game_Play,'.');
  WriteLn;
  WriteLn('Choose:');
  WriteLn;
  WriteLn(' B  - Black (First move)');
  WriteLn(' W  - White');
  WriteLn(' C  - Computer vs. Computer');
  WriteLn(' H  - Human vs. Human');
  WriteLn('ESC - Quit');

  repeat { until B,W,C,H,ESC is pressed }

    { read keypresses/convert to caps }
    GLB_key := UpCase(ReadKey);

    { ESC = quit }
    if GLB_key=#27 then
                 begin
                   WriteLn;
                   writeln('User exit.');
                   WriteLn('Program Aborted.');
                   Halt(0);
                 end;

  until (GLB_key='B') or
        (GLB_key='W') or
        (GLB_key='C') or
        (GLB_key='H');
  Case GLB_key of
    'B': begin
           GLB_Player[Black] := Human;
           GLB_Player[White] := Computer;
         end;
    'W': begin
           GLB_Player[Black] := Computer;
           GLB_Player[White] := Human;
         end;
    'C': begin
           GLB_Player[Black] := Computer;
           GLB_Player[White] := Computer;
         end;
    'H': begin
           GLB_Player[Black] := Human;
           GLB_Player[White] := Human;
         end;
    else
      begin
        { Go back to text mode }
        WriteLn('Error: An incorrect user/computer mode was choosen.');
        Halt(1);
      end;
  end;

  { Initialize 640x480 Graphics }
  { Graphics Drivers:

    grDriver      Г grMode
    ЭЭЭЭЭЭЭЭЭЭЭЭЭЭиЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭ
    VGA           Г VGALo  / 640x200x16 / 4 pages
                  Г VGAMed / 640x350x16 / 2 pages
                  Г VGAHi  / 640x480x16 / 1 page  }
  GLB_grDriver := VGA;
  GLB_grMode := VGAHi;

  { try current directory first }
  InitGraph(GLB_grDriver, GLB_grMode,'');
  GLB_ErrCode := GraphResult;

  { Device driver file not found (EGAVGA.BGI) ??? }
  if GLB_ErrCode = -3 then

    { try C:\TP\BGI directory second }
    begin
      GLB_grDriver := VGA;
      GLB_grMode := VGAHi;
      InitGraph(GLB_grDriver, GLB_grMode,'c:\tp\bgi');
      GLB_ErrCode := GraphResult;
    end;

  if GLB_ErrCode <> grOk then
    begin
      Writeln('Couldn''t Initialize Graphics.');
      WriteLn('Error: ',GraphErrorMsg(GLB_ErrCode));
      Writeln('GLB_ErrCode: ',GLB_ErrCode);
      halt(1);
    end;


  { set palette }
  { - lower green intensity }
  Set_RGB(VGAColorsNum[2],0,21,0);
  Set_RGB(VGAColorsNum[10],0,31,0);


  { Initialize board }
  {                    0 = black stone
                       1 = white stone
                       2 = empty square
                       3 = possible moves/empty square
                       4 = edge = off the board
    кФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФТФФФП
    Г 0 Г 1 Г 2 Г 3 Г 4 Г 5 Г 6 Г 7 Г 8 Г
    УФФФЩЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЛ
    Г 9 К 10Г 11Г 12Г 13Г 14Г 15Г 16Г 17К
    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
    Г 18К 19Г 20Г 21Г 22Г 23Г 24Г 25Г 26К
    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
    Г 27К 28Г 29Г 30Г 31Г 32Г 33Г 34Г 35К
    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
    Г 36К 37Г 38Г 39Г W Г B Г 42Г 43Г 44К
    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
    Г 45К 46Г 47Г 48Г B Г W Г 51Г 52Г 53К
    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
    Г 54К 55Г 56Г 57Г 58Г 59Г 60Г 61Г 62К
    УФФФКФФФХФФФлФФФХФФФХФФФХФФФлФФФХФФФК
    Г 63К 64Г 65Г 66Г 67Г 68Г 69Г 70Г 71К
    УФФФКФФФХФФФХФФФХФФФХФФФХФФФХФФФХФФФК
    Г 72К 73Г 74Г 75Г 76Г 77Г 78Г 79Г 80К
    УФФФШЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭМ
    Г 81Г 82Г 83Г 84Г 85Г 86Г 87Г 88Г 89Г
    УФФФХФФФСФФФСФФФСФФФСФФФСФФФСФФФСФФФй
    Г 90Г
    РФФФй }

  { - empty squares }
  for GLB_i := 10 to 80 do
    GLB_mainboard.board[GLB_i] := Empty;
  { - edges }
  for GLB_i := 0 to 9 do
    GLB_mainboard.board[GLB_i] := Border;
  for GLB_i := 81 to 90 do
    GLB_mainboard.board[GLB_i] := Border;
  GLB_mainboard.board[18] := Border;
  GLB_mainboard.board[27] := Border;
  GLB_mainboard.board[36] := Border;
  GLB_mainboard.board[45] := Border;
  GLB_mainboard.board[54] := Border;
  GLB_mainboard.board[63] := Border;
  GLB_mainboard.board[72] := Border;
  { - 4 initial stones }
  GLB_mainboard.board[41] := Black;
  GLB_mainboard.board[49] := Black;
  GLB_mainboard.board[40] := White;
  GLB_mainboard.board[50] := White;
  { - possible moves }
  for GLB_i := 30 to 33 do
    GLB_mainboard.board[GLB_i] := Possible;
  for GLB_i := 57 to 60 do
    GLB_mainboard.board[GLB_i] := Possible;
  GLB_mainboard.board[39] := Possible;
  GLB_mainboard.board[42] := Possible;
  GLB_mainboard.board[48] := Possible;
  GLB_mainboard.board[51] := Possible;
  { - side to move }
  GLB_mainboard.side2move := Black;
  { - null last move }
  GLB_mainboard.lastmovenull := False;
  { - empty squares }
  GLB_mainboard.Empty_Squares := 60;


  { draw board }

  { - draw green board background }
  Draw_Board_Background;

  { - draw board stones/values/etc. }
  { --- set up copy of main board TOTALLY DIFFERENT from main board
        so that "DRAW BOARD" 'updates' (draws) *entire* board }
  for GLB_i := 0 to 90 do
    GLB_mainboard_copy.board[GLB_i] := Border;
  Draw_Board(GLB_mainboard,GLB_mainboard_copy);


  { initialize vars }

  { - search depth }
  GLB_Depth := Initial_Depth;

  { - user cursor position }
  GLB_user_x := 0;
  GLB_user_y := 0;

  { - consecutive null moves }
  GLB_Consecutive_Null_Moves := 0;

  { - perfect end game play }
  GLB_Perfect_End_Game_Play := false;


  (*
  {--640x480x16 color mode (mode 12h)-------------------------------------}
  procedure SetWritePlane(n: byte); {plane=0..3, use 1 shl plane, or combination}
  procedure SetReadPlane(n: byte); {0..3}
  procedure ClearPlane; {clears currently set write planes}
  procedure printchar16(ascii: char; x,y: word; fptr: pointer);
  procedure printstring16(x,y: byte; s: string; fptr: pointer);
  procedure printchar8(ascii: char; x,y: word; fptr: pointer);
  procedure printstring8(x,y: byte; s: string; fptr: pointer);
  procedure savescreen12h(filename: string);
  procedure loadscreen12h(filename: string);
  *)


  { draw screen graphics/information }
  SetWritePlane(15);
  { - title }
  PrintString16(51,0,'WipeOut '+version+'  Mar. 23 / 1998',sys16.FontPtr);
  { - bottom title }
  PrintString16(1,29,'WipeOut '+version+' (c) 1998 Matthew J. Doucette - 100019062 - COMP 3653 - Soft. Eng.',sys16.FontPtr);
  { - border }
  SetColor(Dividers_color);
  Line(639,19,639,462);
{  Line(0,479,639,479);}
  Line(0,400,0,462);
  Line(0,462,639,462);
  { - score }
  Line(400,19,639,19);
  PrintString8(51,3,'* Black: 2',sys8.FontPtr);
  PrintString8(51,4,'  White: 2',sys8.FontPtr);
  Line(400,44,639,44);
  { - computer thinking info }
  PrintString8(51,6, '         Depth:',sys8.FontPtr);
  PrintString8(51,7, ' Maximum Depth:',sys8.FontPtr);
  PrintString8(51,8, 'Positions Seen:',sys8.FontPtr);
  PrintString8(51,9, 'Leaf Positions:',sys8.FontPtr);
  PrintString8(51,10,'          Time:',sys8.FontPtr);
  PrintString8(51,11,'       Pos/Sec:',sys8.FontPtr);
  PrintString8(51,12,' Empty Squares: 60',sys8.FontPtr);
  Line(400,108,639,108);


  repeat { infinite loop }

    Find_Legal_Moves(GLB_mainboard,GLB_movelist);


    if GLB_movelist[0] > 0

      { LEGAL MOVE AVAILABLE }
      then
        begin

          { restart null move count }
          GLB_Consecutive_Null_Moves := 0;

          { black/white human/computer moves }
          if GLB_Player[GLB_mainboard.side2move] = Human
            then GLB_move := Get_User_Move
            else GLB_move := Get_Computer_Move;

          { make copy of main board before updating with new move }
          GLB_mainboard_copy := GLB_mainboard;

          { print empty squares on screen }
          str(GLB_mainboard.Empty_Squares,GLB_string);
          PrintString8(67,12,GLB_string+' ',sys8.FontPtr);

          { make move }
          Make_Move(GLB_mainboard,GLB_move);

          { print move value on screen }
          str(GLB_mainboard.Empty_Squares,GLB_string);
          PrintString8(67,12,GLB_string+' ',sys8.FontPtr);

          { game over?}
          if GLB_mainboard.Empty_Squares = 0 then goto GLB_Game_Over;

          { perfect play? How many emtpies? }
          if GLB_mainboard.Empty_Squares <=
             Empty_Squares_for_Perfect_End_Game_Play
            then GLB_Perfect_End_Game_Play := true;

        end
      { NO LEGAL MOVES AVAILABLE }
      else
        begin

          { update null move countS (notice the "S") }
          { - main board }
          GLB_mainboard.lastmovenull := True;
          { - global variable }
          inc(GLB_Consecutive_Null_Moves);
          if GLB_Consecutive_Null_Moves=2 then goto GLB_Game_Over;

          { not game over, switch players }
          GLB_mainboard.side2move := 1-GLB_mainboard.side2move;

        end;

    Draw_Board(GLB_mainboard,GLB_mainboard_copy);

    Update_Score;

  until false; { infinite loop }


  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  { ---------------------------- END OF GAME ------------------------------ }
  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }

  GLB_Game_Over:


  Draw_Board(GLB_mainboard,GLB_mainboard_copy);
  Update_Score;
  Update_FINAL_Score;
  PrintString8(1,51,'Game Over.',sys8.FontPtr);
  PrintString8(1,53,'Press ESC To Quit.',sys8.FontPtr);

  while Keypressed do ReadKey;
  repeat until (Keypressed) and (ReadKey=#27);


  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  { ---------------------------- END OF PROGRAM --------------------------- }
  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  { ----------------------------------------------------------------------- }
  GLB_Quit:

  { Go back to text mode }
  CloseGraph;

  Print_End_Title;
  Writeln('You''ve just been wiped out.');

end.