# Tagged Questions

64 views

### Chess Game with N knights [on hold]

Given an infinite chess board containing N knights. The bottom left corner of the board is labelled as (0,0). Two geeks decide to play the following game on the board : In one turn, a player may move ...
60 views

### Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
180 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 ...
41 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, ...
33 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 ...
384 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 ...
67 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 ...
67 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 ...
151 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 ...
116 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 ...
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 ...
59 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 ...
51 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]. ...
25 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 ...
123 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 ...
122 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 ...
40 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 ...
85 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 ...
152 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 ...
526 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 ...
84 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 ...
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 ...
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 ...
167 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 ...
129 views

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? ...
339 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 ...
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 ...
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 ...
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$ ...
### 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 ...