Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. ; C4
  2. ; Copyright (c) 2002 Thomas Mathys
  3. ; killer@vantage.ch
  4. ;
  5. ; This file is part of C4.
  6. ;
  7. ; C4 is free software; you can redistribute it and/or modify
  8. ; it under the terms of the GNU General Public License as published by
  9. ; the Free Software Foundation; either version 2 of the License, or
  10. ; (at your option) any later version.
  11. ;
  12. ; C4 is distributed in the hope that it will be useful,
  13. ; but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. ; GNU General Public License for more details.
  16. ;
  17. ; You should have received a copy of the GNU General Public License
  18. ; along with C4; if not, write to the Free Software
  19. ; Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20.  
  21. %ifndef _AI_INC
  22. %define _AI_INC
  23.  
  24.  
  25. INFTY           equ     1000000000
  26.  
  27.  
  28.  
  29.         section .data
  30.  
  31. ; table used to perform some primitive move "ordering":
  32. ; middle columns which are usually more important are
  33. ; searched first.
  34. moveorder       dd      1,7,2,6,3,5,4
  35.  
  36. ; table used for static evaluation.
  37. ; this table is taken from 4st attack: it is ways better
  38. ; than the table i used before =)
  39. evaltable:      dd       0, 0, 0, 0, 0, 0, 0, 0, 0
  40.                 dd       0, 3, 4, 5, 7, 5, 4, 3, 0
  41.                 dd       0, 4, 6, 8,10, 8, 6, 4, 0
  42.                 dd       0, 5, 8,12,13,12, 8, 5, 0
  43.                 dd       0, 5, 8,12,13,12, 8, 5, 0
  44.                 dd       0, 4, 6, 8,10, 8, 6, 4, 0
  45.                 dd       0, 3, 4, 5, 7, 5, 4, 3, 0
  46.                 dd       0, 0, 0, 0, 0, 0, 0, 0, 0
  47.  
  48.  
  49.  
  50.         section .bss
  51.  
  52. cpulevel        resd    1       ; level of current cpu player
  53. bestval         resd    1       ; value of best move found so far
  54. nbestmoves      resd    1       ; # of best moves found so far
  55. bestmoves       resd    7       ; array to hold all best moves
  56.  
  57.  
  58.  
  59.         section .text
  60.  
  61.  
  62.  
  63. ;**********************************************************
  64. ; aiGetMove
  65. ; returns a move for a computer player
  66. ;
  67. ; input         :       eax = cpu level ( >= 1)
  68. ; output        :       eax = move
  69. ; destroys      :       everything
  70. ;**********************************************************
  71. aiGetMove:
  72.  
  73.         ; initialize variables
  74.         mov [cpulevel],eax
  75.         mov dword [bestval],-INFTY
  76.         mov dword [nbestmoves],0
  77.        
  78.         ; try every move
  79.         mov ecx,6
  80. .evalmoves:
  81.  
  82.         ; get move to make from move order table
  83.         mov eax,[moveorder+ecx*4]
  84.        
  85.         ; if this is an invalid move, continue with next move
  86.         BOARDISVALIDMOVE eax
  87.         jz .nextmove
  88.  
  89.         ; make move for current player
  90.         mov ebx,[currentplayer]
  91.         call boardMakeMove
  92.        
  93.         ; evaluate move
  94.         push eax                        ; save move #
  95.         push ecx                        ; save loop counter
  96.         push dword [cpulevel]           ; ply
  97.         mov ebx,[currentplayer]         ; player
  98.         BOARDGETOTHERPLAYER ebx
  99.         push ebx
  100.         push dword -INFTY               ; alpha
  101.         push dword INFTY                ; beta
  102.         call alphabeta
  103.         neg eax                         ; damn, how could i forget this ???
  104.         mov ebx,eax                     ; save result for later
  105.         pop ecx                         ; restore loop counter
  106.         pop eax                         ; restore move #
  107.        
  108.         ; undo move (eax = move #)
  109.         call boardUndoMove
  110.        
  111.         ; let's see wether we have a new best move
  112.         cmp ebx,[bestval]               ; new best value found ?
  113.         jle .nonewbestval
  114.         mov [bestval],ebx               ; yes -> save it
  115.         mov dword [nbestmoves],1        ; delete everything that was in the list
  116.         mov [bestmoves+0],eax           ; save move number in list
  117.         jmp short .nextmove             ; continue with next move
  118. .nonewbestval:
  119.         cmp ebx,[bestval]               ; another best value found ?
  120.         jne .nextmove
  121.         mov ebx,[nbestmoves]            ; yes -> add move to list
  122.         mov [bestmoves+ebx*4],eax
  123.         inc dword [nbestmoves]
  124.  
  125. .nextmove:
  126.         dec ecx
  127.         js .done
  128.         jmp .evalmoves
  129. .done:
  130.        
  131.         ; randomly pick one of the best moves
  132.         call rand                       ; rand() % nbestmoves
  133.         xor edx,edx
  134.         div dword [nbestmoves]
  135.         mov eax,[bestmoves+edx*4]       ; get move from list
  136.         ret
  137.  
  138.         ; test code : pick first move from list
  139.         mov eax,[bestmoves+0]
  140.         ret
  141.  
  142.  
  143.  
  144. ;**********************************************************
  145. ; alphabeta
  146. ;
  147. ; input         :       see below
  148. ; output        :       eax = move value
  149. ; destroys      :       everything
  150. ;**********************************************************
  151. alphabeta:
  152.  
  153. %define ply     (ebp+20)
  154. %define player  (ebp+16)
  155. %define alpha   (ebp+12)
  156. %define beta    (ebp+ 8)
  157.  
  158.         enter 0,0
  159.        
  160.         ; win for other player -> end search
  161.         mov eax,[player]
  162.         BOARDGETOTHERPLAYER eax
  163.         call boardIsWin
  164.         or eax,eax
  165.         jz .nowin
  166.         mov eax,-1000000
  167.         mov ebx,[ply]
  168.         shl ebx,10
  169.         sub eax,ebx
  170.         leave
  171.         ret 4*4
  172. .nowin:
  173.         ; board full but no win -> draw -> end search
  174.         BOARDISFULL
  175.         jnz .notfull
  176.         xor eax,eax
  177.         leave
  178.         ret 4*4
  179. .notfull
  180.         ; max search depth reached -> do static evaluation
  181.         cmp dword [ply],0
  182.         je .staticeval
  183.        
  184.  
  185.         ; for each move
  186.         mov ecx,6
  187. .evalmoves:
  188.  
  189.         ; while (alpha < beta)
  190.         mov eax,[alpha]
  191.         cmp eax,[beta]
  192.         jge .done
  193.  
  194.         ; pick move from move order table
  195.         mov eax,[moveorder+ecx*4]
  196.        
  197.         ; invalid move ? if so, continue with next move
  198.         BOARDISVALIDMOVE eax
  199.         jz .nextmove
  200.        
  201.         ; make move for current player
  202.         mov ebx,[player]
  203.         call boardMakeMove
  204.        
  205.         ; evaluate move
  206.         push eax
  207.         push ecx
  208.         mov eax,[ply]                   ; ply = ply-1
  209.         dec eax
  210.         push eax
  211.         mov ebx,[player]                ; player = other player
  212.         BOARDGETOTHERPLAYER ebx
  213.         push ebx
  214.         mov ecx,[beta]                  ; alpha = -beta
  215.         neg ecx
  216.         push ecx
  217.         mov edx,[alpha]                 ; beta = -alpha
  218.         neg edx
  219.         push edx
  220.         call alphabeta
  221.         neg eax
  222.        
  223.         ; new alpha ?
  224.         cmp eax,[alpha]
  225.         jle .nonewalpha
  226.         mov [alpha],eax                 ; yes -> save it
  227. .nonewalpha:   
  228.         pop ecx
  229.         pop eax
  230.        
  231.         ; undo move
  232.         call boardUndoMove
  233.  
  234. .nextmove:                              ; evaluate next move
  235.         dec ecx
  236.         jns .evalmoves
  237.        
  238. .done:
  239.         mov eax,[alpha]
  240.         leave
  241.         ret 4*4
  242.                
  243.         ; static evaluation
  244. .staticeval:
  245.         xor eax,eax
  246.         mov esi,BWIDTH*BHEIGHT-1
  247. .l:
  248.         mov ebx,[board+esi*4]           ; get stone from board
  249.         cmp ebx,[player]                ; player's stone ?
  250.         jne .notplayer                  ; nope -> go on
  251.         add eax,[evaltable+esi*4]       ; yes -> add stone value to eax
  252.         jmp .next                       ; next stone
  253. .notplayer:
  254.         cmp ebx,EMPTY                   ; other player's stone ?
  255.         je .empty                       ; nope -> go on
  256.         sub eax,[evaltable+esi*4]       ; yes -> sub stone value from eax
  257. .empty:
  258.        
  259. .next:                                  ; next stone
  260.         dec esi
  261.         jns .l
  262.         leave                           ; eax contains static value
  263.         ret 4*4
  264.  
  265. %undef ply
  266. %undef player
  267. %undef alpha
  268. %undef beta
  269.  
  270. %endif