Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #38794 > unrolled thread

Logic conundrums in check

Back to article view | Back to comp.lang.javascript

Contents

  Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 03:25 -0700
    Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 03:28 -0700
    Re: Logic conundrums in check John G Harris <niam@jghnorth.org.uk.invalid> - 2020-09-17 14:09 +0100
      Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 07:25 -0700
        Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 23:50 -0700
      Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 07:32 -0700
      Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 07:54 -0700
      Re: Logic conundrums in check Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-17 21:19 +0100
        Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-17 13:57 -0700
    Re: Logic conundrums in check Arno Welzel <usenet@arnowelzel.de> - 2020-09-18 12:53 +0200
      Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-18 04:48 -0700
        Re: Logic conundrums in check Arno Welzel <usenet@arnowelzel.de> - 2020-09-19 15:17 +0200
          Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-19 07:58 -0700
            Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-19 08:02 -0700
            Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-19 08:05 -0700
            Re: Logic conundrums in check luserdroog <luser.droog@gmail.com> - 2020-09-19 11:27 -0700
              Re: Logic conundrums in check Arno Welzel <usenet@arnowelzel.de> - 2020-09-20 00:10 +0200
                Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-19 16:09 -0700
                Re: Logic conundrums in check luserdroog <luser.droog@gmail.com> - 2020-09-19 17:07 -0700
            Re: Logic conundrums in check Arno Welzel <usenet@arnowelzel.de> - 2020-09-20 00:08 +0200
    Re: Logic conundrums in check Scott Sauyet <scott@sauyet.com> - 2020-09-22 09:55 -0700
      Re: Logic conundrums in check Scott Sauyet <scott@sauyet.com> - 2020-09-22 10:01 -0700
        Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-23 02:26 -0700
          Re: Logic conundrums in check Scott Sauyet <scott.sauyet@gmail.com> - 2020-09-24 19:41 -0700
            Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-24 22:45 -0700
            Re: Logic conundrums in check Jonas Thörnvall <jonas.thornvall@gmail.com> - 2020-09-24 22:58 -0700

Page 2 of 2 — ← Prev page 1 [2]

#38827

jonas.thornvall@gmail.com wrote:

> I am a bit baffeled about the complexity of checking for check. 
> 
> Checking if the opponent make you check is straightforward, it is 
> just to scan the "occupied/controled tiles" of the opponent piece 
> just moved. 

That is not enough.  A check can be discovered, when the piece moved
clears the line between an attacker and the King.  You need to look
at whether any piece is checking you, and I think it becomes the same
problem as below.

> [ ... ]

> But knowing if you move one of your own pieces to cause your own 
> king to be checked seem to be a complete different animal. 
> 
> First you have to find your kings position "tile" i don't keep track
> of it.  Then it seem i actually have to make a "test move" actually
> moving my own piece to a new position. And then do the above king vs
> opponenet controled tiles. 
> 
> So to check if your king actually will become checked when you move 
> a piece seem to be the most computing intensive part of rules? 

> [ ... ]


I think you're probably falling victim to a design that's not well-
thought out.  I believe others have pointed out in these threads that
you seem to be missing some basic reusable data structures.  If I were
to approach this problem, I would start with some basic inexpensive 
data structures and functions that operate on them.  With that in mind
I would expect to write a function much like this:

    const kingInCheck = (board, color) =>
      getMoves (flipMove (board))
        .map (move => move .targetSquare)
        .includes (getSquares (board, color, 'K') [0]) 

This is of course untested, as I'm not writing a chess engine myself, 
but it's based on some simple ideas.

Here we start by calling `flipMove` which takes a board and returns a
new board identical to the original except with the other player to
move.  Then we call `getMoves` with that board, fetching a list of 
legal moves for the opponent.  We extract the target squares of those
moves, and test whether the resulting array includes the square that
holds the king, using `getSquares` to find which square that is. 

