-1
votes
1answer
178 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
2answers
40 views

Do most nonograms not require backtracking?

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, ...
1
vote
1answer
30 views

An algorithm to rate players in team?

I would like to design an algorithm to rate players in a team sport. One team of N players plays a match against another team of N players. The individual players will possibly change, from match to ...
0
votes
2answers
380 views

Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
4
votes
1answer
59 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
1
vote
1answer
65 views

Game Of Strings

There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a ...
2
votes
1answer
144 views

Largest white rectangle on board

Given a string rectangular board which is divided into unit cells. Each cell is initially painted black or white. The character board[i][j] represents the cell with coordinates (i, j). Each of those ...
2
votes
1answer
115 views

Play with pairs of numbers

Two players are playing a game. The game is played on a sequence of positive integer pairs. The players make their moves alternatively. During his move the player chooses a pair and decreases the ...
1
vote
1answer
55 views

Game of chocolates

Two players A and B play a game alternatively and A starts the game. Their are 2 boxes of chocolates and we are Given the number of chocolates in both the boxes, let them be c1 and c2, the player ...
1
vote
2answers
57 views

Maze Connectivity

Given a grid maze which is an n × m rectangle maze where each cell is either empty, or is a wall. One can go from one cell to another only if both cells are empty and have a common side. Initially we ...
0
votes
0answers
48 views

Rectangle over rectangle

Given N rectangles cut out of paper. The rectangles are labeled 0 through N-1.I am having given int[]s X and Y with N elements each. For each i, the sides of rectangle i have lengths X[i] and Y[i]. ...
0
votes
0answers
23 views

what calculation/algorithm should I consider for finding the winner(s) of a series of games

first of all I'm not in any way a mathematician, so be kind ;) Our current routine: The game is a card game. At the end of each round cards still in your hand are summed up and make your points. The ...
1
vote
0answers
108 views

Make the maximum sum in a interval.

Two players $A$ and $B$ are playing a game with array $A$ of $N$ elements in which each player chooses an array interval with maximum sum. The other simultaneously chooses another interval in the same ...
1
vote
1answer
98 views

K piles stone game

Their are k piles with total n stones in some order where each pile can have stones greater or equal to zero.Two player A and B plays a game in which player A cant see the configuration of piles but ...
1
vote
1answer
38 views

Flipping the Grid

Suppose a grid of size N * M is having only 1 and 0. The rows are numbered from 1 to N, and the columns are numbered from 1 to M. Following steps can be called as a single move. Select two integers ...
0
votes
1answer
80 views

Partisan/Partial Game Theory

There are enough resources available on the internet regarding "impartial" game theory. But I cannot seem to find much information regarding "partial" game theory. Can someone name some such resources ...
2
votes
1answer
144 views

Placing K knights in an nxn board such that no two attack each other

This is a problem from spoj A and B are playing a very interesting variant of the ancient Indian game 'shatranj(also known as chess)' on a 'maidaan'(chessboard) n×n in size. They take turns ...
2
votes
1answer
510 views

Finding Pareto optimal solution set in $O(n \log n)$ time

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...
3
votes
1answer
77 views

Effecient way to find optimal solution in a 2 player game

I have a function: \begin{equation*} f(a_1,\ldots,a_7,b_1,\ldots,b_4)=-14-7 a_1+30 a_1 a_2-7 a_4-2 a_4 a_5+21 a_6+21 a_7+16 a_1 b_1-24 a_1 a_2 b_1+6 a_4 b_1-6 a_4 a_5 b_1+6 a_1 b_2-6 a_1 a_2 b_2+8 a_4 ...
0
votes
1answer
62 views

Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists. Can someone please tell me how do I ...
1
vote
0answers
56 views

Any known strategies for toads and frogs?

Are there any heuristic strategic for playing Toads and Frogs known? I reckon the optimal playthrough may be hard to achieve due to the game being NP-hard but at least something that regularly ...
1
vote
4answers
164 views

How to solve real-time games?

In game theory, we can solve a game by calculating its game tree as backward induction. This method seems to work for turn-based games, but how about real-time games? Are they have game trees? It ...
1
vote
2answers
129 views

Some Questions About Chess

I have to questions about the chess game: please help me to understand it. 1- How can a computer program know if this move or that move is better? It calculates all possbile continuation and examine? ...
3
votes
0answers
332 views

Simple game with coins - strategy

Let's play a game: There are $n$ stacks of coins in a row. $i$-th stack consists of $d_i$ coins. Two players: $\text{Player1},\text{Player2}$ make moves alternately. Player in his turn can only take ...
32
votes
1answer
1k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
2
votes
1answer
72 views

game strategy question

Let's say there are doors each with a lock on the integral points ($0$, $\pm1$, $\pm2$, $\cdots$) of the line. You are given a key which can only open a single lock, but you are not told what lock the ...
1
vote
1answer
756 views

Finding Nash equilibria using Support Enumeration

Chapter 3 of the Book "Algorithmic Game Theory" introduces an algorithm (page 8 of that PDF) to find mixed Nash equilibria for a bimatrix game $(A, B)$, which I struggle to understand. ($M$ and $N$ ...
2
votes
2answers
208 views

Mixed strategy nash equilibria in from $2\times N$ bimatrix form

I'm looking for a way of finding (manually!) mixed strategy Nash equilibria in a $2\times N$ game. Calling player 1 the player with two strategies and player 2 the one with $N$ strategies, I've ...