-- A very quick and dirty tic-tac-toe implementation -- It assumes that the human goes first -- The main purpose is to test the alpha-beta pruning algorithm with Ada.Text_IO, Ada.Integer_Text_IO; use Ada.Text_IO, Ada.Integer_Text_IO; procedure Tic_Tac_Alpha is type Player is ( Human, Comp, Empty ); Comp_Win : constant Integer := 1; Draw : constant Integer := 0; Comp_Loss: constant Integer := -1; type Board_Type is array( 0..9 ) of Player; Move, Bmove, Game_Val: Integer; Game_Board: Board_Type; procedure Place( Board: out Board_Type; Square: Integer; Who: Player ) is begin Board( Square ) := Who; end Place; procedure Unplace( Board: out Board_Type; Square: Integer ) is begin Board( Square ) := Empty; end Unplace; function Is_Empty( Board: Board_Type; Square: Integer ) return Boolean is begin return Board( Square ) = Empty; end Is_Empty; function Full_Board( Board: Board_Type ) return Boolean is begin for I in 1..9 loop if Board( I ) = Empty then return False; end if; end loop; return True; end Full_Board; procedure Immediate_Win( Board: in out Board_Type; Best_Move: out Integer; Side: Player ) is J : Integer; begin for I in 1..9 loop if Board( I ) = Empty then Place( Board, I, Side ); J := 1; while J <= 7 loop if Board( J )=Side and Board( J+1 )=Side and Board( J+2 )=Side then Unplace( Board, I ); Best_Move := I; return; end if; J := J+3; end loop; for K in 1..3 loop if Board( K )=Side and Board( K+3 )=Side and Board( K+6 )=Side then Unplace( Board, I ); Best_Move := I; return; end if; end loop; if Board( 1 )=Side and Board( 5 )=Side and Board( 9 )=Side then Unplace( Board, I ); Best_Move := I; return; end if; if Board( 3 )=Side and Board( 5 )=Side and Board( 7 )=Side then Unplace( Board, I );Best_Move := I; return; end if; Unplace( Board, I ); end if; end loop; Best_Move := 0; return; end Immediate_Win; procedure Print_Board( Board: Board_Type ) is begin Put_Line( "------------" ); for I in 1..9 loop if Board( I ) = Empty then Put( ' ' ); elsif Board( I ) = Comp then Put( 'O' ); else Put( 'X' ); end if; if I mod 3 = 0 then New_Line; end if; end loop; Put_Line( "------------" ); end Print_Board; procedure Print_Board_D( Board: Board_Type; Depth: Integer ) is begin if Depth > 2 then return; end if; for J in 0..Depth loop Put( Ascii.Ht ); end loop; Put_Line( "------------" ); for J in 0..Depth loop Put( Ascii.Ht ); end loop; for I in 1..9 loop if Board( I ) = Empty then Put( ' ' ); elsif Board( I ) = Comp then Put( 'O' ); else Put( 'X' ); end if; if I mod 3 = 0 then New_Line; for I in 0..Depth loop Put( Ascii.Ht ); end loop; end if; end loop; Put_Line( "------------" ); end Print_Board_D; -- Same as before, but perform alpha-beta pruning. -- The main routine should make the call with Alpha = Comp_Loss, -- Beta = Comp_Win procedure Find_Human_Move( Board: in out Board_Type; Alpha, Beta: Integer; Best_Move, Value : in out Integer ); procedure Find_Comp_Move( Board: in out Board_Type; Alpha, Beta: Integer; Best_Move, Value : in out Integer ) is Dc, Response: Integer; begin if Full_Board( Board ) then Value := Draw; return; else Immediate_Win( Board, Best_Move, Comp ); if Best_Move /= 0 then Value := Comp_Win; return; end if; end if; Value := Alpha; for I in 1..9 loop -- Try each square exit when Value >= Beta; if Is_Empty( Board, I ) then Place( Board, I, Comp ); Find_Human_Move( Board, Value, Beta, Dc, Response ); Unplace( Board, I ); -- Restore board if Response > Value then -- Update best move Value := Response; Best_Move := I; end if; end if; end loop; end Find_Comp_Move; procedure Find_Human_Move( Board: in out Board_Type; Alpha, Beta: Integer; Best_Move, Value : in out Integer ) is Dc, Response: Integer; begin if Full_Board( Board ) then Value := Draw; return; else Immediate_Win( Board, Best_Move, Human ); if Best_Move /= 0 then Value := Comp_Loss; return; end if; end if; Value := Beta; for I in 1..9 loop --Try each square if Value <= Alpha then exit; end if; if Is_Empty( Board, I ) then Place( Board, I, Human ); Find_Comp_Move( Board, Alpha, Value, Dc, Response ); Unplace( Board, I ); -- Restore board if Response < Value then -- Update best move Value := Response; Best_Move := I; end if; end if; end loop; end Find_Human_Move; begin -- Simple main that assumes that human goes first. -- There are no error checks for I in 1..9 loop Game_Board( I ) := Empty; end loop; loop Print_Board( Game_Board ); Put( "Enter move: " ); Get( Move ); Game_Board( Move ) := Human; if Full_Board( Game_Board ) then Put_Line( "Draw." ); exit; end if; Print_Board( Game_Board ); Immediate_Win( Game_Board, Bmove, Comp ); if Bmove /= 0 then Put( "Comp move is: " ); Put( Bmove ); New_Line; Game_Board( Bmove ) := Comp; Print_Board( Game_Board ); Put_Line( "Game over -- I win" ); exit; end if; Find_Comp_Move( Game_Board, Comp_Loss, Comp_Win, Bmove, Game_Val ); Put( "Comp move is: " ); Put( Bmove ); New_Line; Game_Board( Bmove ) := Comp; if Full_Board( Game_Board ) then Put_Line( "Draw." ); exit; end if; if Game_Val = Comp_Win then Put_Line( "Forced win." ); end if; end loop; end Tic_Tac_Alpha;