A Board might look like this:

    const board = {
      moveNumber: 21,
      activeColor: 'black',
      squares: [
        ['r', ' ', 'b', 'k', ' ', ' ', 'n', 'r'],
        ['p', ' ', ' ', 'p', ' ', 'p', 'N', 'p'],
        ['n', ' ', ' ', 'B', ' ', 'Q', ' ', ' '],
        [' ', 'p', ' ', 'N', 'P', ' ', ' ', 'P'],
        [' ', ' ', ' ', ' ', ' ', ' ', 'P', ' '],
        [' ', ' ', ' ', 'P', ' ', ' ', ' ', ' '],
        ['P', ' ', 'P', ' ', 'K', ' ', ' ', ' '],
        ['q', ' ', ' ', ' ', ' ', ' ', 'b', ' ']
      ],
      castlingAvailability: {
        whiteKingSide: false,
        whiteQueenSide: false,
        blackKingSide: false,
        blackQueenSide: false
      },
      enPassantTarget: null, // when pawn advances two squares
      halfMoveClock: 1 // for the 50-move draw rule
    }

I think that's all the information required to track a position 
completely.  There are many alternate formulations of the `squares`
property.  I would have to spend more time to decide which worked best
for me.


A Move might look like this: 

    const myMove = {
      color: 'black',
      piece: 'N', 
      sourceSquare: 'g8', 
      targetSquare: 'f6', 
      capture: true, 
      castling: false,  // probably redundant but useful
      enPassant: false  // ditto
    }

Color and Piece are probably just strings, but you might also use some
enumeration type for them.

This would require additional functions.  I don't try to implement the
fairly easy `getSquares` one or the harder `getMoves` one.  The other
two are trivial, though:

    // getSquares :: (Board, Color, Piece) => [Square] 
    const getSquares = (board, color, piece) => 
      'TODO' // for instance, with board supplied 
             // getSquares (board, 'black', 'K') //=> ['d8'] 

    // getMoves :: (Board) => [Move]
    const getMoves = (board) =>
      'TODO' // Given a board, return array of all possible moves
     
    // swapColor :: Color -> Color
    const swapColor = (color) =>
      color == 'black' ? 'white' : 'black' // or add error-checking

    // flipMove :: Board -> Board
    const flipMove = (board) => 
      ({...board, activeColor: swapColor (board .activeColor)})

    // kingInCheck :: (Board, Color) -> Bool
    const kingInCheck = (board, color) =>
      getMoves (flipMove (board))
        .map (move => move .targetSquare)
        .includes (getSquares (board, color, 'K') [0]) 
        // [0] since any legal board will only have one black King.

Note that in all these a Board is immutable.  If we need to look at
a different situation (even changing whose move it is in `flipColors`)
we create a new Board object, structurally sharing what we can of the
previous board.  This would apply even to functions like `makeMove`.
You should be able to cheaply create such boards as you do whatever
analysis you need to do, and then pass the resulting board to an
independent `display` function.

So I think you really might want to rethink the basic design.

  -- Scott

[toc] | [prev] | [next] | [standalone]

#38828

I wrote:

... a long code-filled post about the problem at hand.  I don't know 
if GG ate the formatting, but if you want to see it better formatted, 
I posted it in a Gist:

<https://gist.github.com/CrossEye/ffed6fb67b4d68f040165fc5c3a549e1>

  -- Scott

[toc] | [prev] | [next] | [standalone]

#38831

Den tisdag 22 september 2020 kl. 19:01:21 UTC+2 skrev Scott Sauyet:
> I wrote:
> 
> ... a long code-filled post about the problem at hand.  I don't know 
> if GG ate the formatting, but if you want to see it better formatted, 
> I posted it in a Gist:
> 
> <https://gist.github.com/CrossEye/ffed6fb67b4d68f040165fc5c3a549e1>
> 
>   -- Scott

I "think" my engine always detect when king become in check but probably doing analysis you want those cases solved before "at least before you move king". My engine seem to detect when the attacker block himself or you block him and then remove the check is detected. But maybe my idea just to ambitious or even redundant detect before moved.

