forked from KolibriOS/kolibrios
270 lines
5.6 KiB
PHP
270 lines
5.6 KiB
PHP
; C4
|
|
; Copyright (c) 2002 Thomas Mathys
|
|
; killer@vantage.ch
|
|
;
|
|
; This file is part of C4.
|
|
;
|
|
; C4 is free software; you can redistribute it and/or modify
|
|
; it under the terms of the GNU General Public License as published by
|
|
; the Free Software Foundation; either version 2 of the License, or
|
|
; (at your option) any later version.
|
|
;
|
|
; C4 is distributed in the hope that it will be useful,
|
|
; but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
; GNU General Public License for more details.
|
|
;
|
|
; You should have received a copy of the GNU General Public License
|
|
; along with C4; if not, write to the Free Software
|
|
; Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
|
|
%ifndef _AI_INC
|
|
%define _AI_INC
|
|
|
|
|
|
INFTY equ 1000000000
|
|
|
|
|
|
|
|
section .data
|
|
|
|
; table used to perform some primitive move "ordering":
|
|
; middle columns which are usually more important are
|
|
; searched first.
|
|
moveorder dd 1,7,2,6,3,5,4
|
|
|
|
; table used for static evaluation.
|
|
; this table is taken from 4st attack: it is ways better
|
|
; than the table i used before =)
|
|
evaltable: dd 0, 0, 0, 0, 0, 0, 0, 0, 0
|
|
dd 0, 3, 4, 5, 7, 5, 4, 3, 0
|
|
dd 0, 4, 6, 8,10, 8, 6, 4, 0
|
|
dd 0, 5, 8,12,13,12, 8, 5, 0
|
|
dd 0, 5, 8,12,13,12, 8, 5, 0
|
|
dd 0, 4, 6, 8,10, 8, 6, 4, 0
|
|
dd 0, 3, 4, 5, 7, 5, 4, 3, 0
|
|
dd 0, 0, 0, 0, 0, 0, 0, 0, 0
|
|
|
|
|
|
|
|
section .bss
|
|
|
|
cpulevel resd 1 ; level of current cpu player
|
|
bestval resd 1 ; value of best move found so far
|
|
nbestmoves resd 1 ; # of best moves found so far
|
|
bestmoves resd 7 ; array to hold all best moves
|
|
|
|
|
|
|
|
section .text
|
|
|
|
|
|
|
|
;**********************************************************
|
|
; aiGetMove
|
|
; returns a move for a computer player
|
|
;
|
|
; input : eax = cpu level ( >= 1)
|
|
; output : eax = move
|
|
; destroys : everything
|
|
;**********************************************************
|
|
aiGetMove:
|
|
|
|
; initialize variables
|
|
mov [cpulevel],eax
|
|
mov dword [bestval],-INFTY
|
|
mov dword [nbestmoves],0
|
|
|
|
; try every move
|
|
mov ecx,6
|
|
.evalmoves:
|
|
|
|
; get move to make from move order table
|
|
mov eax,[moveorder+ecx*4]
|
|
|
|
; if this is an invalid move, continue with next move
|
|
BOARDISVALIDMOVE eax
|
|
jz .nextmove
|
|
|
|
; make move for current player
|
|
mov ebx,[currentplayer]
|
|
call boardMakeMove
|
|
|
|
; evaluate move
|
|
push eax ; save move #
|
|
push ecx ; save loop counter
|
|
push dword [cpulevel] ; ply
|
|
mov ebx,[currentplayer] ; player
|
|
BOARDGETOTHERPLAYER ebx
|
|
push ebx
|
|
push dword -INFTY ; alpha
|
|
push dword INFTY ; beta
|
|
call alphabeta
|
|
neg eax ; damn, how could i forget this ???
|
|
mov ebx,eax ; save result for later
|
|
pop ecx ; restore loop counter
|
|
pop eax ; restore move #
|
|
|
|
; undo move (eax = move #)
|
|
call boardUndoMove
|
|
|
|
; let's see wether we have a new best move
|
|
cmp ebx,[bestval] ; new best value found ?
|
|
jle .nonewbestval
|
|
mov [bestval],ebx ; yes -> save it
|
|
mov dword [nbestmoves],1 ; delete everything that was in the list
|
|
mov [bestmoves+0],eax ; save move number in list
|
|
jmp short .nextmove ; continue with next move
|
|
.nonewbestval:
|
|
cmp ebx,[bestval] ; another best value found ?
|
|
jne .nextmove
|
|
mov ebx,[nbestmoves] ; yes -> add move to list
|
|
mov [bestmoves+ebx*4],eax
|
|
inc dword [nbestmoves]
|
|
|
|
.nextmove:
|
|
dec ecx
|
|
js .done
|
|
jmp .evalmoves
|
|
.done:
|
|
|
|
; randomly pick one of the best moves
|
|
call rand ; rand() % nbestmoves
|
|
xor edx,edx
|
|
div dword [nbestmoves]
|
|
mov eax,[bestmoves+edx*4] ; get move from list
|
|
ret
|
|
|
|
; test code : pick first move from list
|
|
mov eax,[bestmoves+0]
|
|
ret
|
|
|
|
|
|
|
|
;**********************************************************
|
|
; alphabeta
|
|
;
|
|
; input : see below
|
|
; output : eax = move value
|
|
; destroys : everything
|
|
;**********************************************************
|
|
alphabeta:
|
|
|
|
%define ply (ebp+20)
|
|
%define player (ebp+16)
|
|
%define alpha (ebp+12)
|
|
%define beta (ebp+ 8)
|
|
|
|
enter 0,0
|
|
|
|
; win for other player -> end search
|
|
mov eax,[player]
|
|
BOARDGETOTHERPLAYER eax
|
|
call boardIsWin
|
|
or eax,eax
|
|
jz .nowin
|
|
mov eax,-1000000
|
|
mov ebx,[ply]
|
|
shl ebx,10
|
|
sub eax,ebx
|
|
leave
|
|
ret 4*4
|
|
.nowin:
|
|
; board full but no win -> draw -> end search
|
|
BOARDISFULL
|
|
jnz .notfull
|
|
xor eax,eax
|
|
leave
|
|
ret 4*4
|
|
.notfull:
|
|
; max search depth reached -> do static evaluation
|
|
cmp dword [ply],0
|
|
je .staticeval
|
|
|
|
|
|
; for each move
|
|
mov ecx,6
|
|
.evalmoves:
|
|
|
|
; while (alpha < beta)
|
|
mov eax,[alpha]
|
|
cmp eax,[beta]
|
|
jge .done
|
|
|
|
; pick move from move order table
|
|
mov eax,[moveorder+ecx*4]
|
|
|
|
; invalid move ? if so, continue with next move
|
|
BOARDISVALIDMOVE eax
|
|
jz .nextmove
|
|
|
|
; make move for current player
|
|
mov ebx,[player]
|
|
call boardMakeMove
|
|
|
|
; evaluate move
|
|
push eax
|
|
push ecx
|
|
mov eax,[ply] ; ply = ply-1
|
|
dec eax
|
|
push eax
|
|
mov ebx,[player] ; player = other player
|
|
BOARDGETOTHERPLAYER ebx
|
|
push ebx
|
|
mov ecx,[beta] ; alpha = -beta
|
|
neg ecx
|
|
push ecx
|
|
mov edx,[alpha] ; beta = -alpha
|
|
neg edx
|
|
push edx
|
|
call alphabeta
|
|
neg eax
|
|
|
|
; new alpha ?
|
|
cmp eax,[alpha]
|
|
jle .nonewalpha
|
|
mov [alpha],eax ; yes -> save it
|
|
.nonewalpha:
|
|
pop ecx
|
|
pop eax
|
|
|
|
; undo move
|
|
call boardUndoMove
|
|
|
|
.nextmove: ; evaluate next move
|
|
dec ecx
|
|
jns .evalmoves
|
|
|
|
.done:
|
|
mov eax,[alpha]
|
|
leave
|
|
ret 4*4
|
|
|
|
; static evaluation
|
|
.staticeval:
|
|
xor eax,eax
|
|
mov esi,BWIDTH*BHEIGHT-1
|
|
.l:
|
|
mov ebx,[board+esi*4] ; get stone from board
|
|
cmp ebx,[player] ; player's stone ?
|
|
jne .notplayer ; nope -> go on
|
|
add eax,[evaltable+esi*4] ; yes -> add stone value to eax
|
|
jmp .next ; next stone
|
|
.notplayer:
|
|
cmp ebx,EMPTY ; other player's stone ?
|
|
je .empty ; nope -> go on
|
|
sub eax,[evaltable+esi*4] ; yes -> sub stone value from eax
|
|
.empty:
|
|
|
|
.next: ; next stone
|
|
dec esi
|
|
jns .l
|
|
leave ; eax contains static value
|
|
ret 4*4
|
|
|
|
%undef ply
|
|
%undef player
|
|
%undef alpha
|
|
%undef beta
|
|
|
|
%endif |