<?/**
  <->  Randi Hagen (vym@kriona.net)
  <->  http://www.kriona.net/
  <->  Tic Tac Toe AI v1.0


There are two types of behavior for the computer opponent - one is blocking an
opponent from wininng, the other is making a winning move - that is, if the
computer has 2 spots in a row, picking that third spot and winning. If the
opponent choses not to block or win (or doesn't need to), it will pick a random spot.

The evil opponent should be unbeatable, so if you somehow manage to win against it,
let me know!


  **/



class TicTacToeAI {

    var $board;

    var $win_combo;

    // the win/block percentages
    var $ai = array(
        array(0, 33),    // easy
        array(33, 66),    // medium
        array(66, 100)    // hard
    );



    function TicTacToeAI($board, $win) {

        $this->board = $board;
        $this->win_combo = $win;

    } // end constructor







    function move($level, $player) {


        switch($level) {

            case 4:

                $this->move_evil($player);
                break;

            case 3:
            case 2:
            case 1:

                $this->move_ai($level, $player);
                break;

            case 0:
            default:

                // human opponent
                break;

        }

        return $this->board;


    } // end function






    function move_random($player) {

        $moves = array();

        // get all empty spaces
        for($i=0;$i<3;$i++) for($n=0;$n<3;$n++) if($this->board[$i][$n]==0) $moves[] = $i . $n;

        srand((float)microtime() * 1000000);
        shuffle($moves);

        $this->board[$moves[0]{0}][$moves[0]{1}] = ($player ? 1 : 2);

        return $this->board;

    } // end function






    // behavior for easy/medium/hard opponents

    function move_ai($level, $player) {

        // check winning case
        if(rand(0, 100)<=$this->ai[($level - 1)][0]) if($this->calc_move($player, true)) return;


        // if we've decided to block
        if(rand(0, 100)<=$this->ai[($level - 1)][1]) if($this->calc_move($player, false)) return;


        $this->board = $this->move_random($player);

    } // end function





    // behavior for evil opponent
    // always block, always win, pre-programmed moves

    function move_evil($player) {

        // awlays check winning case
        if($this->calc_move($player, true)) return;

        // always block
        if($this->calc_move($player, false)) return;

        // programmed moves
        if($this->programmed_moves($player)) return;

        $this->board = $this->move_random($player);


    } // end function










    // calculate smart moves
    // the argument determines what spots we're looking at
    // false = blocking, check for opponent spots
    // true = win move, check for own spots

    function calc_move($player, $move) {

        // go through the win cases
        for($i=0;$i<48;) {

            // if we need to block
            if($this->two_of_three(
                $this->board[$this->win_combo{$i}][$this->win_combo{($i+1)}],
                $this->board[$this->win_combo{($i+2)}][$this->win_combo{($i+3)}],
                $this->board[$this->win_combo{($i+4)}][$this->win_combo{($i+5)}],
                ($move ? ($player ? 1 : 2) : ($player ? 2 : 1))
            )) {

                for($n=0;$n<6;$n++) {

                    if($this->board[$this->win_combo{($i+$n)}][$this->win_combo{($i+$n+1)}]==0) {

                        $this->board[$this->win_combo{($i+$n)}][$this->win_combo{($i+$n+1)}] = ($player ? 1 : 2);
                        break;

                    }

                    $i++;
                }

                return true;

            }

            $i += 6;

        }

        return false;

    } // end




    // there are three cases:
    // 0 spots chosen, return false
    // 1 spot chosen, return false
    // 2 spots chosen, return true

    function two_of_three($a, $b, $c, $num) {

        return ($a==0 && $b==$num && $c==$num) || ($a==$num && $b==0 && $c==$num) || ($a==$num && $b==$num && $c==0);

    } // end function






    // these custom moves should make the evil AI unbeatable