I start to think maybe i should just redraw "own" moves putting king check have not decided yet.

[toc] | [prev] | [next] | [standalone]

#38859

jonas.thornvall@gmail.com wrote

> I "think" my engine always detect when king become in check but 
> probably doing analysis you want those cases solved before "at least
> before you move king". My engine seem to detect when the attacker
> block himself or you block him and then remove the check is detected.
> But maybe my idea just to ambitious or even redundant detect before
> moved.

I'm afraid I can make very little of that paragraph.  Could you try
restating it more clearly?


> I start to think maybe i should just redraw "own" moves putting king
> check have not decided yet. 

This is what people have been trying to explain.  You shouldn't have
anything to do with drawing the board when you're doing this sort of
analysis.  You need to break the problem up better.  The first step
in this is to create a data structure that captures a position, and
not link it to the UI.

  -- Scott

[toc] | [prev] | [next] | [standalone]

#38862

Den fredag 25 september 2020 kl. 04:41:14 UTC+2 skrev Scott Sauyet:
> jonas.thornvall@gmail.com wrote
> 
> > I "think" my engine always detect when king become in check but 
> > probably doing analysis you want those cases solved before "at least
> > before you move king". My engine seem to detect when the attacker
> > block himself or you block him and then remove the check is detected.
> > But maybe my idea just to ambitious or even redundant detect before
> > moved.
> 
> I'm afraid I can make very little of that paragraph.  Could you try
> restating it more clearly?
> 
> 
> > I start to think maybe i should just redraw "own" moves putting king
> > check have not decided yet. 
> 
> This is what people have been trying to explain.  You shouldn't have
> anything to do with drawing the board when you're doing this sort of
> analysis.  You need to break the problem up better.  The first step
> in this is to create a data structure that captures a position, and
> not link it to the UI.
> 
>   -- Scott

Well i will have a look at the bugs today i think i will sort them out, actually you could think of what i have done so far as an UI, that also hold the rules, and show potential moves.

That said the actual engine will rest upon those rules and the potential moves, so it will be a stripped down version without graphics generating a board tree, that the evaluation rules will be done at. Probably the first "heuristic?" engine will just be another JS file. But i plan to run over server generate communication via PHP "if i come so far".

And when on server you could potentially try build some AI thingy and DB to helpout.

But it is months until i am there, first i must get the ruleset and UI working. I read there is sort of testbench tool for chessengines called jasmine, i will test with it when i come so far.

[toc] | [prev] | [next] | [standalone]

#38863

Den fredag 25 september 2020 kl. 04:41:14 UTC+2 skrev Scott Sauyet:
> jonas.thornvall@gmail.com wrote
> 
> > I "think" my engine always detect when king become in check but 
> > probably doing analysis you want those cases solved before "at least
> > before you move king". My engine seem to detect when the attacker
> > block himself or you block him and then remove the check is detected.
> > But maybe my idea just to ambitious or even redundant detect before
> > moved.
> 
> I'm afraid I can make very little of that paragraph.  Could you try
> restating it more clearly?

The engine already handle all cases when you become check, but do not act upon them "not programmed yet". You can test block your own king from opponent piece and reveal it, it will be detected "red".
Same goes for the oppoent blocking his own piece that checks your king, when he removes it you automatically becomes check. So detection seem solved, but i must program the "allowed" resolving of become in check. Well it is basicly just to check if still in check after dummy move, but of course if the engine could show the options allowed "both blocks and king moves" that would be great and what i strive for. 

> 
> > I start to think maybe i should just redraw "own" moves putting king
> > check have not decided yet. 
> 
> This is what people have been trying to explain.  You shouldn't have
> anything to do with drawing the board when you're doing this sort of
> analysis.  You need to break the problem up better.  The first step
> in this is to create a data structure that captures a position, and
> not link it to the UI.

This is just a hobby project for two months, i am quite satisfied where it is going.
 
>   -- Scott

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.javascript

csiph-web