// Michael McElroy
 // michaelmcelroy.net, 2010

    var mm_vertex = function ()
    
        {
        this . number = null;
        this . x = null;
        this . y = null;
        };

    var mm_edge = function ()
    
        {
        this . vertex_a = null;
        this . vertex_b = null;
        }

    var mm_option = function (move)
        
        {
        this . move             = move;
        this . will_check       = NO;
        this . will_checkmate   = NO;
        this . will_stalemate   = NO;
        this . move_risk        = 0;    // 0 -> no risk
        this . stay_risk        = 0;    // 0 -> no risk
        this . capture_value    = 0;    // 0 -> no capture
        this . has_purpose      = NO;   // NO -> not part of a goal path, YES -> part of a goal path
        
        this . get_order = function (that)
        
            {
         // -1 -> this is better than that
         //  0 -> this is equal to that
         // +1 -> this is lesser than that

            var order = 0;
            
            var this_score = this . get_score ();
            var that_score = that . get_score ();

            if (this_score > that_score) order = -1;
            if (this_score < that_score) order = +1;
            
            return (order);
            };
        
        this . get_score = function ()
            
            {
            var score = null;
            
            if (this . will_checkmate)
            
                {
                score = Infinity;
                }
            
            else
            
                {
                score += this . will_check ? +1 : 0;
                score += this . will_stalemate ? -1 : 0;
                score -= this . move_risk;
                score += this . stay_risk;
                score += this . capture_value;
                score += this . has_purpose ? +1 : 0;
                }
            
            return (score);
            };
            
        this . print_diagnostics = function ()
        
            {
            console . log ("will_check: " + this . will_check);
            console . log ("will_checkmate: " + this . will_checkmate);
            console . log ("will_stalemate: " + this . will_stalemate);
            console . log ("move_risk: " + this . move_risk);
            console . log ("stay_risk: " + this . stay_risk);
            console . log ("capture_value: " + this . capture_value);
            console . log ("has_purpose: " + this . has_purpose);
            
            return;
            };
        };

    var mm_ai = function ()

        {
        this . VALUES           = null;
        this . VERTICES         = null;
        this . VERTICES_MAP     = null;
        this . EDGES            = null;
        this . BREATH_DURATION  = 10;
        this . ACT_DELAY        = 250;
        
        this . options = null;      // for the analyze_options method
        this . color = null;        // for the analyze_options method
        this . stay_risk = null;    // for the analyze_options method
        
        this . initialize = function ()
        
            {
            this . VALUES = this . get_values ();
            this . VERTICES = this . get_vertices ();
            this . VERTICES_MAP = this . get_vertices_map (this . VERTICES);
            this . EDGES = this . get_edges ();

            return;
            };

        this . get_values = function ()
        
            {
            var values = new Object ();

            values ["pawn"] = 1;
            values ["knight"] = 3;
            values ["bishop"] = 3;
            values ["rook"] = 5;
            values ["queen"] = 9;
            values ["king"] = 0;

            return (values);
            };

        this . get_vertices = function ()
        
            {
            var vertices = new Array ();

            for (var x = 0; x < 8; x ++)
            for (var y = 0; y < 8; y ++)
            
                {
                var vertex = new mm_vertex ();
                
                vertex . number = y * 8 + x;
                vertex . x = x;
                vertex . y = y;
                
                vertices [vertex . number] = vertex;
                }

            return (vertices);
            };

        this . get_vertices_map = function (vertices)
        
            {
            var map = new Object ();
            
            for (var v = 0; v < vertices . length; v ++)
            
                {
                var vertex = vertices [v];
                
                map ["_" + vertex . x + "_" + vertex . y] = vertex;
                }
        
            return (map);
            };

        this . get_edges = function ()
        
            {
            var edges = new Object ();

            edges ["pawn"] = new Array ();
            edges ["knight"] = new Array ();
            edges ["bishop"] = new Array ();
            edges ["rook"] = new Array ();
            edges ["queen"] = new Array ();
            edges ["king"] = new Array ();

            for (var fx = 0; fx < 8; fx ++)
            for (var fy = 0; fy < 8; fy ++)

                {
                for (var tx = 0; tx < 8; tx ++)
                for (var ty = 0; ty < 8; ty ++)
                
                    {
                    var dx = Math . abs (tx - fx);
                    var dy = Math . abs (ty - fy);
                    
                    if ((dx != 0) || (dy != 0)) // not the same vertex
                    
                        {
                        if ((dx == 0) && (dy == 1)) edges ["pawn"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx == 1) && (dy == 2)) edges ["knight"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx == 2) && (dy == 1)) edges ["knight"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx == 0) && (dy != 0)) edges ["rook"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx != 0) && (dy == 0)) edges ["rook"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dy == 0) && (dy != 0)) edges ["queen"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dy != 0) && (dy == 0)) edges ["queen"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx == 1) && (dy == 1)) edges ["king"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx == 0) && (dy == 1)) edges ["king"] . push (this . get_edge (fx, fy, tx, ty));
                        if ((dx == 1) && (dy == 0)) edges ["king"] . push (this . get_edge (fx, fy, tx, ty));
                        
                        if (dx == dy) edges ["bishop"] . push (this . get_edge (fx, fy, tx, ty));
                        if (dx == dy) edges ["queen"] . push (this . get_edge (fx, fy, tx, ty));
                        
                        if ((fy == 0) || (fy == 7))
                        
                            {
                         // Assuming that the pawn will be promoted to a queen:

                            if ((dy == 0) && (dy != 0)) edges ["pawn"] . push (this . get_edge (fx, fy, tx, ty));
                            if ((dy != 0) && (dy == 0)) edges ["pawn"] . push (this . get_edge (fx, fy, tx, ty));
                            if (dx == dy) edges ["pawn"] . push (this . get_edge (fx, fy, tx, ty));
                            }
                        }
                    }
                }

            return (edges);
            };

        this . get_edge = function (fx, fy, tx, ty)

            {
            var edge = new mm_edge ();
            
            edge . vertex_a = this . VERTICES_MAP ["_" + fx + "_" + fy];
            edge . vertex_b = this . VERTICES_MAP ["_" + tx + "_" + ty];
            edge . value = 1;
            
            return (edge);
            }
        
        this . get_trimmed_edges = function (edges, color, title)
        
            {
            var trimmed_edges = new Array ();
            
            for (var e = 0; e < edges . length; e ++)
            
                {
                var edge = edges [e];
                var piece = game . get_piece (edge . vertex_b . x, edge . vertex_b . y);
                
                if (piece == null)
                
                    {
                    trimmed_edges . push (edge);
                    }
                
                else if ((piece . color != color) && (title != "pawn"))
                
                    {
                    trimmed_edges . push (edge);
                    }
                }
            
            return (trimmed_edges);
            };

        this . choose_move = function (color)
        
            {
            if (game . settled)
            
                {
                game . freeze_pieces ();
                this . aggregate_options (color);
                }
            
            else
            
                {
             // Try again later.
             
                window . setTimeout ("ai . choose_move ('" + color + "');", 300);
                }
            
            return;
            };
            
        this . aggregate_options = function (color)
        
            {
            var options = new Array ();

            for (var p = 0; p < game . pieces . length; p ++)

                {
                var piece = game . pieces [p];

                if (game . was_captured (piece) == NO)
                if (piece . color == color)
                
                    {
                 // Get each option.

                    for (var x = 0; x < 8; x ++)
                    for (var y = 0; y < 8; y ++)

                        {
                        var move = new mm_move (piece . x, piece . y, x, y, null);

                        if (game . is_legal (move))
                        
                            {
                            game . analysis = YES;
                            game . do_move (move);

                            if (! game . is_check (color))
                            
                                {
                                var other_color = (this . color == "white") ? "black" : "white";
                                var option = new mm_option (move);
                                
                                options . push (option);
                                }
                            
                            game . undo_move ();
                            game . analysis = NO;
                            }
                        }
                    }
                }

            this . analyze_options (options, color);
            
            return (options);
            };

        this . analyze_options = function (options, color)
    
            {
            this . options = options;
            this . color = color;
            this . stay_risk = this . get_risk (color);

            window . setTimeout ("ai . analyze_option (0);", this . BREATH_DURATION);
            
            return;
            };
                
        this . analyze_option = function (index)
        
            {
            var other_color = (this . color == "white") ? "black" : "white";

            var option = this . options [index];
            var piece = game . get_piece (option . move . fx, option . move . fy);

            var goals = this . get_goals (piece);
            var edges = this . get_trimmed_edges (this . EDGES [piece . title], piece . color);
            var paths = this . get_shortest_paths (this . VERTICES, edges, this . VERTICES_MAP ["_" + piece . x + "_" + piece . y]);
            
            game . analysis = YES;
            game . do_move (option . move);

            option . stay_risk = this . stay_risk;
            option . move_risk = this . get_risk (this . color);

            if (game . is_stalemate (this . color)) option . will_stalemate = YES;
            if (game . is_stalemate (other_color)) option . will_stalemate = YES;
            if (game . is_checkmate (other_color)) option . will_checkmate = YES;
            if (game . is_check (other_color)) option . will_check = YES;

            option . capture_value = (game . moves [game . moves . length - 1] . captured_piece == null) ? 0 : this . VALUES [game . moves [game . moves . length - 1] . captured_piece . title];
                        
            for (var g = 0; g < goals . length; g ++)

                {
                var goal = goals [g];

                if (paths [goal . number] != null)

                    {
                    var vertex = paths [goal . number] [0];

                    if (vertex . x == option . move . tx)
                    if (vertex . y == option . move . ty)
                    
                        {
                        option . has_purpose = YES;
                        
                        break;
                        }
                    }
                }

            game . undo_move ();
            game . analysis = NO;
            
            index ++;
            
            if (index < this . options . length)
            
                {
                window . setTimeout ("ai . analyze_option (" + index + ");", this . BREATH_DURATION);
                }
            
            else
            
                {
                this . act ();
                }
            
            return;
            };
        
        this . act = function ()
        
            {
         // stabilize the pieces

            for (var p = 0; p < game . pieces . length; p ++)
            
                {
                var piece = game . pieces [p];

                piece . move (piece . x, piece . y, ! ANIMATE);
                }


         // sort the options

            var sorted = false;
            var limit = this . options . length - 1;
            
            while (! sorted)
            
                {
                sorted = true; // assumption
                
                for (var o = 0; o < limit; o ++)
                
                    {
                    var option_a = this . options [o + 0];
                    var option_b = this . options [o + 1];
                    var order = option_a . get_order (option_b);
                    
                    if ((order > 0) || ((order == 0) && (Math . random () < 0.5)))
                    
                        {
                        this . options [o + 0] = option_b;
                        this . options [o + 1] = option_a;
                        
                        sorted = false;
                        }
                    }
                
                limit --;
                }


         // move

            var number = game . get_move_count ();
            var move = this . options [0] . move;

            game . unfreeze_pieces ();
            game . do_move (move);
            
            if ((move . piece . title == "pawn") && ((move . piece . y == 0) || (move . piece . y == 7)))

                {
                game . promotion_move = move;
                game . set_promotion ("queen");

             // game::set_promotion calls ajax::set_move
                }
            
            else
            
                {
                ajax . set_move (number, move);
                }

            return;
            };
        
        this . get_risk = function (color)
        
            {
            var risk = 0;
            
            for (var sp = 0; sp < game . pieces . length; sp ++)
            
                {
                var piece_a = game . pieces [sp];

                if (game . was_captured (piece_a) == NO)
                if (piece_a . color == color)

                    {
                    for (var op = 0; op < game . pieces . length; op ++)
                    
                        {
                        var piece_b = game . pieces [op];
                        
                        if (game . was_captured (piece_b) == NO)
                        if (piece_b . color != color)
                        
                            {
                            if (game . is_legal (new mm_move (piece_a . x, piece_a . y, piece_b . x, piece_b . y, null)))
                            
                                {
                                risk = risk - this . VALUES [piece_b . title];
                                }

                            if (game . is_legal (new mm_move (piece_b . x, piece_b . y, piece_a . x, piece_a . y, null)))
                            
                                {
                                risk = risk + this . VALUES [piece_a . title];
                                }
                            }
                        }
                    }
                }

            return (risk);
            };
        
        this . get_shortest_paths = function (vertices, edges, first_vertex)
        
            {
         // Dijkstra's Algorithm

            var all_vertices = get_copy (vertices);
            var shortest_paths = new Array ();
            var path_weights = new Array ();
            var preceding_vertices = new Array ();

            vertices = get_copy (vertices);
            first_vertex . reachable = true;
            
            for (var v = 0; v < vertices . length; v ++)
            
                {
                var vertex = vertices [v];
                
                path_weights [vertex . number] = Infinity;
                preceding_vertices [vertex . number] = null;
                }

            path_weights [first_vertex . number] = 0;

            while (vertices . length > 0)

                {
             // select the next vertex that is at the end of the current shortest path and still exists in the vertices array

                var selected_vertex = null;

                for (var v = 0; v < vertices . length; v ++)
                
                    {
                    var vertex = vertices [v];

                    var weight_a = path_weights [vertex . number];
                    var weight_b = (selected_vertex == null) ? Infinity : path_weights [selected_vertex . number];

                    if (weight_a < weight_b) selected_vertex = vertex;
                    }

                if (selected_vertex == null)
                    
                    {
                    vertices = new Array ();
                    }
                
                else
                
                    {
                    for (var v = 0; v < vertices . length; v ++)
                    
                        {
                        var vertex = vertices [v];
                        
                        if (vertex == selected_vertex)
                        
                            {
                            vertices . splice (v, 1);

                            break;
                            }
                        }


                 // analyze each of the vertices that can be directly reached form the current vertex

                    for (var e = 0; e < edges . length; e ++)
                    
                        {
                        var edge = edges [e];
                        
                        if (edge . vertex_a == vertex)
                        
                            {
                            var next_vertex = edge . vertex_b;

                            next_vertex . reachable = true;

                            var vertex_weight = path_weights [vertex . number];
                            var next_vertex_weight = path_weights [next_vertex . number];
                            var edge_weight = 1;

                            var a = (edge_weight + vertex_weight) < next_vertex_weight;
                            var b = ((edge_weight + vertex_weight) == next_vertex_weight) && (Math . random () < 0.5);

                            if (a || b)
                            
                                {
                                path_weights [next_vertex . number] = vertex_weight + edge_weight;
                                preceding_vertices [next_vertex . number] = selected_vertex;
                                }
                            }
                        }
                    }
                }


         // convert the preceding vertices collection into an array of paths

            for (var v = 0; v < all_vertices . length; v ++)
            
                {
                var vertex = all_vertices [v];

                if (preceding_vertices [vertex . number] == null)
                
                    {
                    shortest_paths [vertex . number] = null;
                    }
                
                else
                
                    {
                    shortest_paths [vertex . number] = this . get_shortest_path (preceding_vertices, first_vertex, vertex);
                    }
                }
            
            return (shortest_paths);
            };

        this . get_shortest_path = function (preceding_vertices, source_vertex, destination_vertex)
        
            {
            var shortest_path = new Array ();
            var vertex = destination_vertex;
            
            while (preceding_vertices [vertex . number] != null)
            
                {
                shortest_path . unshift (vertex);
                
                vertex = preceding_vertices [vertex . number];
                }
            
//          shortest_path . unshift (source_vertex);
            
            return (shortest_path);
            };

        this . get_shortest_distances = function (vertices, edges)
        
            {
         // Floyd-Warshall    
        
            var shortest_distances = new Array ();

            for (var v = 0; v < Math . pow (vertices . length, 2); v ++)
            
                {
                shortest_distances [v] = Infinity;
                }

            for (var e = 0; e < edges . length; e ++)
            
                {
                var edge = edges [e];
                var i = vertices . length * edge . vertex_a . number + edge . vertex_b . number;

                shortest_distances [i] = edge . value;
                }

            for (var va = 0; va < vertices . length; va ++)
            for (var vb = 0; vb < vertices . length; vb ++)
            for (var vc = 0; vc < vertices . length; vc ++)

                {
                var bci = vertices . length * vb + vc;
                var bai = vertices . length * vb + va;
                var aci = vertices . length * va + vc;

                shortest_distances [bci] = Math . min (shortest_distances [bci], shortest_distances [bai] + shortest_distances [aci]);
                }

            for (var v = 0; v < vertices . length; v ++)
            
                {
                var vertex = vertices [v];

                shortest_distances [vertices . length * vertex . number + vertex . number] = 0;
                }

            return (shortest_distances);
            };
            
        this . get_goals = function (piece)
        
            {
            var goals = new Array ();
            var other_color = (piece . color == "white") ? "black" : "white";
            var other_king = null;
            
            for (var p = 0; p < game . pieces . length; p ++)
            
                {
                if (game . pieces [p] . title == "king")
                if (game . pieces [p] . color == other_color)
                
                    {
                    other_king = game . pieces [p];
                    
                    break;
                    }
                }

            switch (piece . title)
            
                {
                case "pawn":
                
                    {
                    var y = (piece . color == game . self . color) ? 0 : 7;

                    for (var x = 0; x < 8; x ++) this . append_goal (goals, x, y);
                    
                    this . append_goal (goals, 3, 3);
                    this . append_goal (goals, 3, 4);
                    this . append_goal (goals, 4, 3);
                    this . append_goal (goals, 4, 4);

                    break;
                    }
                
                case "knight":
                    
                    {
                    this . append_goal (goals, other_king . x + 1, other_king . y + 2);
                    this . append_goal (goals, other_king . x + 1, other_king . y - 2);
                    this . append_goal (goals, other_king . x - 1, other_king . y + 2);
                    this . append_goal (goals, other_king . x - 1, other_king . y - 2);
                    this . append_goal (goals, other_king . x + 2, other_king . y + 1);
                    this . append_goal (goals, other_king . x + 2, other_king . y - 1);
                    this . append_goal (goals, other_king . x - 2, other_king . y + 1);
                    this . append_goal (goals, other_king . x - 2, other_king . y - 1);

                    this . append_goal (goals, 3, 3);
                    this . append_goal (goals, 3, 4);
                    this . append_goal (goals, 4, 3);
                    this . append_goal (goals, 4, 4);

                    break;
                    }
                    
                case "bishop":
                
                    {
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x - z, other_king . y - z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x - z, other_king . y + z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + z, other_king . y - z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + z, other_king . y + z);

                    this . append_goal (goals, 3, 3);
                    this . append_goal (goals, 3, 4);
                    this . append_goal (goals, 4, 3);
                    this . append_goal (goals, 4, 4);

                    break;
                    }
                
                case "rook":
                
                    {
                    for (var x = 2; x <= 7; x ++) this . append_goal (goals, other_king . x - x, other_king . y + 0);
                    for (var x = 2; x <= 7; x ++) this . append_goal (goals, other_king . x + x, other_king . y + 0);
                    for (var y = 2; y <= 7; y ++) this . append_goal (goals, other_king . x + 0, other_king . y - y);
                    for (var y = 2; y <= 7; y ++) this . append_goal (goals, other_king . x + 0, other_king . y + y);

                    this . append_goal (goals, 3, 3);
                    this . append_goal (goals, 3, 4);
                    this . append_goal (goals, 4, 3);
                    this . append_goal (goals, 4, 4);
                    
                    break;
                    }

                case "queen":
                
                    {
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x - z, other_king . y - z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x - z, other_king . y + z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + z, other_king . y - z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + z, other_king . y + z);

                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x - z, other_king . y + 0);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + z, other_king . y + 0);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + 0, other_king . y - z);
                    for (var z = 2; z <= 7; z ++) this . append_goal (goals, other_king . x + 0, other_king . y + z);

                    this . append_goal (goals, 3, 3);
                    this . append_goal (goals, 3, 4);
                    this . append_goal (goals, 4, 3);
                    this . append_goal (goals, 4, 4);

                    break;
                    }
                }

            return (goals);
            };

        this . append_goal = function (goals, x, y)
        
            {
            if ((0 <= x) && (x <= 7))
            if ((0 <= y) && (y <= 7))
            
                {
                goals . push (this . VERTICES_MAP ["_" + x + "_" + y]);
                }

            return;
            };
        };