    function programmed_moves($player) {


        $opponent = ($player ? 2 : 1);
        $player = ($player ? 1 : 2);

        $moves = $this->count_moves();

        // corners are 0|0, 2|2, 0|2, 2|0
        $corner = "00220220";
        // sides are 0|1, 1|0, 1|2, 2|1
        $side = "01101221";



        // -------------
        // |   |   |   |
        // -------------
        // |   | ! |   |
        // -------------
        // |   |   |   |
        // -------------
        // always take center

        if(
            $moves==0 ||
            ($moves==1 && $this->board[1][1]==0)
        ) {

            $this->board[1][1] = $player;
            return true;

        }


        // -------------
        // |   |   | ! |
        // -------------
        // |   | x |   |
        // -------------
        // |   |   |   |
        // -------------
        // take a corner, since taking a side means you lose

        if($moves==1 && $this->board[1][1]==$opponent) {

            // pick a random corner
            $rand = 2*rand(0, 3);

            $this->board[$corner{$rand}][$corner{($rand + 1)}] = $player;

            return true;

        }



        // -------------
        // | ! | O | ! |
        // -------------
        // | O | x |   |
        // -------------
        // | ! |   |   |
        // -------------
        // take a corner next to their side, since taking a far corner means you lose

        if($moves==3 && $this->board[1][1]==$player) {

            $sides = 0;
            $sd = "";
            
            // check which side
            for($i=0;$i<4;$i++) {

                $k = $i*2;
                if($this->board[$side{$k}][$side{($k+1)}]==$opponent) {

                    $sides++;
                    $sd .= $side{$k} . $side{($k+1)};

                }

            }


            if($sides==2) {


                // take a pick a random side
                $rand = 2*rand(0, 1);

                // move to corner
                $crn = $this->side_same_corners($sd{$rand} . $sd{($rand+1)});

                $rand = 2*rand(0, 1);

                $this->board[$crn{$rand}][$crn{($rand + 1)}] = $player;
                return true;


            }

        }




        // -------------
        // |   |   | ! |
        // -------------
        // |   | x | O |
        // -------------
        // |   |   |   |
        // -------------
        // taking a corner next to their side means you always win

        if($moves==2 && $this->board[1][1]==$player) {

            // check which side
            for($i=0;$i<4;$i++) {

                $k = $i*2;
                if($this->board[$side{$k}][$side{($k+1)}]==$opponent) {

                    // move to corner
                    $crn = $this->side_same_corners($side{$k} . $side{($k+1)});

                    $rand = 2*rand(0, 1);

                    $this->board[$crn{$rand}][$crn{($rand + 1)}] = $player;
                    return true;

                }

            }


        }



        // -------------
        // | ! |   | X |
        // -------------
        // |   | x | O |
        // -------------
        // | O |   |   |
        // -------------
        // taking the corner NOT next to their side means you always win

        if($moves==4 && $this->board[1][1]==$player) {

            // check which side
            for($i=0;$i<4;$i++) {

                $k = $i*2;
                if($this->board[$side{$k}][$side{($k+1)}]==$opponent) {

                    // move to corner
                    $crn = $this->side_same_corners($side{$k} . $side{($k+1)});

                    // check which corner
                    for($n=0;$n<2;$n++) {

                        $x = $n*2;
                        if($this->board[$crn{$x}][$crn{($x+1)}]==$player) {

                            // check the kitty-corner
                            $kitty = $this->kitty($crn{$x} . $crn{($x+1)});

                            
                            if($this->board[$kitty{0}][$kitty{1}]==$opponent) {


                                // pick a corner opposite their side
                                // one of these corners will have already been taken
                                $move_crn = $this->side_opposite_corners($side{$k} . $side{($k+1)});


                                $move = ($this->board[$move_crn{0}][$move_crn{1}]==$opponent ? "23" : "01");

                                $this->board[$move_crn{($move{0})}][$move_crn{($move{1})}] = $player;
                                return true;


                            } // end if

                        } // end if

                    } // end for

                } // end if

            } // end for

        } // end if




        // -------------
        // |   |   | ! |
        // -------------
        // |   | x |   |
        // -------------
        // | O |   |   |
        // -------------
        // taking the kitty corner is the best way to win

        if($moves==2 && $this->board[1][1]==$player) {

            // check which corner
            for($i=0;$i<4;$i++) {

                $k = $i*2;
                if($this->board[$corner{$k}][$corner{($k+1)}]==$opponent) {

                    // move to kitty
                    $crn = $this->kitty($corner{$k} . $corner{($k+1)});

                    $this->board[$crn{0}][$crn{1}] = $player;
                    return true;

                }

            }


        }






        // -------------
        // | ! |   | X |
        // -------------
        // |   | x |   |
        // -------------
        // | O |   |   |
        // -------------
        // take another corner to stalemate

        if($moves==3 && $this->board[1][1]==$opponent) {

            // check each corner
            for($i=0;$i<4;$i++) {

                $k = $i*2;
                if($this->board[$corner{$k}][$corner{($k+1)}]==$opponent) {

                    // move to kitty
                    $crn = $this->kitty($corner{$k} . $corner{($k+1)});

                    if($this->board[$crn{0}][$crn{1}]==$player) {


                        $not_crn = $this->not_kitty($crn);

                        $rand = 2*rand(0, 1);

                        $this->board[$not_crn{$rand}][$not_crn{($rand + 1)}] = $player;
                        

                        return true;

                    }

                }

            }


        }



        // -------------
        // |   |   | O |
        // -------------
        // |   | X |   |
        // -------------
        // |   | O | ! |
        // -------------
        // take the corner to avoid lose condition


        if($moves==3 && $this->board[1][1]==$player) {

            // check which side
            for($i=0;$i<4;$i++) {

                $k = $i*2;
                if($this->board[$side{$k}][$side{($k+1)}]==$opponent) {

                    // opposite corner
                    $crn = $this->side_opposite_corners($side{$k} . $side{($k+1)});

                    // check which corner
                    for($n=0;$n<2;$n++) {

                        $x = $n*2;
                        if($this->board[$crn{$x}][$crn{($x+1)}]==$opponent) {

                            // not-kitty corners of taken corner
                            $not_kitty = $this->not_kitty($crn{$x} . $crn{($x+1)});

                            // corners next to side
                            $near_crn = $this->side_same_corners($side{$k} . $side{($k+1)});



                            // one of these corners must equal the other
                            for($a=0;$a<2;$a++) {

                                $b = $a*2;

                                for($c=0;$c<2;$c++) {

                                    $d = $c*2;

                                    if(($not_kitty{$b} . $not_kitty{($b+1)})==($near_crn{$d} . $near_crn{($d+1)})) {

                                        $this->board[$not_kitty{$b}][$not_kitty{($b+1)}] = $player;
                                        return true;

                                    }

                                }

                            }

                        }

                    }


                }

            }

        }



        // -------------
        // | ! |   | O |
        // -------------
        // |   | X |   |
        // -------------
        // | O |   | ! |
        // -------------
        // avoid kitty corners or you lose


        if($moves==3 && $this->board[1][1]==$player) {

            $move = 2*rand(0,4);

            $this->board[$side{$move}][$side{($move+1)}] = $player;
            return true;

        }





        // nope, no special moves interested us

        return false;

    } // end if








