multi-player games thoughts
Posted: Wed Oct 05, 2011 2:35 am
So I was pondering about multi-player games past few days ,when I decided to post the following rant
for the sake of those souls who need something fresh to think about There is a lot of opportunity for research
when you can't even use alpha-beta (or even negamax). Something simple like adding one more player brings
a whole lot of social studies to the mix. It has major applications to economics and social science in general.
My first attempt was to implement the paranoid algorithm. In this algorithm, the root player assumes the rest
of the players "gang up" on him to make his life miserable. This effectively reduces the n-player game into a
two player game where the n-1 players form a coalition against the one root player. (<skip>pretty much west vs gadafi IYKWIM</skip>)
Anyway this allowed me to use existing algorithms of Nebiyu with minor changes. The algorithm is not the best
because paranoic assumptions are usually not realistic. But it can be used for instance to get a lower bound score.
It can't get worse than the paranoic value!
-> coalitions are static. Maybe not for the whole game but atleast until the current root search finishes and a player makes a move.
This implies that the hash table has to be cleared at each move because the scores are always relative to the root player.
So the hashtable scores become useless when the root player changes.
-> with larger search depth parnoid gives bad results. The coalition is too much to handle for the root player.
For example score starts with about -6000 for three player chess (i.e if I don't scale it down). So searching deep
is not in his benefit for the root player. It can only discover it will get annihlated.
The second method is the "maxn" algorithm which is the complete opposite of paranoid player.
This is basically minmax for three or more players. Each player tries to maximize his own score regardless of opponent scores.
Unfortunately alpha-beta can not be used. Shallow alpha-beta pruning is possible under certain circumstances but the
deep-pruning is proven not to be applicable! You don't even need to order moves. Most of the pruning methods I read in general
give minimal improvements. Null move and futility pruning can not be used in general since they require alpha and beta .
Surprisingly I couldn't find use of LMR in literature. I tried it and it seems to give some increase in depth.
That is the only pruning scheme I have right now for this method.
In actual games coalitions form and break depending on who is ahead. So if one player is ahead, the other two will gang up on him
to bring his score down, so it is in his best interest not to "show off". So using purely paranoid algorithm is not realistic in most
cases. That cancels out alpha-beta and all of its derivatives. There are algorithms which mix paranoid and maxn, and they do not use
alpha-beta. One such algorithm is the social oriented search (SOS) where a player's animosity towards others is represented by a matrix.
The evaluation for players form a tuple. Hence multiplying the eval with the matrix gives a modified evaluation according to social orientation.
This can be dynamically adjusted according to the current board situation. All fascinating stuff if you want to read.
Btw I am experimenting with triple chess http://www.chessvariants.com/historic.d ... nelli.html
Rant is over. Thoughts are welcome.
cheers,
Daniel
for the sake of those souls who need something fresh to think about There is a lot of opportunity for research
when you can't even use alpha-beta (or even negamax). Something simple like adding one more player brings
a whole lot of social studies to the mix. It has major applications to economics and social science in general.
My first attempt was to implement the paranoid algorithm. In this algorithm, the root player assumes the rest
of the players "gang up" on him to make his life miserable. This effectively reduces the n-player game into a
two player game where the n-1 players form a coalition against the one root player. (<skip>pretty much west vs gadafi IYKWIM</skip>)
Anyway this allowed me to use existing algorithms of Nebiyu with minor changes. The algorithm is not the best
because paranoic assumptions are usually not realistic. But it can be used for instance to get a lower bound score.
It can't get worse than the paranoic value!
-> coalitions are static. Maybe not for the whole game but atleast until the current root search finishes and a player makes a move.
This implies that the hash table has to be cleared at each move because the scores are always relative to the root player.
So the hashtable scores become useless when the root player changes.
-> with larger search depth parnoid gives bad results. The coalition is too much to handle for the root player.
For example score starts with about -6000 for three player chess (i.e if I don't scale it down). So searching deep
is not in his benefit for the root player. It can only discover it will get annihlated.
The second method is the "maxn" algorithm which is the complete opposite of paranoid player.
This is basically minmax for three or more players. Each player tries to maximize his own score regardless of opponent scores.
Unfortunately alpha-beta can not be used. Shallow alpha-beta pruning is possible under certain circumstances but the
deep-pruning is proven not to be applicable! You don't even need to order moves. Most of the pruning methods I read in general
give minimal improvements. Null move and futility pruning can not be used in general since they require alpha and beta .
Surprisingly I couldn't find use of LMR in literature. I tried it and it seems to give some increase in depth.
That is the only pruning scheme I have right now for this method.
In actual games coalitions form and break depending on who is ahead. So if one player is ahead, the other two will gang up on him
to bring his score down, so it is in his best interest not to "show off". So using purely paranoid algorithm is not realistic in most
cases. That cancels out alpha-beta and all of its derivatives. There are algorithms which mix paranoid and maxn, and they do not use
alpha-beta. One such algorithm is the social oriented search (SOS) where a player's animosity towards others is represented by a matrix.
The evaluation for players form a tuple. Hence multiplying the eval with the matrix gives a modified evaluation according to social orientation.
This can be dynamically adjusted according to the current board situation. All fascinating stuff if you want to read.
Btw I am experimenting with triple chess http://www.chessvariants.com/historic.d ... nelli.html
Rant is over. Thoughts are welcome.
cheers,
Daniel