Studying simple AI
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.
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.
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.
Problem with Tic-Tac-Toe is, that - if you don't have a stupid opponent - you can't win anyway.
Remembers me if this... 
https://www.youtube.com/watch?v=F7qOV8xonfY
https://www.youtube.com/watch?v=MpmGXeAtWUw
Yes 
Best you can do is to draw. But you still need to play a perfect game in order not to lose
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).
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.
Oh!! I remember your precalculated map for Bumper Ship Racing, I thought that was a really good idea!!
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.
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 