    function count_moves() {

        $return = 0;

        for($i=0;$i<3;$i++) for($n=0;$n<3;$n++) if($this->board[$i][$n]) $return++;

        return $return;

    } // end function




    // side: 01    corner: 00 02
    // side: 10    corner: 00 20
    // side: 12    corner: 02 22
    // side: 21    corner: 20 22

    function side_same_corners($side) {

        return str_replace("1", "0", $side) . str_replace("1", "2", $side);

    } // end function




    // side: 01    corner: 20 22
    // side: 10    corner: 02 22
    // side: 12    corner: 00 20
    // side: 21    corner: 00 02

    function side_opposite_corners($side) {

        switch($side) {

            case "01":
                return "2022";
            case "10":
                return "0222";
            case "12":
                return "0020";
            case "21":
                return "0002";
            default:
                break;

        } // end switch


    } // end function




    // corner: 00    kitty: 22
    // corner: 02    kitty: 20
    // corner: 20    kitty: 02
    // corner: 22    kitty: 00

    function kitty($corner) {

        if($corner{0}!=$corner{1}) {

            return strrev($corner);

        } else {

            return ($corner=="00" ? "22" : "00");

        }

    } // end function




    // corner: 02    not kitty: 0022
    // corner: 20    not kitty: 0022
    // corner: 00    not kitty: 0220
    // corner: 22    not kitty: 0220

    function not_kitty($corner) {

        if($corner{0}!=$corner{1}) {

            return "0022";

        } else {

            return "0220";

        }

    } // end function



} // end class


?>