Teaching Kids Programming: Videos on Data Structures and Algorithms
Yesterday, we talked about the Apple-Catching Game on Microbit: human plays with two Buttons, A to move the bowl one pixel left, B to move the bowl one pixel right.
Today, we are going to teach Computer how to play using the most simplest AI algorithm – Decision Rules or Decision Trees to do the decision making e.g. Should I move left or right?
Simple AI Algorithm of Decision Rules/Trees
The first AI version is pretty simple and based on the following three rules:
- If the apple is on the right, computer moves right (prediction of moving right is the shortest)
- If the apple is on the left, computer moves left(prediction of moving left is the shortest)
- If the apple is above, computer does nothing (prediction of staying same place is optimal)
This is also simple to implement:
1 2 3 4 5 6 7 8 | def computer_plays(): if apple.x() == bowl.x(): # do nothing when apple is above us return if apple.x() > bowl.x(): moveRight() else: moveLeft() |
def computer_plays():
if apple.x() == bowl.x():
# do nothing when apple is above us
return
if apple.x() > bowl.x():
moveRight()
else:
moveLeft()We then can just plug the function computer_plays() in the game main loop.
However, the above AI has a problem. When the apple is far on the right and AI is on the first column (x = 0), the computer may not have enough time to catch the apple when the apple is about to touch the ground. The optimal way is to wrap the bowl to the other side which has a shorter distance.
We just need to compute the cost (distance) of moving left or moving right and choose a shorter approach.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def computer_plays(): apple_x = apple.x() bowl_x = bowl.x() if bowl_x == apple_x: # do nothing return if bowl_x < apple_x: costOfMovingRight = apple_x - bowl_x costOfMovingLeft = 5 - apple_x + bowl_x else: # bowl_x > apple_x costOfMovingLeft = bowl_x - apple_x costOfMovingRight = 5 - bowl_x + apple_x if costOfMovingLeft < costOfMovingRight: moveLeft() else: moveRight() |
def computer_plays():
apple_x = apple.x()
bowl_x = bowl.x()
if bowl_x == apple_x:
# do nothing
return
if bowl_x < apple_x:
costOfMovingRight = apple_x - bowl_x
costOfMovingLeft = 5 - apple_x + bowl_x
else:
# bowl_x > apple_x
costOfMovingLeft = bowl_x - apple_x
costOfMovingRight = 5 - bowl_x + apple_x
if costOfMovingLeft < costOfMovingRight:
moveLeft()
else:
moveRight()The full source code including this enhanced AI version (decision tree, decision rules) on Microbit Python Programming:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | # Apple Catching Game (AI - Decision Trees/Rules) # Teaching Kids Programming # 2022-2-18 # move bowl one pixel to the left # wrap to right if go beyond the left boundary e.g x=0 then x=4 def moveLeft(): if not game.is_running(): return if bowl.x() == 0: bowl.set_x(4) return bowl.move(-1) input.on_button_pressed(Button.A, moveLeft) # game over: show score, pause and display game over def gameOver(): if not game.is_running(): return basic.show_number(game.score()) basic.pause(2000) game.game_over() # start a new game # triggered only when apple is on the ground # clear score, reset apple position def resetGame(): if apple.y() != 4: return game.set_score(0) apple.set_x(randint(0, 4)) apple.set_y(0) game.resume() # A+B button reset the game when apple is on the ground input.on_button_pressed(Button.AB, resetGame) # move bowl one pixel to the right and # wrap to left if beyond the boundary e.g. x=4 then x=0 def moveRight(): if bowl.x() == 4: bowl.set_x(0) return bowl.move(1) input.on_button_pressed(Button.B, moveRight) # higher score, less delay, faster apple falling speed def getCurrentDelay(score: number): delay = 500 - 10 * score # min delay is 50ms delay = max(50, delay) return delay apple = game.create_sprite(randint(0, 4), 0) bowl = game.create_sprite(2, 4) def computer_plays(): apple_x = apple.x() bowl_x = bowl.x() if bowl_x == apple_x: # do nothing return if bowl_x < apple_x: costOfMovingRight = apple_x - bowl_x costOfMovingLeft = 5 - apple_x + bowl_x else: # bowl_x > apple_x costOfMovingLeft = bowl_x - apple_x costOfMovingRight = 5 - bowl_x + apple_x if costOfMovingLeft < costOfMovingRight: moveLeft() else: moveRight() def on_forever(): if not game.is_running(): return # apple should be falling basic.pause(getCurrentDelay(game.score())) # falling one pixel at a time apple.change_yby(1) # we've got the apple if bowl.is_touching(apple): # score += 1 game.set_score(game.score() + 1) # move apple back to top with a random x apple.go_to(randint(0, 4), 0) return # apple is on the ground if apple.y() == 4: gameOver() return computer_plays() # driver - main game loop basic.forever(on_forever) |
# Apple Catching Game (AI - Decision Trees/Rules)
# Teaching Kids Programming
# 2022-2-18
# move bowl one pixel to the left
# wrap to right if go beyond the left boundary e.g x=0 then x=4
def moveLeft():
if not game.is_running():
return
if bowl.x() == 0:
bowl.set_x(4)
return
bowl.move(-1)
input.on_button_pressed(Button.A, moveLeft)
# game over: show score, pause and display game over
def gameOver():
if not game.is_running():
return
basic.show_number(game.score())
basic.pause(2000)
game.game_over()
# start a new game
# triggered only when apple is on the ground
# clear score, reset apple position
def resetGame():
if apple.y() != 4:
return
game.set_score(0)
apple.set_x(randint(0, 4))
apple.set_y(0)
game.resume()
# A+B button reset the game when apple is on the ground
input.on_button_pressed(Button.AB, resetGame)
# move bowl one pixel to the right and
# wrap to left if beyond the boundary e.g. x=4 then x=0
def moveRight():
if bowl.x() == 4:
bowl.set_x(0)
return
bowl.move(1)
input.on_button_pressed(Button.B, moveRight)
# higher score, less delay, faster apple falling speed
def getCurrentDelay(score: number):
delay = 500 - 10 * score
# min delay is 50ms
delay = max(50, delay)
return delay
apple = game.create_sprite(randint(0, 4), 0)
bowl = game.create_sprite(2, 4)
def computer_plays():
apple_x = apple.x()
bowl_x = bowl.x()
if bowl_x == apple_x:
# do nothing
return
if bowl_x < apple_x:
costOfMovingRight = apple_x - bowl_x
costOfMovingLeft = 5 - apple_x + bowl_x
else:
# bowl_x > apple_x
costOfMovingLeft = bowl_x - apple_x
costOfMovingRight = 5 - bowl_x + apple_x
if costOfMovingLeft < costOfMovingRight:
moveLeft()
else:
moveRight()
def on_forever():
if not game.is_running():
return
# apple should be falling
basic.pause(getCurrentDelay(game.score()))
# falling one pixel at a time
apple.change_yby(1)
# we've got the apple
if bowl.is_touching(apple):
# score += 1
game.set_score(game.score() + 1)
# move apple back to top with a random x
apple.go_to(randint(0, 4), 0)
return
# apple is on the ground
if apple.y() == 4:
gameOver()
return
computer_plays()
# driver - main game loop
basic.forever(on_forever)We have not turned off the controls yet, so we can move against the AI and AI may still miss the apple! See: Microbit Programming: Introduction to AI – Letting Computer Play the Game
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
a WordPress rating system
909 wordsa WordPress rating system
Last Post: Teaching Kids Programming - Design and Develop an Apple Catching Game on Microbit using Python
Next Post: Teaching Kids Programming - Find Three Consecutive Integers That Sum to a Given Number