C#•2y ago

✅ What is the best way to fix StackOverflow when methods are calling each other?

Here is all the relevant code to the question When Checkmate is called, it calls Stalemate, which calls AllPossibilitesOfPlayer, which calls RemovesCheck, which calls Check, which calls AllPossibilitesOfPlayer, which calls RemovesCheck, which calls Check and so on. What is the best way to fix this problem? I can duplicate some functions and I think it will fix it, but is there any other better solution?

        public List<int> AllPossiblitiesOfPlayer(int player, Board b) 
        {
            List<int> allMoves = new List<int>(), playerPositions = player == 0 ? whitePositions : blackPositions; ;
            for (int i = 0; i < playerPositions.Count; i++)
            {
                List<int> possibles = new Find(playerPositions[i], board[playerPositions[i]].piece, player, this).FindMoves();
                for (int j = 0; j < possibles.Count; j++)
                {
                    if (!RemovesCheck(i, possibles[j], player, b))
                    {
                        possibles.RemoveAt(j);
                    }
                }
                allMoves.Concat(possibles).ToList();
            }
            return allMoves;
        }
        public int Stalemate(Board b, int player) 
        {
            if (AllPossiblitiesOfPlayer(player, b).Count() == 0)
                return player;
            else return -1;
        }
        public int Checkmate(Board b, int player) 
        {
            if (Stalemate(b, player) == player && Check(player, b))
                return player == 0 ? 1 : player;
            return -1;
        }
        public bool Check(int player, Board b) 
        {
            return AllPossiblitiesOfPlayer(player == 0 ? 1 : player, b).Contains(FindKingPos(player, b));
        }
        public bool RemovesCheck(int source, int dest, int player, Board b) 
        {
            var copy = b.Clone(b);
            Move(source, dest, player, copy);
            return !Check(player, copy);
        }

        public List<int> AllPossiblitiesOfPlayer(int player, Board b) 
        {
            List<int> allMoves = new List<int>(), playerPositions = player == 0 ? whitePositions : blackPositions; ;
            for (int i = 0; i < playerPositions.Count; i++)
            {
                List<int> possibles = new Find(playerPositions[i], board[playerPositions[i]].piece, player, this).FindMoves();
                for (int j = 0; j < possibles.Count; j++)
                {
                    if (!RemovesCheck(i, possibles[j], player, b))
                    {
                        possibles.RemoveAt(j);
                    }
                }
                allMoves.Concat(possibles).ToList();
            }
            return allMoves;
        }
        public int Stalemate(Board b, int player) 
        {
            if (AllPossiblitiesOfPlayer(player, b).Count() == 0)
                return player;
            else return -1;
        }
        public int Checkmate(Board b, int player) 
        {
            if (Stalemate(b, player) == player && Check(player, b))
                return player == 0 ? 1 : player;
            return -1;
        }
        public bool Check(int player, Board b) 
        {
            return AllPossiblitiesOfPlayer(player == 0 ? 1 : player, b).Contains(FindKingPos(player, b));
        }
        public bool RemovesCheck(int source, int dest, int player, Board b) 
        {
            var copy = b.Clone(b);
            Move(source, dest, player, copy);
            return !Check(player, copy);
        }

15 Replies

Murphy•2y ago

It's kind of hard to help optimize just seeing this bit but why do you have to call AllPossibilitiesOfPlayer in Check? That sems like there will be a lot of computation when you only need to confirm that the other player's king is threatened? Seems like you're going to be doing a lot more work than needed. It seems like your approach is to brute force all possibilities and then see if one of those is invalid rather than just checking for invalid-ness in the first place.

Tvde1•2y ago

You could introduce an int parameter that represents how "deep" we are looking. Maybe after a depth of 20 moves you'll want to stop looking

deemOP•2y ago

I have a list of both player's positions of all their pieces, and I found the best way to check if a player is in check is to check if all the possible moves of the opponent (using list mentioned) land on player's king position. So the best way to fix this would be to rewrite the code? Additionally RemovesCheck checks if the move from position source to dest is legal or not

TravestyOfCode•2y ago

It would probably be faster to check each piece by piece instead of getting all valid moves first. Once you find one move that results in a Check (or Checkmate) you don't have to search the other possible moves. Quit searching early if you can Unless you need to know all possible moves that would result in a Check situation, but it looks like your just doing true/false. Other optimizations could include ignoring a piece's if it's range is outside of king pos. For example, if a pawn is at A2, and King is at G5, there's no need to check that piece for Check as it's impossible.

Murphy•2y ago

Ah, ok. You effectively have an infinite loop since youre trying to find every possible move first before you determine if there are invalid moves. There needs to be a ground case where the cycle of calls stops, but if you enumerate every possible move first, you'll never hit it. Think of one piece just moving back and forth, there are an infinte number of possible moves. You need to stop checking for possible moves once you find an invalid move.

ZacharyPatten•2y ago

can you provide the full source code for your app? We could help more easily if we can replicate the error

deemOP•2y ago

I don't quite understand how are there infinite possible moves. FindMoves returns all of the positions that a piece can move to

deemOP•2y ago

https://gist.github.com/deemure/322782c9cc136ed2f25491ea995aeb8d It's nowhere closed to being finished, which why I feel like it will be hard to read

Gist

Random Chess Move Console App

Random Chess Move Console App. GitHub Gist: instantly share code, notes, and snippets.

deemOP•2y ago

I will try and work something out. Thanks for the help, I will definitely implement some optimizations you've mentioned as well

ZacharyPatten•2y ago

thanks for sharing 🙂 will try to give it a look (and help you with your issue) when I have time

Murphy•2y ago

It's more of an error in the logic of the algorithm and how youre checking for invalid moves rather than the code itself. You're not 'pruning your game tree' correctly. If you try to run through all possible moves, and only RemoveAt() the moves that fail the RemovesCheck() check, you'll run into an infinite loop. It's just harder to see since the 'loop' is split up with function calls. Consider a board with two kings and a white rook; call it state1. Lets say you try to run through all possible moves of the rook- the first move you validate with RemovesCheck() will attempt to make a new board, call it state2, and Move() the rook and then look for checks with Check() on that new board state. Well, now the Check() method will have to find all possibilities and one of those is going to be the same state you started with - state1. You'll just go back and forth infinitely without a way to remove that already checked move from the move list. When you clone the board in RemovesCheck(), you need to remember where the piece was originally before the move and exclude the move that would bring it back to the same place it was the next time you call AllPossiblitiesOfPlayer() inside the Check() method. That's where I'd start

deemOP•2y ago

I understand now thank you 🙏

Murphy•2y ago

Now that I think about it, you're still going to run into issues since you're still going to be checking so deep into possible moves when you don't have to. When you're eliminating from your set of possible moves that will place a player into check, when you check the opponent's pieces' possible moves to see if they hit the player's king, skip the RemovesCheck() for those moves. It's irrelevant because you don't care if the opponents can actually perform the capture, only that they are threatening the king. It will cause a bunch of branching by essentially walking over every single possible move that could happen for the rest of the game after that one move. You'll very likely still run into stack overflows since the number of possible moves in a game is just so dang big.

ZacharyPatten•2y ago

@deemure are you still needing help with this topic?

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

✅ What is the best way to fix StackOverflow when methods are calling each other?