Studying simple AI

Page 1/2
| 2

By Chilly Willy

Expert (88)

Chilly Willy's picture

08-06-2022, 21:14

I am trying to work out some AI for a simple game.

Is there Tic Tac Toe source code for the MSX1 in z80 assembly language?

I looked everywhere but apparently my google skills are subpar.

Better yet, if someone can share a Pac-Man style source code written in Z80 assembly language for the MSX1 that would be cool too.

But mostly the Tic-Tac-Toe if anything.

Login or register to post comments

By Prodatron

Paragon (1824)

Prodatron's picture

08-06-2022, 22:13

Pac-Man for MSX/SymbOS is open source and available here:
http://www.symbos.org/appinfo.htm?00010
This won't help you for displaying stuff on MSX1, as SymbOS has its abstract way of displaying things onto the "desktop". But you maybe could have a look at the so-called "AI" and sprite control/movement etc.

By T.R.

Resident (45)

T.R.'s picture

08-06-2022, 22:14

Tic tac toe (and similar two player games) can be solved with the famous mini-max algorithm. This should be easy to implement. It basically performs a smart search through the game tree. Complexity is exponential in the depth of the tree which might be problematic in combination with the limitations of MSX. However, tic tac toe does not have a deep game tree, so should be no problem on an MSX. However, I think a pac-man AI would require very different techniques.

By ducasp

Hero (608)

ducasp's picture

08-06-2022, 22:36

Real arcade pac-man doesn't have an A.I. per say, it has a few rules for each ghosts that will determine what they do every intersection of the maze... Something like this:

https://pacman.fandom.com/wiki/Maze_Ghost_AI_Behaviors

Is used every time a ghost is near a corner if I'm not mistake. Now, that doesn't help with Tic-Tac-Toe, but then, calculating every possible movement up to n-turns (and considering oponent possibilities as well) where n would be the difficult level is something achievable on a MSX, you can also pre-program some plays to evaluate those pre-programmed scenarios first to be faster whenever they apply.

By Prodatron

Paragon (1824)

Prodatron's picture

08-06-2022, 22:49

Problem with Tic-Tac-Toe is, that - if you don't have a stupid opponent - you can't win anyway.
Remembers me if this... Tongue
https://www.youtube.com/watch?v=F7qOV8xonfY
https://www.youtube.com/watch?v=MpmGXeAtWUw

By T.R.

Resident (45)

T.R.'s picture

08-06-2022, 23:08

Yes Smile Best you can do is to draw. But you still need to play a perfect game in order not to lose

By santiontanon

Paragon (1696)

santiontanon's picture

09-06-2022, 22:34

PacMan and Tic-Tac-Toe are games that would use very different AI algorithms though, So, one will not be helpful for the other:
- Tic-Tac-Toe-style games are typically solved using game-tree search (like the "minimax" algorithm mentioned above). These algorithms are suitable for turn-based games, with a discrete action set.
- Pam-Man style games are usually addressed using much simpler techniques. The most common are (probabilistic) state-machines, and also simple hard-coded rules.

Neither should be too hard to implement in Z80 assembler, although there are many common optimization tricks usually used in practical implementations of minimax-style algorithms that you might not find in textbooks. So, if you decide to go that route, I can give you some advice (I taught the "Game AI" class in my university for many years haha, so, happy to help out here).

By Uninteresting

Champion (338)

Uninteresting's picture

09-06-2022, 23:06

What they said -- what kind of AI to use is very much case-dependent.

In my card game (Turfy), I basically used a reduced version of the min-max tree -- fewer move options to make the search faster, since otherwise the opponent's turn might've taken hours or days. I don't know if that source code could be of any use, since it was my first game in ASM and the fanciest part of the code was to use recursion when planning to play a card from the hand.

For Bumper Ship Racing (a real-time racing game), I had made a precalculated map where each 16*16px block had the X and Y deltas to aim for. This AI ended up being too good, even if I had optimized it with wrong parameters. The AI ignored the player completely.

Neither source code is currently available online, but if you're not in a hurry, I think I can upload those to Github at some point.

By santiontanon

Paragon (1696)

santiontanon's picture

10-06-2022, 00:37

Oh!! I remember your precalculated map for Bumper Ship Racing, I thought that was a really good idea!!

By Chilly Willy

Expert (88)

Chilly Willy's picture

11-06-2022, 04:02

It wasn't just to know a formula but also how to implement it in Z80 assembly game.

A lot of books out there are title "Great Formulas for Programing"
Then when you read it they give this convoluted equation instead of actually how to use it.

I would also figure that Tic Tac Toe is not giving away trade secrets as far as a game.

By Uninteresting

Champion (338)

Uninteresting's picture

11-06-2022, 09:28

This probably isn't useful, but I uploaded Turfy source code to github.

This won't compile (no toolchain to produce the graphics binaries present), the code is absolutely horrible (my first ASM project ever) and it's not simple, but the label CPUTurn marks the start of the interesting part. SimpleAI contains the "minmax" search, although it completely ignores what the player can do and instead only looks for the best spots to place its cards in and move so it's basically just "max search". Min aspect comes to play only when counting the effect of claiming areas -- placing the first card is 3 points, placing over one opponent's card is 5 points (2 for the CPU, 3 away from the player), and so on. These points are stored at StackPoints.

Some simplifications were made:

Quote:

I didn't do so much optimization as reducing the search space by two simplifications. First, do not plan that many moves ahead. The more moves the AI plans ahead, the less reliable the information becomes anyway. By limiting the plays to just two plays ahead of the current one, the number of plays to evaluate drops drastically. Second, limit the order in which the AI plans to play its cards: never plan to play a lower card after a higher one, since it's usually better to hold on to high cards. The first shrinks the number of plays to evaluate to 0.03% and the second change drops it further to 0.38% of that, to "only" around 20,000 plays.

In reality, the number of plays evaluated are far, far below those (by orders of magnitude), but even in practice, the time spent in determining the next move dropped from hours to a few seconds.

As for Bumper Ship Racing, here's the AI routine with hopefully self-explainatory subroutine labels for those outside this snippet. This is called for every AI-controlled racer. Since this is a real-time game, there are no loops.

AI:
	;; (IX) is the racer's record
	;; 1. Find the address with the track-specific info for the AI
	ld a, (ix + 0)
	add a, 8
	and $f0 ;; This is neatly now the desired row; divide by 16, multiply by 16.
	ld b, a
	ld a, (ix + 2)
	add a, 8
	and $f0
	rrca
	rrca
	rrca
	rrca
	add a, b
	ld l, a
	ld h, 0
	add hl, hl
	ld bc, TRACKMAP_AI
	add hl, bc
	
	;; Now points to the correct memory address for the cell data.
	ld a, (hl)
	ld e, a
	inc hl
	ld a, (hl)
	ld d, a

	;; 2. Parse the data.
	;; DE now has the target speeds, 4 bits from both variables.
	ld a, (ix + 4) ;; Load DY1
	and $0f ;; Should be unnecessary.
	rlca
	rlca
	rlca
	rlca
	ld b, a
	ld a, (ix + 5)
	and $f0
	rrca
	rrca
	rrca
	rrca
	xor b
	ld b, a ;; Now with the actual movement (4+4 bits)
	
	ld a, (ix + 6)
	and $0f ;; Should be unnecessary.
	rlca
	rlca
	rlca
	rlca
	ld c, a
	ld a, (ix + 7)
	and $f0
	rrca
	rrca
	rrca
	rrca
	xor c
	ld c, a ;; Now with the actual movement (4+4 bits)
	
	;; Now, what?
	;; 3. Find the difference between desired momentum (AI map) and reality
	;; Compute the difference to the real desired speed.
	;; Determine which of the eight main directions to turn towards by the sign of the mark.
	ld a, d
	sub c
	add a, 128
	;; The target direction *should* be real dX + 128
	;; A now has (target dX - current dX), so > 0 means thrusting to the right.
	ld d, a
	ld a, e
	sub b
	add a, 128
	;; A now has (target dY - current dY), so > 0 means thrusting to the bottom.
	ld e, a
	;; The target direction *should* be real dY + 128

	ld b, 0 ;; This will have the index to DIRECTION_TABLE
	;; Is A between 128 +- 8?
	ACCEPTED_DRIFT_DIFFERENCE: EQU 8
	
	cp 128-ACCEPTED_DRIFT_DIFFERENCE
	jp c, .aimUp
	cp 128+ACCEPTED_DRIFT_DIFFERENCE
	jp nc, .aimDown
	;; dY alright.
	
  .evaluateX:
	ld a, d
	cp 128-ACCEPTED_DRIFT_DIFFERENCE
	jp c, .aimLeft
	cp 128+ACCEPTED_DRIFT_DIFFERENCE
	jp nc, .aimRight
	;; dX alright.
	
  .aimCalculated:
	ld c, b
	ld b, 0
	ld a, c
	and a
	ret z ;; No need to adjust speed or heading.
	
	;; 4. Determine which way to turn (and turn) and if thrusting is OK (and thrust)
	ld hl, DIRECTION_TABLE
	add hl, bc
	ld b, (hl)
	
	;; B has now the target direction
	ld a, (ix + 8)
	add a, 16
	sub b
	
	cp 2
	jp c, .thrustOK
	cp 16 - 2
	jp c, .postThrust
	cp 16 + 2
	jp c, .thrustOK
	jp .postThrust
	
  .thrustOK:
    push af
	call ThrustForward
	pop af
	
  .postThrust:
	;; 1 - 8, 9 - 16, 17 - (16+8), (16+8)
	cp 16 - 8
	jp c, .turnCW
	cp 16
	jp z, .straightOn
	jp c, .turnCCW
	cp 16 + 8
	jp c, .turnCW
	jp .turnCCW
		
  .turnCW:
	cp 16 - 2 ;; If gap is at most two, then thrusting is OK.
	call nc, ThrustForward
	call RotateRacerCW
	ret

	.straightOn:
	call ThrustForward
	ret

	.turnCCW:
	cp 16 + 2
	call c, ThrustForward
	call RotateRacerCCW
	ret
	
  .aimUp:
	ld b, 6
	jp .evaluateX
	
  .aimDown:
	ld b, 3
	jp .evaluateX
  .aimLeft:
	ld a, b
	add a, 2
	ld b, a
	jp .aimCalculated
  .aimRight:
	ld a, b
	add a, 1
	ld b, a
	jp .aimCalculated
  
DIRECTION_TABLE:
	DB 17, 0, 8, 12, 14, 10, 4, 2, 6
Page 1/2
| 2