Karoshi MSX Community

Desarrollo MSX => Rutinas - Snipets => Mensaje iniciado por: pitpan en 01 de Septiembre de 2009, 12:52:50 pm



Título: Automated goban for MSX
Publicado por: pitpan en 01 de Septiembre de 2009, 12:52:50 pm
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.

Código:
; 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.



Título: Re: Automated goban for MSX
Publicado por: Dioniso en 01 de Septiembre de 2009, 02:52:04 pm
Gracias por compartir!  :griel:


Título: Re: Automated goban for MSX
Publicado por: Jon_Cortazar en 02 de Septiembre de 2009, 09:38:31 am
Cojonudo!! He estado comprobando situaciones complejas y el comportamiento es más que perfecto. Como siempre, muy lejos de lo que yo nunca conseguiré en programación :-[

Y encima, has publicado un algo! Doble buena noticia, ya que te ayudará a "reactivarte"! ¡¡Ánimo, Edu!! :griel:


Título: Re: Automated goban for MSX
Publicado por: pitpan en 02 de Septiembre de 2009, 10:03:08 am
El código publicado fue programado en marzo, en plena vorágine de mi adicción al juego de go, y aunque es funcional puede y debe ser mejorado, ya que como está preparado para tableros de tamaño arbitrario (hasta 254 x 254), se ve obligado a emplear aritmética de 16 bits, lo cual complica bastante todas las operaciones. Para el juego de tsumegos, bastaría con aritmética de 8 bits (tamaño máximo de hasta 14 x 14), más que suficiente para mis propósitos. Con eso conseguiría que el UNDO no sea tan lento, ya que lo que hace es reconstruir toda la partida desde su inicio hasta el movimiento N-1.

Por otra parte, tengo un intérprete parcial del formato SGF, que no es más que una máquina de estados finitos con mucha querencia a las bifurcaciones, que sería la otra parte necesaria para el juego de tsumegos.

Mi intención, evidentemente, es hacer un poco de campaña de difusión de este juego entre el colectivo MSXero, con un pequeño tutorial intereactivo - las reglas son muy sencillas - y una colección de problemas con dificultad creciente.

Y ahora la confesión vergonzosa: traté de hacer esto mismo en C para PC y estoy tan intoxicado por el ensamblador que no me salía, así que no tuve otro remedio que ponerme con mi querido asMSX y darle cañita a bajo nivel al Z80. Es curioso, pero el bajo nivel me está incapacitando para la vida moderna del programador  :(

Puestos a ser menos obsoleto, la idea es incluir soporte para ratón y, lo que es peor, un motor gráfico completo para MSX2/MSX2+ separado del "normal" para MSX1. Al menos me actualizaré un poco en cuanto a conocimientos MSXeros...


Título: Re: Automated goban for MSX
Publicado por: Jon_Cortazar en 02 de Septiembre de 2009, 10:24:19 am
Robs, voy a poner el rom y el source en el listado de RKOS. Me podrías enviar cuando tengas un ratín la última distribución del G-Monkey, para así tener esa zona de los foros actualizada?? Thnx! ;)

Citar
traté de hacer esto mismo en C para PC y estoy tan intoxicado por el ensamblador que no me salía, así que no tuve otro remedio que ponerme con mi querido asMSX y darle cañita a bajo nivel al Z80

LMAO :D


Título: Re: Automated goban for MSX
Publicado por: GuyveR800 en 02 de Septiembre de 2009, 11:59:29 am
Interesting! Thanks for your continued efforts to publish source code in a way beginner programmers will be able to learn from it.

As a side note: It surprises me that this english forumpost is replied to in spanish only, by people I know are great at english. Then again, I haven't visited Karoshi forums in a long time (actually this reminds me to visit MSX Posse forums again too) so maybe it has become normal. ???

Also funny that all labels in the source are english, except BUCLE :D


Título: Re: Automated goban for MSX
Publicado por: Jon_Cortazar en 02 de Septiembre de 2009, 01:03:57 pm
hey G! In fact you're right, we should continue in english: it is just that this "snippets" board is out from both "spanish" and "english" board groups, and sometimes they get quite anarchic regarding language use ;). btw, it is always nice to have you here :)


Título: Re: Automated goban for MSX
Publicado por: pitpan en 02 de Septiembre de 2009, 01:32:23 pm
Hi, Guyver!

Yes, you're right. I started the topic in English but we soon switched to Spanish. So, lets go back to the lingua franca. When it comes to labels and programming conventions, I try to use English as much as possible, but when I introduce some temporary code, it is usually labeled and commented in Spanish. BUCLE means, of course, LOOP - and it is just temporary code to show that the engine actually works ;)

In other productions you could find the all-time favourite KAKA label, that means in phonetic translation, shit. Very handy and useful when coding in a hurry :D


Título: Re: Automated goban for MSX
Publicado por: Dioniso en 02 de Septiembre de 2009, 01:35:19 pm
Yes, you're right. I started the topic in English but we soon switched to Spanish.

Oops! It's true. It's my fault...


Título: Re: Automated goban for MSX
Publicado por: kabish en 02 de Septiembre de 2009, 07:53:47 pm
Thanks for sharing your code. You are very brave.  :saimazoom:

I never play 'Go' but rules seems to be easy to learn. how about to play go in a ru, it's the best option to make attention to msx users.

Citar
traté de hacer esto mismo en C para PC y estoy tan intoxicado por el ensamblador que no me salía, así que no tuve otro remedio que ponerme con mi querido asMSX y darle cañita a bajo nivel al Z80

hey, I experience the same.  ;D


Título: Re: Automated goban for MSX
Publicado por: GuyveR800 en 05 de Septiembre de 2009, 01:40:19 pm
I've seen some tutorials on japanese television about Go and it seems to be a very strategic game, but it seems indeed easier to understand than e.g. Mahjong ;)
Writing a good Artificial Intelligence for Go is the biggest challenge, I think.

I'm looking forward to pitpan's finished product, but may I also suggest someone do a MSX2 version with mouse support? :D

By the way, anyone interested in doing Shogi (also known as Japanese chess)?  ::phone::


Título: Re: Automated goban for MSX
Publicado por: pitpan en 06 de Septiembre de 2009, 02:07:55 pm
Patriek: in my own reply in Spanish I said that I would code such mouse support and MSX2/2+ versions. Therefore, NO PROBLEMO! I would ask for help 'cause I've no V9938 experience so far.