Hi everyone!
Today I'd like to share with you a go engine. Go, also known as Weiqi or Baduk, is an ancient asian board game and supposedly one of the oldests games known to mankind. You can find more information at
http://sensei.xmp.net or
http://en.wikipedia.org/wiki/Go_(game)
Anyway, this is a simple board (called goban) with automated rules such as killing, lack of liberties and ko (eternity rule). Of course, it is a two player game, although one player alone can use it to study a bit.
From the technical point of view, the code results interesting because it uses heavily recursion techniques for group identification and capture. It also includes a slow-but-secure undo system with unlimited depth.
Controls:
- Cursor keys: select stone position
- Space: put stone
- Backspace: undo one movement
Feel free to modify it. It will probably be the base for a tsumego (life and death problems) game by Karoshi Corp. that will be anounced soon.
; Goban for MSX
; Coded by Eduardo Robsy Petrus
; (c) Karoshi Corporation, 2009
; Assemble with asMSX
.bios
.page 2
.rom
.start INIT
.org 8010h
.db "[RKOS04] MINI GOBAN",1Ah
NAMTBL equ 1800h
SPRTBL equ 3800h
SPRATR equ 1B00h
INIT:
ld a,13
ld [SIZE],a
call INIT32
ld hl,SPR_CURSOR
ld de,SPRTBL
ld bc,8
call LDIRVM
call INIT_GOBAN
xor a
ld [X],a
ld [Y],a
ld [REPLAY],a
call SHOW_GOBAN
jr @@OK
@@BUCLE:
ld a,7
call SNSMAT
cp 0DFh
jr nz,@@PUT
@@STILL:
ld a,7
call SNSMAT
cp 0DFh
jr z,@@STILL
call UNDO_MOVEMENT
@@PUT:
xor a
call GTTRIG
jr z,@@NOK
ld a,[Y]
inc a
ld b,a
ld hl,0000h
ld de,20
@@SUM:
add hl,de
djnz @@SUM
ld a,[X]
inc a
ld e,a
ld d,0
add hl,de
ex de,hl
call PUT_STONE
call SHOW_GOBAN
@@MAKE:
xor a
call GTTRIG
jr nz,@@MAKE
@@NOK:
xor a
call GTSTCK
cp 1
ld hl,Y
jr nz,@@NO_UP
dec [hl]
jr @@OK
@@NO_UP:
cp 5
jr nz,@@NO_DOWN
inc [hl]
jr @@OK
@@NO_DOWN:
ld hl,X
cp 3
jr nz,@@NO_RIGHT
inc [hl]
jr @@OK
@@NO_RIGHT:
cp 7
jr nz,@@BUCLE
dec [hl]
@@OK:
halt
ld a,[Y]
add a
add a
add a
dec a
ld hl,SPRATR
call WRTVRM
ld a,[X]
add a
add a
add a
ld hl,SPRATR+1
call WRTVRM
ld a,0
ld hl,SPRATR+2
call WRTVRM
ld a,8
ld hl,SPRATR+3
call WRTVRM
@@RELEASE:
xor a
call GTSTCK
or a
jr nz,@@RELEASE
jp @@BUCLE
UNDO_MOVEMENT:
; Reduce movement number
ld hl,[MOVEMENT]
; Check if there are movements to undo
ld a,h
or l
ret z
; Decrease movement
dec hl
push hl
call INIT_GOBAN
pop bc
; Check if there are movements to undo
ld a,c
or b
jr nz,@@CONTINUE
call SHOW_GOBAN
ret
@@CONTINUE:
ld a,1
ld [REPLAY],a
; Kifu pointer
ld hl,KIFU
; Replay
@@REPLAY:
ld e,[hl]
inc hl
ld d,[hl]
inc hl
push hl
push bc
call PUT_STONE
pop bc
pop hl
dec bc
ld a,b
or c
jr nz,@@REPLAY
call SHOW_GOBAN
xor a
ld [REPLAY],a
ret
PUT_STONE:
; Parameters: DE - position
; Store movement
ld hl,[MOVEMENT]
add hl,hl
ld bc,KIFU
add hl,bc
ld [hl],e
inc hl
ld [hl],d
; Copy goban positions
push de
ld hl,GOBAN
ld de,AUX
ld bc,20*20
ldir
pop de
; Check if it is occupied
ld hl,AUX
add hl,de
ld a,[hl]
or a
ret nz
; Place stone
ld a,[PLAYER]
ld [hl],a
; Clear kill count
xor a
ld [KILL],a
ld [KILL+1],a
ld a,[PLAYER]
xor 3
ld [PLAYER],a
push de
dec de
call CHECK_GROUP
pop de
push de
inc de
call CHECK_GROUP
pop hl
push hl
ld bc,-20
add hl,bc
ex de,hl
call CHECK_GROUP
pop hl
push hl
ld bc,20
add hl,bc
ex de,hl
call CHECK_GROUP
pop de
ld a,[REPLAY]
or a
jr nz,@@DONE
ld a,[KILL]
ld b,a
ld a,[KILL+1]
or b
jr z,@@SUICIDE
; Check ko rule
ld hl,AUX
ld de,KO
ld bc,20*20
@@COMPARE:
ld a,[de]
xor [hl]
jr nz,@@DONE
inc de
inc hl
dec bc
ld a,b
or c
jr nz,@@COMPARE
ld a,[PLAYER]
xor 3
ld [PLAYER],a
ret
@@SUICIDE:
ld a,[PLAYER]
xor 3
ld [PLAYER],a
call CHECK_GROUP
ld a,[LIBERTY]
or a
ret z
ld a,[PLAYER]
xor 3
ld [PLAYER],a
@@DONE:
ld a,[PLAYER]
xor 3
add a
ld
c,a
ld b,0
ld hl,CAPTURES-2
add hl,bc
push hl
ld e,[hl]
inc hl
ld d,[hl]
ld hl,[KILL]
add hl,de
pop de
ex de,hl
ld [hl],e
inc hl
ld [hl],d
ld hl,GOBAN
ld de,KO
ld bc,20*20
ldir
ld hl,AUX
ld de,GOBAN
ld bc,20*20
ldir
ld hl,[MOVEMENT]
inc hl
ld [MOVEMENT],hl
ret
CHECK_GROUP:
; Parameters: DE - position;
xor a
ld [LIBERTY],a
call COUNT_LIBERTIES
ld hl,AUX+20
ld bc,20*19
@@CHECK:
ld a,[LIBERTY]
or a
jr nz,@@ALIVE
ld a,[PLAYER]
or 4
cp [hl]
jr nz,@@ALIVE
xor a
ld [hl],a
push hl
ld hl,[KILL]
inc hl
ld [KILL],hl
pop hl
@@ALIVE:
ld a,[hl]
and 03h
ld [hl],a
inc hl
dec bc
ld a,b
or c
jr nz,@@CHECK
ret
COUNT_LIBERTIES:
; Parameters: DE - position;
ld b,4
ld hl,AUX
add hl,de
ld a,[hl]
or a
jr nz,@@CONTINUE
; Mark and count liberty
ld [hl],b
ld hl,LIBERTY
inc [hl]
ret
; Check colour of stone
@@CONTINUE:
ld a,[PLAYER]
cp [hl]
ret nz
; Mark stone
or b
ld [hl],a
; Recursive
push de
inc de
call COUNT_LIBERTIES
pop de
push de
dec de
call COUNT_LIBERTIES
pop hl
push hl
ld bc,-20
add hl,bc
ex de,hl
call COUNT_LIBERTIES
pop hl
ld bc,20
add hl,bc
ex de,hl
call COUNT_LIBERTIES
ret
SHOW_GOBAN:
ld hl,NAMTBL
ld de,GOBAN+1+20
ld a,19
ld b,a
ld c,a
@@ROW:
push bc
ld b,c
@@COLUMN:
ld a,[de]
or a
jr nz,@@OK
ld a,21
@@OK:
cp 3
jr nz,@@NOK
ld a,0
@@NOK:
; add 48
call WRTVRM
inc hl
inc de
djnz @@COLUMN
inc de
ld bc,32-19
add hl,bc
pop bc
djnz @@ROW
ret
INIT_GOBAN:
; Check data
ld hl,0
ld [CAPTURES],hl
ld [CAPTURES+2],hl
ld [MOVEMENT],hl
; Set player
ld a,1
ld [PLAYER],a
; Define borders
ld hl,GOBAN
ld bc,20*20
@@BORDERS:
ld [hl],3
inc hl
dec bc
ld a,b
or c
jr nz,@@BORDERS
; Clear playing grid
ld hl,GOBAN+1+20
ld a,[SIZE]
ld c,a
ld e,a
ld a,20
sub e
ld e,a
ld d,0
ld a,c
@@ROW:
ld b,a
@@COLUMN:
ld [hl],d
inc hl
djnz @@COLUMN
add hl,de
dec c
jr nz,@@ROW
ret
SPR_CURSOR:
db 0FFh,81h,81h,81h,81h,81h,81h,0FFh
print $-INIT
.page 3
Y: ds 1
X: ds 1
SIZE:
ds 1
PLAYER:
ds 1
REPLAY:
ds 1
LIBERTY:
ds 1
MOVEMENT:
ds 2
KILL:
ds 2
CAPTURES:
ds 4
GOBAN:
ds 20*20
AUX:
ds 20*20
KO:
ds 20*20
KIFU:
ds 361*2
print $-0C000h
For the lazy people, I've also uploaded a ROM version. Please note that the compiled code is less than 700 bytes at the moment.
