C
C#13mo ago
deem

✅ 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
Murphy13mo 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
Tvde113mo 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
deem
deem13mo 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
TravestyOfCode13mo 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
Murphy13mo 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
ZacharyPatten13mo ago
can you provide the full source code for your app? We could help more easily if we can replicate the error
deem
deem13mo ago
I don't quite understand how are there infinite possible moves. FindMoves returns all of the positions that a piece can move to
deem
deem13mo 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.
deem
deem13mo ago
I will try and work something out. Thanks for the help, I will definitely implement some optimizations you've mentioned as well
ZacharyPatten
ZacharyPatten13mo ago
thanks for sharing 🙂 will try to give it a look (and help you with your issue) when I have time
Murphy
Murphy13mo 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
deem
deem13mo ago
I understand now thank you 🙏
Murphy
Murphy13mo 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
ZacharyPatten13mo ago
@deemure are you still needing help with this topic?
Accord
Accord13mo 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.
Want results from more Discord servers?
Add your server
More Posts