Description

This week and one week from now we will execute a 2-player tabletop game in Prolog. ... Board (state) Representation. There are MANY approaches to speak to the ...

Transcripts

AI – Week 10 AI and Games (2) Lee McCluskey, room 2/09 Email lee@hud.ac.uk http://scom.hud.ac.uk/scomtlm/cha2555/

Last Week Introduction to AI Games 2-player recreations Minimax and alpha beta pruning

AI in Games: handy illustration This week and one week from now we will execute a 2-player tabletop game in Prolog. Board (state) representation Board (state) assessment Move application Move era Mini-max/alpha beta calculation Same Code in Prolog

Fox and Goose fox Goal: Goose in section 4 HOME Rules: If fox beside goose and foxes turn, then fox can eat goose Fox/goose can move corner to corner and additionally vert/horiz. One and only fox can move every turn. goose fox

Fox and Goose fox Goal: Goose in section 4 HOME Rules: If fox by goose and foxes turn, then fox can eat goose Fox/goose can move slanting and also vert/horiz goose fox GOOSE to move – which MOVE??????

Fox and Goose fox Goal: Goose in section 4 HOME Rules: If fox by goose and foxes turn, then fox can eat goose Fox/goose can move slanting and in addition vert/horiz goose FOX to move – which MOVE??????

Fox and Goose – more intricate amusement.. Objective: Goose in last segment Rules: If fox by goose and foxes turn, then fox can eat goose Fox/goose can move askew and also vert/horiz New guidelines: - Fox can\'t move to last section - Obstacles to diminish development fox HOME fox goose

Board (state) Representation There are MANY approaches to speak to the condition of a diversion eg b(1,[ 0 , 0, f, 0 ], [ 0 , 0, 0, 0 ], [ 0 , 0, 0, 0 ], [ g , 0, 0, 0 ], [ 0 , 0, 0, 0 ], [ 0 , 0, f, 0 ]).

Better Representation b(1, [ x(1,1,0), x(1,2,0), x(1,3,f), x(1,4,0), x(2,1,0), x(2,2,0), x(2,3,0), x(2,4,0), x(3,1,0), x(3,2,0), x(3,3,0), x(3,4,0), x(4,1,g), x(4,2,0), x(4,3,0), x(4,4,0), x(5,1,0), x(5,2,0), x(5,3,0), x(5,4,0), x(6,1,0), x(6,2,0), x(6,3,f), x(6,4,0)]). Request OF ELEMENT IN LIST IS IRRELEVANT

Representation and Simple Evaluation b(1, [ x(1,1,0), x(1,2,0), x(1,3,f), x(1,4,0), x(2,1,0), x(2,2,0), x(2,3,0), x(2,4,0), x(3,1,0), x(3,2,0), x(3,3,0), x(3,4,0), x(4,1,g), x(4,2,0), x(4,3,0), x(4,4,0), x(5,1,0), x(5,2,0), x(5,3,0), x(5,4,0), x(6,1,0), x(6,2,0), x(6,3,f), x(6,4,0)]). /* SIMPLE EVALUATION – Positive for Goose, Negative for Fox */board_eval(L, 10000) :- member(x(_,4,g), L),!. board_eval(L, - 10000) :- \+ member(x(_,_,g), L),!. board_eval(L, 0 ) :- !.

Move Application AND Generation apply( FROM, TO, BOARD_IN, BOARD_OUT) Move Generation: Precondition: FROM and BOARD_IN are instantiated. Postcondition: TO and BOARD_OUT get values. Move Application: Precondition: FROM, TO, and BOARD_IN are instantiated. Postcondition: BOARD_OUT gets a quality.

Move Application AND Generation Fixes parameters % Assume Z is either f or g apply( x(X,Y,Z), x(X1,Y1,Z1), B_IN, B_OUT) :- % move to exhaust square OR fox eats goose .. (Z1 = 0 ; (Z=f, Z1=g)), member(x(X,Y,Z), B_IN), member(x(X1,Y1,Z1),B_IN), % FOX can\'t go into the fourth section... \+ (Z=f, Y1=4), % two squares must be by each other next(X,Y,X1,Y1), % checks over – now make the move remove(x(X,Y,Z), B_IN, B1), remove(x(X1,Y1,Z1), B1, B2), B_OUT = [x(X1,Y1,Z),x(X,Y,0)|B2]. Produces Generate and Test Tests parameters Deterministic methods – stand out conceivable yield

Search profundity Identifier of the beginning board Examples Who goes first Initial call to minimax Finds best move | ?- t(7,5,goose). Move goose from 4,1 to 5,1 Estimated estimation of Board is - 5 misty who wins Number of leaf sheets assessed is 43979 Move fox from 3,3 to 4,2 Move goose from 5,1 to 6,1 Move fox from 4,2 to 5,1 Move goose from 6,1 to 7,2 Move fox from 5,1 to 6,1 Move goose from 7,2 to 7,3 yes - insufficient pursuit space to see who wins so fox pursues goose Subsequent calls to Minimax from "finish_game" strategy

Examples | ?- t(8,5,goose). Move goose from 4,1 to 5,1 Estimated estimation of Board is 10000 goose wins Number of leaf loads up assessed is 222714 Move fox from 3,3 to 2,2 Move goose from 5,1 to 4,2 Move fox from 2,2 to 3,3 Move goose from 4,2 to 5,3 Move fox from 3,3 to 4,2 Move goose from 5,3 to 4,4 Move fox from 4,2 to 5,3 yes | ?- This time enough inquiry space to see that the goose wins Note the fox meanders about as it realizes that impossible to win is conceivable!